### Python 天梯赛 L2 一小时专项学习计划（由简入难） 本计划旨在利用一小时时间，针对 Python 天梯赛 L2 的核心考点进行高效复习与深化，内容安排遵循由基础操作到复杂算法的递进顺序，并穿插典型例题的快速解析。 #### 学习内容清单 | 时间段 | 学习模块 | 核心内容与目标 | 关键代码/练习要点 | | :--- | :--- | :--- | :--- | | **0-15分钟**<br>**基础巩固** | **1. 高效输入输出与数据解析** | 掌握大规模数据下的标准输入读取方法，熟悉常见数据格式（整数、字符串、列表）的快速解析。 | 使用 `sys.stdin.readline` 替代 `input()`，并处理尾随换行符[ref_3]。<br>练习：连续读取 N 行数据并转换为整数列表。 | | | **2. 列表、栈与队列的熟练应用** | 强化用列表模拟栈和队列的操作，理解其在模拟类题目中的核心作用。 | 栈：`list.append()` 入栈，`list.pop()` 出栈。<br>队列：`from collections import deque; q = deque(); q.append() / q.popleft()`[ref_1]。<br>练习：实现一个简单的括号匹配检查器。 | | **16-35分钟**<br>**数据结构深化** | **3. 字典与集合的妙用** | 学习利用字典进行计数、映射和状态记录，使用集合进行快速去重和成员检查，以优化查找效率。 | `dict.get(key, default)` 安全访问，`collections.Counter` 进行计数统计。<br>练习：给定一个列表，找出第一个重复出现的数字。 | | | **4. 树结构的构建与遍历** | 掌握使用邻接表（列表的列表或字典）表示树，并熟练编写递归与非递归的 DFS、BFS 遍历模板。 | 递归 DFS 模板，注意设置递归深度限制 (`sys.setrecursionlimit`)[ref_5]。<br>练习：给定父节点数组，构建树并计算每个节点的深度。 | | **36-55分钟**<br>**算法思想入门** | **5. 排序与自定义比较** | 掌握多关键字排序和复杂规则的排序实现，理解 `sorted(key=)` 和 `functools.cmp_to_key` 的用法。 | 使用 `lambda` 表达式定义排序键。<br>练习：对一组学生记录按成绩降序、姓名升序进行排序。 | | | **6. 贪心思想与简单模拟** | 理解贪心算法的局部最优选择思想，并应用于路径优化等问题。能够将复杂题目描述转化为清晰的模拟步骤。 | 分析 L2-043 “龙龙送外卖”中的贪心策略：总路径 = 边数×2 - 最大深度[ref_5]。<br>练习：模拟一个按特定规则排队的过程。 | | **56-60分钟**<br>**综合与回顾** | **7. 常见陷阱与优化回顾** | 回顾 Python 中常见的性能陷阱（如字符串拼接），并总结之前各模块的关键优化点。 | 字符串拼接务必使用 `‘’.join(list)`[ref_3]。<br>综合练习：快速阅读一道 L2 模拟题（如 L2-041 插松枝），梳理其解题步骤和所需的数据结构。 | #### 详细学习内容与代码示例 **第一部分：基础巩固 (0-15分钟)** 1. **输入输出优化**：这是所有题目的基础，处理不当会导致超时。 ```python import sys # 重定向标准输入，大幅提升读取速度 input = sys.stdin.readline # 读取一个整数 n = int(input().strip()) # .strip() 去除可能的换行符 # 读取一行由空格分隔的整数 arr = list(map(int, input().split())) # 读取 N 行数据 n = int(input().strip()) data_lines = [input().strip() for _ in range(n)] ``` 2. **栈与队列应用**：这是 L2 最频繁的考点之一[ref_1][ref_4]。 ```python # 栈的应用：判断括号字符串是否有效 def is_valid_parentheses(s: str) -> bool: stack = [] mapping = {‘)': ‘(‘, ‘]': ‘[‘, ‘}': ‘{‘} for char in s: if char in mapping.values(): # 左括号，入栈 stack.append(char) elif char in mapping: # 右括号，检查匹配 if not stack or stack[-1] != mapping[char]: return False stack.pop() return not stack # 栈空则有效 # 队列的应用：使用 collections.deque from collections import deque queue = deque() queue.append(‘a‘) # 入队 queue.append(‘b‘) front_item = queue.popleft() # 出队，得到 ‘a‘ ``` **第二部分：数据结构深化 (16-35分钟)** 3. **字典与集合**：用于优化查找，将 O(n) 降至 O(1)。 ```python # 使用字典记录元素索引，快速查找两数之和 def two_sum(nums, target): num_dict = {} for i, num in enumerate(nums): complement = target - num if complement in num_dict: # O(1)查找 return [num_dict[complement], i] num_dict[num] = i return [] # 使用集合进行去重和快速存在性检查 unique_nums = set([1, 2, 2, 3, 4]) # {1, 2, 3, 4} if 5 not in unique_nums: # O(1) 时间复杂度 print(“5 not in set“) ``` 4. **树的构建与遍历**：重点在于递归思想和状态的传递[ref_5]。 ```python import sys sys.setrecursionlimit(10**6) # 防止递归过深报错 # 假设输入是每个节点的父节点，-1表示根节点 parent = [2, 3, -1, 2] # 节点1~4的父节点，节点3是根 n = len(parent) children = [[] for _ in range(n+1)] # 邻接表，索引从1开始 root = -1 for i, p in enumerate(parent, start=1): if p == -1: root = i else: children[p].append(i) # DFS 计算深度 depth = [0]*(n+1) def dfs(u, d): depth[u] = d for v in children[u]: dfs(v, d+1) dfs(root, 0) print(depth[1:]) # 输出每个节点的深度 ``` **第三部分：算法思想入门 (36-55分钟)** 5. **复杂排序**：掌握灵活的多级排序是关键。 ```python students = [ {‘name‘: ‘Alice‘, ‘score‘: 90, ‘age‘: 20}, {‘name‘: ‘Bob‘, ‘score‘: 85, ‘age‘: 21}, {‘name‘: ‘Alice‘, ‘score‘: 95, ‘age‘: 20} ] # 按score降序，再按name升序排序 sorted_students = sorted(students, key=lambda x: (-x[‘score‘], x[‘name‘])) ``` 6. **贪心与模拟**：理解“龙龙送外卖”题的贪心核心。 ```python # 基于之前构建的树和深度数组，模拟新增标记节点过程 marked = [False]*(n+1) marked[root] = True max_depth = 0 total_edges_visited = 0 def add_destination(x): nonlocal max_depth, total_edges_visited path = [] # 向上回溯，直到遇到已标记的祖先 while not marked[x]: path.append(x) x = parent[x-1] # 假设parent是0-indexed的父节点列表 # 标记路径上的新节点 for node in reversed(path): # 从浅到深标记 marked[node] = True total_edges_visited += 1 max_depth = max(max_depth, depth[node]) # 计算当前最短总路径 return total_edges_visited * 2 - max_depth ``` **第四部分：综合与回顾 (56-60分钟)** * **陷阱回顾**： * **字符串拼接**：在循环中构建长字符串，必须使用列表收集后 join。 ```python # 错误：每次拼接都生成新字符串，效率极低 s = ‘’ for i in range(100000): s += str(i) # 正确：使用列表 parts = [] for i in range(100000): parts.append(str(i)) s = ‘’.join(parts) ``` * **递归深度**：树深度可能超过1000，需 `sys.setrecursionlimit(10**6)`。 * **列表复制**：直接赋值 (`list2 = list1`) 是浅拷贝，修改会相互影响。需使用 `list2 = list1.copy()` 或 `list2 = list1[:]`。 * **实战建议**：最后几分钟，快速在脑海中过一遍 L2 的典型解题流程：1. 解析题意与输入输出；2. 选择核心数据结构（栈、队列、树、字典）；3. 设计算法流程（模拟、搜索、贪心）；4. 编码实现，注意边界条件；5. 用样例和自测案例验证。