Python LeetCode & ACM笔试 极简速查表

1
2
3
4

# enumarate 同时获取索引和值
arr = ['a', 'b', 'c']
for i, val in enumerate(arr):
    print(f"Index: {i}, Value: {val}")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

import sys

# 1. 万能读取法 (应对空格、换行混乱的输入)
# 将所有输入全部读入，打平为一个一维列表，后续通过迭代器或指针逐步提取
data = sys.stdin.read().split() 
if not data: exit()
iterator = iter(data)
n = int(next(iterator)) # 提取第一个数

# 2. 单行读取 (极速版)
def get_ints():
    return list(map(int, sys.stdin.readline().split()))

# 3. 矩阵读取 (读取 n 行 m 列)
n, m = get_ints()
matrix = [get_ints() for _ in range(n)]

# 4. 高效输出
# print 在大量输出时很慢，改用 sys.stdout.write
sys.stdout.write(" ".join(map(str, result_list)) + "\n")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# 基础遍历 [0, n-1]
for i in range(n): pass

# 区间遍历 [1, n-1]
for i in range(1, n): pass

# 倒序遍历 [n-1, 0] (左闭右开，步长-1)
for i in range(n - 1, -1, -1): pass

# 步长遍历 (每次+2)
for i in range(0, n, 2): pass

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

# 1. 仅遍历值
for val in arr: pass

# 2. 同时获取索引和值 (高频)
for i, val in enumerate(arr): pass

# 3. 多序列并行遍历 (以最短为准)
for v1, v2 in zip(arr1, arr2): pass

# 4. 集合遍历 (无序)
for x in my_set: pass

# 5. 字典遍历
for k in my_dict: pass            # 仅遍历键 (默认行为)
for v in my_dict.values(): pass   # 仅遍历值
for k, v in my_dict.items(): pass # 同时遍历键值 (高频)
# 注意：严禁在遍历 Set/Dict 时修改其大小 (add/remove/pop)，否则报错

1
2
3
4
5
6
7

# 1. 标准边界控制 (如二分查找)
while left <= right: pass

# 2. 容器判空 (代替 C++ 的 !q.empty())
# 空列表 []、空集合 set() 均等价于 False
while q: 
    node = q.popleft()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# for...else / while...else 结构 (省去 bool 标记)
for x in arr:
    if x == target:
        break # 触发 break，直接跳出，不执行 else
else:
    # 循环自然跑完（未被 break 中断）时执行
    return "Not Found" 

# 基础控制符
continue # 跳过本次循环剩余代码，进入下一次
break    # 强制跳出当前所在的一层循环
pass     # 空语句占位符 (等价于 C++ 的 {})

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 1. 双端队列 (BFS 核心)
from collections import deque
q = deque([1, 2])
q.append(3)      # 尾部入队 O(1)
curr = q.popleft() # 头部出队 O(1) 

# 2. 自动初始化字典 (图论建图、归类核心)
from collections import defaultdict
adj = defaultdict(list) # 默认值为 []
adj[0].append(1)        # 免去 if 0 not in adj 的判断

# 3. 词频统计器
from collections import Counter
cnt = Counter("anagram") # {'a': 3, 'n': 1, 'g': 1, 'r': 1, 'm': 1}

# 4. 堆 / 优先队列 (Dijkstra、TopK 核心)
import heapq
arr = [3, 1, 2]
heapq.heapify(arr)       # 原地建小顶堆 O(N)
heapq.heappush(arr, 0)   # 插入 O(log N)
min_val = heapq.heappop(arr) # 弹出最小值 O(log N)
heapq.heappushpop(arr, 4) # 插入后弹出最小值 O(log N)
# 大顶堆技巧：压入 -x，弹出时再取负

1
2
3
4
5
6

import bisect
arr = [1, 2, 2, 4]
# 找第一个 >= x 的位置 (左侧插入点)
idx_left = bisect.bisect_left(arr, 2)  # 返回 1
# 找第一个 > x 的位置 (右侧插入点)
idx_right = bisect.bisect_right(arr, 2) # 返回 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

step = 0
visited = set([start])
q = deque([start])
while q:
    size = len(q)
    for _ in range(size): # 按层扩展
        curr = q.popleft()
        if curr == target: return step
        for nxt in graph[curr]:
            if nxt not in visited:
                visited.add(nxt)
                q.append(nxt)
    step += 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class UnionFind:
    def __init__(self, size):
        # 初始化：每个人的老总都是自己
        self.parent = [i for i in range(size)]
        # 记录以 i 为根的集合的大小，初始都是 1
        self.size = [1] * size
        # 连通分量的数量（有多少个独立的帮派）
        self.count = size

    def find(self, i):
        # 路径压缩 (Path Compression)
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        
        # 已经是同一个老总，无需合并
        if root_i == root_j:
            return False
            
        # 按大小合并 (Union by Size)：小树挂在大树下面
        if self.size[root_i] < self.size[root_j]:
            self.parent[root_i] = root_j
            self.size[root_j] += self.size[root_i]
        else:
            self.parent[root_j] = root_i
            self.size[root_i] += self.size[root_j]
            
        # 合并成功，独立帮派数量减一
        self.count -= 1
        return True
        
    def is_connected(self, i, j):
        # 判断两人是否连通
        return self.find(i) == self.find(j)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def dfs_template(node, state_var):
    # 1. 递归终止条件 (Base Case)
    # 遇到空节点、越界，或者满足特定结算条件时，立刻向上层返回
    if not node:
        return
    if is_target_reached(node):
        process_result(node, state_var)
        return

    # 2. 处理当前层逻辑 (Process Current Node)
    # 根据题意，修改状态变量或记录当前节点的信息
    update_state(state_var, node)

    # 3. 递归下探 (Drill Down)
    # 遍历所有可能的下一个节点（如树的左右子树，图的邻居节点）
    # 注意：下探时必须传递更新后的状态变量
    dfs_template(node.left, next_state(state_var))
    dfs_template(node.right, next_state(state_var))

    # 4. 恢复当前层状态 (Restore State / Backtrack) - 可选
    # 如果 state_var 是全局变量或可变对象（如列表），在回溯时需要撤销第2步的修改
    # 如果 state_var 是按值传递（如数字相加），则不需要此步
    revert_state(state_var, node)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

def zero_one_knapsack(weights, values, capacity):
    n = len(weights)
    
    # 1. 定义与初始化 DP 数组
    # dp[j] 表示：当背包容量为 j 时，能获得的最大价值（或最小代价）
    # 如果求最大值，初始化为 0；如果求最小值，初始化为 float('inf')
    dp = [0] * (capacity + 1)
    
    # base case: 容量为 0 时，价值为 0
    dp[0] = 0 

    # 2. 外层循环：遍历每一个物品
    for i in range(n):
        w = weights[i]
        v = values[i]
        
        # 3. 内层循环：遍历背包容量（核心难点：必须倒序！）
        # 倒序的原因：dp[j] 的更新依赖于上一层状态的 dp[j-w]。
        # 如果正序遍历，dp[j-w] 会在当前物品这一层被提前更新，导致同一个物品被重复放入（这就变成了完全背包问题）。
        for j in range(capacity, w - 1, -1):
            
            # 4. 状态转移方程 (State Transition)
            # 决策：是不放这个物品（保持 dp[j]），还是腾出 w 的空间放入这个物品（dp[j - w] + v）？
            # 根据题意取 max 或 min
            dp[j] = max(dp[j], dp[j - w] + v)

    # 5. 返回最终状态
    return dp[capacity]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isValidBST(root: TreeNode) -> bool:
    # 辩证点：不要单纯只判断左孩子小于根、右孩子大于根。
    # 必须传递一个不断收紧的上下界，确保整棵子树都符合规则。
    def dfs(node, lower, upper):
        if not node:
            return True
        if node.val <= lower or node.val >= upper:
            return False
        # 往左走，上限变成当前节点的值；往右走，下限变成当前节点的值
        return dfs(node.left, lower, node.val) and dfs(node.right, node.val, upper)
        
    return dfs(root, float('-inf'), float('inf'))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class TrieNode:
    def __init__(self):
        self.children = {}  # 存储子节点，例如 {'a': TrieNode, 'b': TrieNode}
        self.is_end = False # 标识此处是否构成一个完整的单词

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end # 必须是单词结尾才算找到

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

from collections import deque, defaultdict

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    # 1. 初始化邻接表和入度数组
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    
    # 2. 构建图 (prerequisites[i] = [a, b] 表示选 a 必须先学 b，即 b -> a)
    for course, pre in prerequisites:
        graph[pre].append(course)
        in_degree[course] += 1
        
    # 3. 将所有入度为 0 的节点（即不需要任何先修课的课程）入队
    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    
    # 4. 记录已完成的课程数量
    completed_count = 0
    
    while queue:
        node = queue.popleft()
        completed_count += 1
        
        # 将依赖该课程的所有后续课程入度减 1
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            # 一旦前置依赖全部解除，加入队列准备学习
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
                
    # 辩证点：如果完成的数量等于总课程数，说明不存在环，可以学完。
    # 如果最后还有课程没学完（入度死活降不到0），说明图里必定存在互相依赖的“死锁环”。
    return completed_count == numCourses