专为 AI 算法工程师转岗/晋升面试设计 | 涵盖概念讲解 · 完整解题模板 · 每日练习清单
算法面试本质是模式识别——遇到题目，快速匹配已知解题模板，再加以变通。盲目刷题不如系统训练题型。
两周策略： - 第一周（Day 1–7）：打牢基础数据结构 + 核心算法思想 - 第二周（Day 8–14）：进阶题型 + 综合训练 + 模拟面试
每日节奏（建议）：
⚠️ 关键原则：每道题做完后，必须能用一句话说出「这道题用了什么技巧、为什么」，否则重做。
算法题型 ├── 基础数据结构 │ ├── 数组 / 字符串 │ ├── 链表 │ ├── 栈 / 队列 │ └── 哈希表 ├── 树与图 │ ├── 二叉树（DFS / BFS） │ ├── 二叉搜索树 │ └── 图（拓扑排序 / 最短路） ├── 核心算法思想 │ ├── 双指针 / 滑动窗口 │ ├── 二分查找 │ ├── 排序算法 │ └── 前缀和 / 差分 ├── 递归与回溯 │ ├── 排列 / 组合 / 子集 │ └── N 皇后 / 数独类 ├── 动态规划 │ ├── 一维 DP（线性） │ ├── 二维 DP（路径 / 区间） │ ├── 背包问题 │ └── 字符串 DP └── 进阶专题 ├── 堆 / 优先队列 ├── 单调栈 / 单调队列 └── 并查集 / Trie
数组（Array） 是最基础的数据结构，在内存中连续存储一组相同类型的元素。通过下标（索引）可以在 O(1) 时间内随机访问任意元素。
双指针（Two Pointers） 是一种思维技巧，并不是特殊的数据结构。核心思想是：用两个变量（left 和 right）同时指向数组的不同位置，通过协调移动这两个指针来避免暴力的 O(n²) 双重循环，将时间复杂度降低到 O(n)。
left
right
双指针有两种形态： - 对撞指针：left 从左端出发，right 从右端出发，两者相向而行，适合处理有序数组的两端夹逼问题。 - 快慢指针：slow 和 fast 都从左端出发，但移动速度不同，常用于链表（见 Day 2）或数组去重。
slow
fast
滑动窗口（Sliding Window） 是双指针的进化版本，专门用来处理「连续子数组/子串」的最值问题。把 left 和 right 想象成一扇窗户的左右边框：right 不断向右扩大窗口来纳入新元素，当窗口内的状态不满足条件时，收缩 left 缩小窗口，直到满足条件为止。整个过程每个元素最多被访问两次（进窗口一次、出窗口一次），因此时间复杂度是 O(n)。
适用场景：有序数组中寻找满足条件的两个数（如两数之和等于目标值）。
核心逻辑：若两数之和等于目标，记录结果；若偏小，左指针右移；若偏大，右指针左移。
def two_sum_sorted(nums, target): """ 在有序数组 nums 中找两个数使其和等于 target 变量说明： nums : 已排序的整数数组，例如 [2, 7, 11, 15] target : 目标和，例如 9 left : 左指针，初始指向数组第一个元素（索引 0） right : 右指针，初始指向数组最后一个元素（索引 len-1） result : 存储找到的答案对 """ left = 0 # 左指针从最左端出发 right = len(nums) - 1 # 右指针从最右端出发 result = [] while left < right: # 两指针未相遇时持续循环 current_sum = nums[left] + nums[right] if current_sum == target: result.append([nums[left], nums[right]]) # 找到一对答案 left += 1 # 继续寻找下一对（两指针同时内缩） right -= 1 elif current_sum < target: # 当前和太小，需要更大的数 → 左指针右移，换一个更大的数 left += 1 else: # 当前和太大，需要更小的数 → 右指针左移，换一个更小的数 right -= 1 return result
适用场景：原地修改有序数组，删除重复元素，不允许使用额外空间。
核心逻辑：slow 指针指向已处理好的数组末尾，fast 指针负责扫描；当 fast 发现新元素时，将其写入 slow 位置并推进 slow。
def remove_duplicates(nums): """ 原地删除有序数组 nums 中的重复项，返回去重后的长度 变量说明： nums : 已排序的数组，例如 [1, 1, 2, 3, 3] slow : 慢指针，始终指向已处理的无重复子数组的最后一个位置 fast : 快指针，负责向前扫描寻找不重复的新元素 过程示意（以 [1,1,2,3,3] 为例）： 初始：slow=0, fast=0，nums[slow]=1 fast=1：nums[1]=1 == nums[0]=1，跳过（重复） fast=2：nums[2]=2 != nums[0]=1，写入 slow+1=1 位置，slow=1 fast=3：nums[3]=3 != nums[1]=2，写入 slow+1=2 位置，slow=2 fast=4：nums[4]=3 == nums[2]=3，跳过（重复） 结果：nums[:slow+1] = [1, 2, 3]，返回长度 3 """ if not nums: return 0 slow = 0 # slow 从 0 出发，表示当前已确定的无重复序列长度为 slow+1 for fast in range(1, len(nums)): # fast 从 1 开始向右扫描 if nums[fast] != nums[slow]: # 发现了一个和当前末尾不同的新元素 slow += 1 # 将 slow 向前推进一位 nums[slow] = nums[fast] # 把新元素写到 slow 位置 return slow + 1 # 无重复子数组的长度
适用场景：寻找满足某条件的最长（或最短）连续子串/子数组。
核心逻辑：right 不断右扩纳入新字符；当窗口不满足条件时，不断右移 left 直到重新满足；每次更新最优结果。
from collections import defaultdict def length_of_longest_substring(s): """ 求字符串 s 中不含重复字符的最长子串长度（LC 3 的解法） 变量说明： s : 输入字符串，例如 "abcabcbb" window : 字典，记录当前窗口内每个字符出现的次数 key = 字符，value = 该字符在窗口内的出现次数 left : 窗口左边界（闭区间），初始为 0 right : 窗口右边界（闭区间），由 for 循环控制右扩 res : 记录遍历过程中出现的最长不重复子串长度 过程示意（以 "abcabcbb" 为例）： right=0，加入'a'，窗口="a"，无重复，res=1 right=1，加入'b'，窗口="ab"，无重复，res=2 right=2，加入'c'，窗口="abc"，无重复，res=3 right=3，加入'a'，窗口="abca"，'a'重复！ → 移除 s[left]='a'，left=1，窗口="bca"，不再重复 right=4，加入'b'，窗口="bcab"，'b'重复！ → 移除 s[left]='b'，left=2，窗口="cab"，不再重复 ... 最终 res=3 """ window = defaultdict(int) # 窗口内字符频次，defaultdict 默认值为 0，避免 KeyError left = 0 # 窗口左边界 res = 0 # 最终答案（最长不重复子串长度） for right in range(len(s)): # right 右指针逐步右移，扩大窗口 window[s[right]] += 1 # 将 s[right] 加入窗口，频次 +1 # 当窗口内某字符出现超过 1 次，说明出现了重复，需要收缩左边界 while window[s[right]] > 1: window[s[left]] -= 1 # 将 s[left] 移出窗口，频次 -1 left += 1 # 左边界右移 # 此时窗口内无重复字符，更新最大长度 res = max(res, right - left + 1) # 窗口长度 = right - left + 1 return res
💡 今日重点：先彻底搞懂 LC 3（最长不重复子串）的窗口收缩逻辑，LC 76 是它的升级版。
链表（Linked List） 是一种通过「指针」将节点串联起来的数据结构。每个节点包含两部分：存储数据的 val 字段，以及指向下一个节点的 next 指针。
val
next
链表与数组的核心区别： - 数组：内存连续，支持 O(1) 随机访问，但插入/删除需要移动元素，代价 O(n) - 链表：内存不连续，只能从头顺序访问（O(n)），但插入/删除只需修改指针，代价 O(1)
面试中链表节点的标准定义：
class ListNode: def __init__(self, val=0, next=None): self.val = val # 节点存储的值 self.next = next # 指向下一个节点的引用（None 表示链表结尾）
链表题的三大核心技巧： 1. 虚拟头节点（Dummy Head）：在链表真正头节点之前额外添加一个哑节点，目的是统一头节点和普通节点的处理逻辑，避免各种「头节点特判」。 2. 快慢指针：两个指针从同一起点出发，fast 每次走两步，slow 每次走一步。利用速度差可以找中点、判断环、找环入口等。 3. 画图辅助：反转链表等操作涉及多个指针同时变化，强烈建议先画出指针变化图再写代码，避免顺序搞错导致节点丢失。
核心逻辑：用三个指针维护「上一个节点」「当前节点」「下一个节点」，逐步将每个节点的 next 反向。
def reverse_list(head): """ 反转整个链表，返回反转后的新头节点 变量说明： head : 原链表头节点，例如 1->2->3->4->5->None prev : 前驱节点指针，初始为 None（反转后它会成为新链表的尾节点） curr : 当前正在处理的节点，初始指向 head nxt : 临时保存 curr.next，防止反转 curr.next 后找不到下一个节点 过程示意（以 1->2->3->None 为例）： 初始：prev=None, curr=1 第1轮：nxt=2，1.next=None，prev=1，curr=2 → None<-1 2->3 第2轮：nxt=3，2.next=1， prev=2，curr=3 → None<-1<-2 3->None 第3轮：nxt=None，3.next=2，prev=3，curr=None → None<-1<-2<-3 curr 为 None，循环结束，返回 prev=3（新头节点） """ prev = None # prev 初始为 None，最终会成为反转链表的尾节点（指向 None） curr = head # curr 从头节点开始逐个处理 while curr is not None: # 当 curr 不为空时持续处理 nxt = curr.next # ① 先保存下一个节点，防止丢失 curr.next = prev # ② 将当前节点的 next 反向指向 prev prev = curr # ③ prev 前进到当前节点 curr = nxt # ④ curr 前进到原来保存的下一个节点 return prev # 循环结束时 curr=None，prev 指向原链表最后一个节点（即新头节点）
核心逻辑：fast 每次走两步，slow 每次走一步；当 fast 到达末尾时，slow 恰好在中间。
def find_middle(head): """ 找到链表的中间节点 变量说明： head : 链表头节点 slow : 慢指针，每次移动一步 fast : 快指针，每次移动两步 为什么这样能找到中点？ 假设链表长度为 n，fast 走了 k 步后到达末尾，则 fast 走了约 n 步。 因为 fast 速度是 slow 的 2 倍，所以 slow 走了约 n/2 步，恰好在中间。 过程示意（以 1->2->3->4->5 为例）： 初始：slow=1, fast=1 第1步：slow=2, fast=3 第2步：slow=3, fast=5 fast.next=None，循环终止，slow=3（第3个节点，即中点） 对于偶数长度（1->2->3->4）： 初始：slow=1, fast=1 第1步：slow=2, fast=3 第2步：fast.next=None，循环终止，slow=2（偏左的中点） """ slow = head # 慢指针从头出发 fast = head # 快指针从头出发 # 终止条件：fast 到达最后一个节点（fast.next=None）或 fast 已超出链表（fast=None） while fast is not None and fast.next is not None: slow = slow.next # slow 每次走一步 fast = fast.next.next # fast 每次走两步 return slow # 返回中间节点
核心逻辑：创建一个值无意义的哑节点作为「假头」，让所有实际节点都变成「普通节点」处理，避免头节点的特殊判断。
def delete_nth_from_end(head, n): """ 删除链表倒数第 n 个节点，返回新链表头（LC 19） 变量说明： head : 原链表头节点 n : 要删除的倒数第几个节点（n >= 1） dummy : 虚拟头节点，值为 0，其 next 指向真正的 head 作用：即使删除的是真正的头节点，也不需要特殊处理 fast : 快指针，先走 n+1 步，形成与 slow 的 n 步差距 slow : 慢指针，最终停在倒数第 n 个节点的前一个位置 思路： 要删除倒数第 n 个节点，需要找到它的「前驱节点」。 让 fast 先走 n+1 步，然后 fast 和 slow 同步前进， 当 fast 到达 None（链表末尾之后）时，slow 恰好在目标节点的前驱位置。 """ dummy = ListNode(0) # 创建虚拟头节点，值任意（通常写 0） dummy.next = head # 虚拟头节点指向真实头节点 fast = dummy # fast 从虚拟头出发 slow = dummy # slow 从虚拟头出发 # fast 先走 n+1 步（走 n+1 步而非 n 步，是为了让 slow 停在目标的前驱） for _ in range(n + 1): fast = fast.next # fast 和 slow 同步前进，直到 fast 到达 None while fast is not None: fast = fast.next slow = slow.next # 此时 slow 在倒数第 n+1 个节点（目标节点的前驱），执行删除 slow.next = slow.next.next # 跳过目标节点，完成删除 return dummy.next # 返回真实头节点（dummy.next，因为 dummy 是虚拟的）
💡 今日重点：LC 142 的精妙之处在于数学推导——从头节点和快慢指针相遇点同速出发，会在环入口相遇，建议手推一遍验证。
栈（Stack） 是一种「后进先出（LIFO）」的数据结构，只能从一端（栈顶）进行插入（push）和删除（pop）操作。类比：叠放的盘子，只能从最上面取。Python 中直接用列表模拟：stack = []，stack.append(x) 入栈，stack.pop() 出栈，stack[-1] 查看栈顶。
stack = []
stack.append(x)
stack.pop()
stack[-1]
单调栈（Monotonic Stack） 是栈的特殊使用方式：栈内元素始终保持单调递增或单调递减的顺序。它用来高效解决「寻找数组中每个元素左/右第一个比它大/小的元素」这类问题，时间复杂度 O(n)。
队列（Queue） 是一种「先进先出（FIFO）」的数据结构，从队尾插入，从队头取出。类比：排队买票，先来先服务。Python 中用 collections.deque 实现：queue.append(x) 入队，queue.popleft() 出队（效率远高于 list.pop(0)）。
collections.deque
queue.append(x)
queue.popleft()
list.pop(0)
哈希表（Hash Table） 也叫字典（Dictionary），是一种通过「键值对（key-value）」存储数据的数据结构，支持 O(1) 的平均插入、查找、删除操作。
哈希表的核心原理：通过一个哈希函数将 key 映射到数组的某个下标，直接定位存储位置。例如，将字符串 key="name" 经哈希函数算出下标 3，然后把 value="Alice" 存在第 3 个槽位——这样查找时也只需一次哈希运算就能定位，而不需要遍历。
哈希表解决的核心问题：用 O(n) 的额外空间，将查找时间从 O(n) 降到 O(1)（经典的以空间换时间）。
核心逻辑：遇到左括号就压栈；遇到右括号时，检查栈顶是否是对应的左括号，匹配则弹出，不匹配则非法。
def is_valid_parentheses(s): """ 判断括号字符串 s 是否合法（LC 20） 例如 "()" 合法，"([)]" 不合法，"{[]}" 合法 变量说明： s : 只包含 '(', ')', '{', '}', '[', ']' 的字符串 stack : 列表模拟的栈，存放遇到的左括号 pairs : 哈希表，存储右括号→对应左括号的映射关系 用于快速判断右括号对应哪个左括号 算法思路： 遍历字符串，遇到左括号就压入栈； 遇到右括号时，若栈为空或栈顶不是对应左括号，则不合法； 否则弹出栈顶（成功配对）。 最终栈为空说明所有括号都配对成功。 """ stack = [] # 初始空栈 # 哈希表：右括号 → 对应的左括号（用于快速查找） pairs = { ')': '(', '}': '{', ']': '[' } for ch in s: # 遍历字符串每个字符 if ch in '({[': # 遇到左括号，压入栈中等待配对 stack.append(ch) else: # 遇到右括号，需要与栈顶左括号配对 if not stack: # 栈为空，无左括号可配对，非法 return False if stack[-1] != pairs[ch]: # 栈顶左括号与当前右括号不匹配，非法 return False stack.pop() # 匹配成功，弹出栈顶左括号 return len(stack) == 0 # 栈空 → 所有括号都配对成功；栈不空 → 有未配对的左括号
核心逻辑：维护一个「单调递减栈」（栈底最大），当新元素比栈顶大时，说明找到了栈顶元素「右边第一个更大值」，弹出并记录答案。
def next_greater_element(nums): """ 对数组 nums 中每个元素，找出其右侧第一个比它大的元素 如果不存在，返回 -1（LC 496 / LC 739 的核心逻辑） 例如 nums = [2, 1, 5, 3]，结果应为 [5, 5, -1, -1] 变量说明： nums : 输入整数数组，例如 [2, 1, 5, 3] n : 数组长度 stack : 单调递减栈，存储元素的「索引」（不是值！存索引方便更新结果） 栈内索引对应的值从栈底到栈顶单调递减 res : 结果数组，res[i] 表示 nums[i] 右边第一个更大的值，初始全为 -1 为什么存索引而不是值？ 找到答案时需要更新 res[idx]，必须知道是哪个位置的元素，所以存索引。 过程示意（nums = [2, 1, 5, 3]）： i=0：stack=[], 直接入栈。stack=[0]（代表值2） i=1：nums[1]=1 < nums[stack[-1]]=2，不弹栈，直接入栈。stack=[0,1] i=2：nums[2]=5 > nums[stack[-1]]=1，弹出1，res[1]=5； 继续：5 > nums[stack[-1]]=2，弹出0，res[0]=5； 栈空，入栈。stack=[2] i=3：nums[3]=3 < nums[stack[-1]]=5，不弹栈，入栈。stack=[2,3] 遍历结束，栈内剩余 [2,3] 对应的元素无更大值，res 保持 -1。 最终 res = [5, 5, -1, -1] """ n = len(nums) stack = [] # 单调递减栈，存索引 res = [-1] * n # 结果数组，默认 -1（表示右边没有更大的元素） for i in range(n): # 从左到右遍历每个元素 # 当栈不为空，且当前元素比栈顶索引对应的元素大时，弹栈 while stack and nums[stack[-1]] < nums[i]: idx = stack.pop() # 弹出栈顶索引 res[idx] = nums[i] # nums[i] 就是 nums[idx] 右边第一个更大值 stack.append(i) # 当前索引入栈（等待找到它右边的更大值） # 循环结束后，栈中剩余的索引对应的元素，右边没有更大值，res 已默认为 -1 return res
核心逻辑：遍历数组，对每个元素 x，用哈希表 O(1) 查找「target - x 是否已出现过」，而不是对每对元素都检查一遍（那样是 O(n²)）。
def two_sum(nums, target): """ 在数组 nums 中找两个数使其和等于 target，返回它们的下标（LC 1） 变量说明： nums : 整数数组，例如 [2, 7, 11, 15] target : 目标和，例如 9 seen : 哈希表（字典），记录已遍历过的元素 key = 元素值，value = 该元素在 nums 中的索引 complement : 当前元素 nums[i] 需要的「配对数」= target - nums[i] 算法思路： 遍历数组，对每个 nums[i]，计算需要的配对数 complement = target - nums[i]。 如果 complement 在 seen 中，说明之前遍历过的某个数和当前数加起来等于 target， 直接返回两者的下标。 否则，将 nums[i] 及其下标存入 seen，供后续元素查询。 过程示意（nums=[2,7,11,15], target=9）： i=0：nums[0]=2，complement=7，seen 中无 7，将 {2:0} 存入 seen i=1：nums[1]=7，complement=2，seen 中有 2（索引为 0），返回 [0, 1] """ seen = {} # 哈希表：{元素值: 元素在 nums 中的索引} for i, num in enumerate(nums): # enumerate 同时获取下标 i 和值 num complement = target - num # 计算当前元素需要的配对数 if complement in seen: # O(1) 查询：配对数是否已经存在于哈希表中 return [seen[complement], i] # 找到答案，返回两个下标 seen[num] = i # 未找到，将当前元素存入哈希表 return [] # 无解（题目保证有解时可省略） def group_anagrams(strs): """ 将字符串数组按字母异位词分组（LC 49） 变量说明： strs : 字符串数组，例如 ["eat","tea","tan","ate","nat","bat"] groups : 哈希表，key = 排序后的字符串（作为同组的唯一标识）， value = 所有排序后相同的原始字符串列表 核心思路： 字母异位词排序后结果相同（"eat" 和 "tea" 排序后都是 "aet"）。 以排序结果作为 key，将原始字符串分组到对应 key 下。 """ groups = defaultdict(list) # defaultdict(list)：key 不存在时自动创建空列表 for s in strs: key = ''.join(sorted(s)) # 将字符串排序后作为哈希 key（如 "eat" → "aet"） groups[key].append(s) # 将原始字符串追加到对应分组 return list(groups.values()) # 返回所有分组（值列表）
二叉树（Binary Tree） 是每个节点最多有两个子节点（左子节点和右子节点）的树形数据结构。节点的标准定义：
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val # 节点存储的值 self.left = left # 左子节点（TreeNode 或 None） self.right = right # 右子节点（TreeNode 或 None）
DFS（深度优先搜索） 的含义：从根节点出发，沿着一条路径一直深入到叶子节点，然后回退，再探索下一条路径。在二叉树中，DFS 对应三种遍历顺序：
递归是二叉树 DFS 的天然实现方式。理解递归的关键是「信任递归」：你不需要想清楚递归是怎么一步步执行的，只需要相信「solve(root.left) 会正确返回左子树的答案」，然后利用这个答案来组合出当前节点的答案。
solve(root.left)
遇到二叉树题，先判断属于哪种模式： 1. 遍历模式：通过 DFS 遍历树，用一个外部变量（全局变量或列表）收集结果。 2. 分解模式：将问题拆解为「如果知道了左右子树的答案，怎么得到整棵树的答案」，通过返回值逐层传递。
def traverse(root): """ 二叉树三种 DFS 遍历的统一框架 变量说明： root : 当前节点（TreeNode 或 None） 递归时，root 依次代表树中的每一个节点 三种遍历只有「处理 root 的位置」不同： 前序（Preorder）：先处理 root，再递归左右 中序（Inorder）：递归左，处理 root，递归右 后序（Postorder）：递归左右，最后处理 root """ if root is None: # 递归终止条件：遇到空节点，直接返回 return # ↓ 前序位置：在这里写处理 root 的逻辑（此时左右子树还未被访问） print(root.val) # 示例：打印节点值 traverse(root.left) # 递归处理左子树 # ↓ 中序位置：在这里写处理 root 的逻辑（此时左子树已处理完） # print(root.val) # 如果改为中序，把打印语句移到这里 traverse(root.right) # 递归处理右子树 # ↓ 后序位置：在这里写处理 root 的逻辑（此时左右子树都已处理完） # print(root.val) # 如果改为后序，把打印语句移到这里
核心思路：「整棵树的最大深度」= max(左子树最大深度, 右子树最大深度) + 1。通过函数返回值传递子树信息。
def max_depth(root): """ 计算二叉树的最大深度（LC 104） 变量说明： root : 当前节点 left_depth : 左子树的最大深度（由递归得到） right_depth : 右子树的最大深度（由递归得到） 递归思路： 1. 空节点的深度为 0（base case） 2. 非空节点的深度 = max(左子树深度, 右子树深度) + 1（+1 是当前节点本身） 以下图为例： 3 / \ 9 20 / \ 15 7 max_depth(9) = max(0,0)+1 = 1 max_depth(15) = max(0,0)+1 = 1 max_depth(7) = max(0,0)+1 = 1 max_depth(20) = max(1,1)+1 = 2 max_depth(3) = max(1,2)+1 = 3 ← 答案 """ if root is None: # base case：空节点深度为 0 return 0 left_depth = max_depth(root.left) # 递归获取左子树深度 right_depth = max_depth(root.right) # 递归获取右子树深度 # 后序位置：左右子树的结果都拿到了，组合出当前节点的答案 return max(left_depth, right_depth) + 1 # +1 表示当前节点这一层
核心思路：前序遍历时将当前节点加入路径；到达叶子时记录路径；回溯时从路径中删除当前节点，恢复状态。
def path_sum(root, target_sum): """ 找出所有从根节点到叶子节点的路径，使得路径上节点值之和等于 target_sum（LC 113） 变量说明： root : 二叉树根节点 target_sum : 目标路径和 result : 最终结果列表，存储所有满足条件的路径（每条路径是一个列表） path : 当前正在探索的路径（从根到当前节点的节点值列表） """ result = [] # 存储所有满足条件的路径 path = [] # 记录当前路径（从根到当前节点） def dfs(node, remaining): """ 变量说明： node : 当前访问的节点 remaining : 路径还需要凑够的剩余目标和（每经过一个节点就减去该节点的值） """ if node is None: # 遇到空节点，返回 return path.append(node.val) # ① 做选择：将当前节点加入路径 remaining -= node.val # 减去当前节点的值 # 判断是否到达叶子节点且路径和满足条件 if node.left is None and node.right is None and remaining == 0: result.append(list(path)) # 注意：必须用 list(path) 拷贝，否则后续修改会影响结果 dfs(node.left, remaining) # 递归探索左子树 dfs(node.right, remaining) # 递归探索右子树 path.pop() # ② 撤销选择（回溯！）：离开当前节点，从路径中移除，恢复状态 dfs(root, target_sum) return result
💡 今日重点：LC 543（直径 = 左子树高度 + 右子树高度）和 LC 236（LCA 后序处理）是高频题型，模板背熟。
BFS（广度优先搜索） 的含义：从根节点出发，先访问所有距离根节点为 1 的节点，再访问距离为 2 的节点，以此类推——即「按层」从上到下逐层访问。
BFS 使用队列（Queue）实现：初始将根节点入队；每次从队头取出一个节点访问，并将其所有子节点加入队尾。Python 中用 collections.deque 实现队列（双端队列），deque.popleft() 是 O(1) 的，而 list.pop(0) 是 O(n) 的。
deque.popleft()
层序遍历的关键技巧：在每层开始时记录 len(queue)，然后只处理这固定数量的节点，确保每次内层循环只处理同一层的节点。
len(queue)
二叉搜索树（BST，Binary Search Tree） 是满足以下性质的二叉树： - 左子树中所有节点的值 < 根节点的值 - 右子树中所有节点的值 > 根节点的值 - 左右子树本身也是 BST
BST 的关键性质：中序遍历（左→根→右）的结果是严格递增的有序序列。因此，很多 BST 题目可以转化为「有序数组」的问题。
from collections import deque def level_order(root): """ 二叉树层序遍历，返回按层分组的节点值（LC 102） 例如： 3 / \ 9 20 / \ 15 7 返回：[[3], [9, 20], [15, 7]] 变量说明： root : 二叉树根节点 queue : 双端队列，存储待访问的节点，初始只有根节点 res : 结果列表，每个元素是一层节点值的列表 level : 当前层的节点值列表，每层开始时初始化为空 size : 当前层的节点数量（在处理每层前固定下来，防止处理过程中 queue 长度变化） """ if root is None: return [] queue = deque([root]) # 初始化队列，根节点入队 res = [] # 存储所有层的结果 while queue: # 队列不为空时，说明还有节点未处理 size = len(queue) # 关键！固定本层节点数（此时队列中恰好存着这一层的所有节点） level = [] # 存储本层的节点值 for _ in range(size): # 只处理本层的 size 个节点 node = queue.popleft() # 从队头取出节点 level.append(node.val) # 记录节点值 if node.left: # 将左子节点（下一层）加入队尾 queue.append(node.left) if node.right: # 将右子节点（下一层）加入队尾 queue.append(node.right) res.append(level) # 本层处理完毕，将本层结果加入总结果 return res
核心思路：对每个节点，不只检查与直接父节点的大小关系，而是传递一个「合法值的范围 [lo, hi]」，确保整棵子树的值都在这个范围内。
def is_valid_bst(root, lo=float('-inf'), hi=float('inf')): """ 验证二叉搜索树（LC 98） 变量说明： root : 当前节点 lo : 当前节点值的下界（当前节点值必须严格大于 lo） 初始为负无穷（根节点没有下界限制） hi : 当前节点值的上界（当前节点值必须严格小于 hi） 初始为正无穷（根节点没有上界限制） 为什么需要传递上下界？ 只比较父子节点不够。例如： 5 / \ 1 4 / \ 3 6 节点 4 满足「小于父节点 5」，但整棵右子树的节点都应该大于 5！ 所以必须向下传递「当前子树所有节点的合法范围」。 递归逻辑： - 对根节点调用：is_valid_bst(root, -inf, +inf)，无限制 - 递归左子树：所有节点必须 < root.val，上界变为 root.val - 递归右子树：所有节点必须 > root.val，下界变为 root.val """ if root is None: return True # 空树是合法的 BST # 当前节点的值必须在 (lo, hi) 开区间内 if root.val <= lo or root.val >= hi: return False # 递归验证左子树：左子树所有节点必须 < root.val，所以上界更新为 root.val left_valid = is_valid_bst(root.left, lo, root.val) # 递归验证右子树：右子树所有节点必须 > root.val，所以下界更新为 root.val right_valid = is_valid_bst(root.right, root.val, hi) return left_valid and right_valid
二分查找（Binary Search） 是一种在有序数组中查找目标值的高效算法，每次比较后排除一半的候选范围，时间复杂度 O(log n)。
更广义地理解：二分查找的本质不是「在数组中找一个值」，而是在具有单调性的答案空间中高效定位目标。只要满足「答案越大/越小，某个条件越容易/越难满足」这种单调性，就可以对「答案本身」二分搜索，这被称为「在答案空间上二分」。
二分查找最常见的错误是边界处理，主要由以下选择决定： - 区间是左闭右闭 [left, right] 还是左闭右开 [left, right)？ - 循环条件是 while left <= right 还是 while left < right？ - 找到目标后是否继续缩小范围（用于找左/右边界）？
[left, right]
[left, right)
while left <= right
while left < right
推荐记忆一套统一模板（左闭右开），用它可以解决所有场景。
def binary_search(nums, target): """ 在有序数组 nums 中查找 target，返回其索引，不存在返回 -1 变量说明： nums : 已排序的整数数组（升序），例如 [-1, 0, 3, 5, 9, 12] target : 要查找的目标值，例如 9 left : 当前搜索区间的左边界（闭区间，包含 left 位置） right : 当前搜索区间的右边界（开区间，不包含 right 位置） 使用「左闭右开」区间 [left, right) 的好处： - 初始化 right = len(nums)（不是 len-1），统一空数组情况 - 循环条件 left < right（而非 <=），逻辑更清晰 mid : 区间中点索引，计算时用 left + (right-left)//2 避免整数溢出 """ left = 0 # 左边界，初始为数组起点 right = len(nums) # 右边界，初始为数组长度（左闭右开区间） while left < right: # 区间非空时继续搜索 mid = left + (right - left) // 2 # 计算中点（防溢出写法） if nums[mid] == target: return mid # 找到目标，直接返回索引 elif nums[mid] < target: left = mid + 1 # 目标在右半区，左边界右移（排除 mid） else: right = mid # 目标在左半区，右边界左移到 mid（排除 mid 右侧） return -1 # 未找到
适用场景：在有序数组中找第一个 >= target 的位置（即目标的左边界/插入位置）。
>= target
def left_bound(nums, target): """ 在有序数组 nums 中找第一个值 >= target 的位置（左边界） 例如 nums=[1,2,2,2,3], target=2，返回 1（第一个 2 的位置） 变量说明（同上，使用左闭右开区间）： 当 nums[mid] >= target 时，右边界收缩到 mid（不排除 mid，因为 mid 可能就是答案） 当 nums[mid] < target 时，左边界收缩到 mid+1（排除 mid，它一定不是答案） 最终 left == right，指向第一个 >= target 的位置 如果 target 不在数组中： 返回的是 target 应该插入的位置（LC 35 搜索插入位置） """ left = 0 right = len(nums) # 左闭右开 while left < right: mid = left + (right - left) // 2 if nums[mid] >= target: right = mid # mid 可能是答案，不排除，右边界收缩到 mid else: left = mid + 1 # mid 一定不是答案，左边界跳过 mid # 循环结束时 left == right，即为第一个 >= target 的位置 # 如果数组中所有元素都 < target，则 left = len(nums)（越界，表示不存在） return left
适用场景：求满足某条件的「最小可行答案」（或「最大可行答案」）。关键是能写出 check(mid) 函数，判断给定答案 mid 是否可行。
check(mid)
def min_eating_speed(piles, h): """ 爱吃香蕉的珂珂（LC 875）： 有 n 堆香蕉，piles[i] 表示第 i 堆的数量，珂珂有 h 小时， 每小时选一堆以速度 k 吃，求能在 h 小时内吃完所有香蕉的最小速度 k。 变量说明： piles : 每堆香蕉数量，例如 [3, 6, 7, 11] h : 总时间限制（小时数），例如 8 left : 答案的下界，速度至少为 1（每小时至少吃 1 根） right : 答案的上界，速度最多为 max(piles)（一小时吃完最大的一堆就够了） mid : 当前尝试的速度 关键洞察：答案空间具有单调性！ 速度越大 → 越容易在 h 小时内吃完（check 返回 True） 速度越小 → 越难在 h 小时内吃完（check 返回 False） → 找满足 check(k)=True 的最小 k，即「左边界二分」 """ import math def check(speed): """ 判断以 speed 的速度，能否在 h 小时内吃完所有香蕉 变量说明： speed : 每小时吃香蕉的速度（正整数） total_hours : 按此速度吃完所有香蕉需要的总小时数 每堆需要的时间 = ceil(pile / speed)（向上取整，不足一小时也占一小时） """ total_hours = sum(math.ceil(pile / speed) for pile in piles) return total_hours <= h # 如果所需时间 <= h 小时，则 speed 可行 left = 1 # 最小速度 right = max(piles) # 最大速度（吃最大那堆只需 1 小时就够了） while left < right: # 左闭右开，寻找左边界 mid = left + (right - left) // 2 if check(mid): # mid 速度可行 right = mid # 尝试更小的速度，右边界收缩到 mid else: # mid 速度不可行 left = mid + 1 # 需要更大的速度，左边界跳过 mid return left # 最小可行速度
check
快速排序（Quick Sort） 的核心思想是「分治」：选一个基准值（pivot），将数组分为「小于 pivot」和「大于 pivot」两部分，再对两部分递归排序。平均时间复杂度 O(n log n)，但最坏 O(n²)（输入已有序时）。
归并排序（Merge Sort） 也是分治：将数组对半分，分别排序，再将两个有序子数组合并。时间复杂度稳定 O(n log n)，额外需要 O(n) 空间。
前缀和（Prefix Sum） 是一种预处理技巧：对数组 nums，构建前缀和数组 prefix，其中 prefix[i] 表示 nums[0] 到 nums[i-1] 的累加和（注意：prefix[0] = 0，这样设计可以方便地用 prefix[r+1] - prefix[l] 求任意区间 [l, r] 的和，而不需要每次重新累加，查询时间 O(1)）。
prefix
prefix[i]
nums[0]
nums[i-1]
prefix[0] = 0
prefix[r+1] - prefix[l]
[l, r]
差分数组（Difference Array） 是前缀和的逆操作，专门用于频繁的「区间加减」操作：构建差分数组 diff，对区间 [l, r] 加 val 只需修改 diff[l] += val 和 diff[r+1] -= val 两个位置（O(1)），最后对 diff 求前缀和还原出结果数组。
diff
diff[l] += val
diff[r+1] -= val
def quick_sort(nums, lo, hi): """ 快速排序主函数 变量说明： nums : 待排序数组（原地修改） lo : 当前递归处理的子数组左边界（包含） hi : 当前递归处理的子数组右边界（包含） 递归思路： 1. 对 nums[lo..hi] 进行 partition，将 pivot 放到最终位置 p 2. 递归排序 nums[lo..p-1]（pivot 左边） 3. 递归排序 nums[p+1..hi]（pivot 右边） """ if lo >= hi: # 子数组长度为 0 或 1，已有序，递归终止 return pivot_idx = partition(nums, lo, hi) # 获取 pivot 的最终位置 quick_sort(nums, lo, pivot_idx - 1) # 递归排序左半部分 quick_sort(nums, pivot_idx + 1, hi) # 递归排序右半部分 def partition(nums, lo, hi): """ 分区函数：选 nums[hi] 为 pivot，将数组分为 <= pivot 和 > pivot 两部分 返回 pivot 最终所在的位置索引 变量说明： pivot : 基准值，选取 nums[hi]（选最后一个元素，简单常用） i : 指向「小于等于 pivot 区域」的末尾，初始为 lo 含义：nums[lo..i-1] 都是 <= pivot 的元素 j : 遍历指针，从 lo 到 hi-1 扫描每个元素 过程示意（nums=[3,6,8,10,1,2,1], lo=0, hi=6, pivot=1）： j=0: nums[0]=3 > 1，不交换，i=0 j=1: nums[1]=6 > 1，不交换，i=0 ... j=4: nums[4]=1 <= 1，交换 nums[0]和nums[4]，i=1 j=5: nums[5]=2 > 1，不交换，i=1 最后：交换 nums[i]=nums[1] 和 pivot=nums[6] 结果：[1, 6, 8, 10, 3, 2, 3]（实际会继续） """ pivot = nums[hi] # 选最后一个元素作为基准值 i = lo # i 指向下一个应该放「小于等于 pivot」元素的位置 for j in range(lo, hi): # j 扫描从 lo 到 hi-1 的所有元素 if nums[j] <= pivot: # 当前元素 <= pivot，应该放到左半部分 nums[i], nums[j] = nums[j], nums[i] # 交换到 i 位置 i += 1 # i 向右推进 # 将 pivot 放到最终位置（i 就是 pivot 应该在的位置） nums[i], nums[hi] = nums[hi], nums[i] return i # 返回 pivot 的最终位置
def prefix_sum_query(nums, queries): """ 利用前缀和实现区间求和查询 变量说明： nums : 原始数组，例如 [1, 2, 3, 4, 5] queries : 查询列表，每个查询 [l, r] 表示求 nums[l..r] 的和（0-indexed） n : 数组长度 prefix : 前缀和数组，长度为 n+1 prefix[0] = 0（边界哨兵，简化计算） prefix[i] = nums[0] + nums[1] + ... + nums[i-1] 即 prefix[i] 是前 i 个元素的累加和（不包含 nums[i]） 核心公式：nums[l..r] 的和 = prefix[r+1] - prefix[l] 证明：prefix[r+1] = nums[0]+...+nums[r] prefix[l] = nums[0]+...+nums[l-1] 相减得 nums[l]+...+nums[r] ✓ 以 nums=[1,2,3,4,5] 为例： prefix = [0, 1, 3, 6, 10, 15] 查询 [1,3]（nums[1]+nums[2]+nums[3]=2+3+4=9）： prefix[4] - prefix[1] = 10 - 1 = 9 ✓ """ n = len(nums) prefix = [0] * (n + 1) # 多一个位置存 prefix[0]=0 # 构建前缀和数组（预处理，O(n)） for i in range(n): prefix[i + 1] = prefix[i] + nums[i] # prefix[i+1] = 前 i+1 个元素之和 # 处理查询（每次查询 O(1)） results = [] for l, r in queries: range_sum = prefix[r + 1] - prefix[l] # 区间 [l, r] 的和 results.append(range_sum) return results
🔄 第一周复盘（今天下午）：把第 1–6 天中做错或看了答案的题目重新计时做一遍，不看任何提示。
回溯（Backtracking） 是一种系统性的枚举算法，本质是暴力搜索 + 剪枝。
把所有可能的选择想象成一棵「决策树」，回溯算法通过 DFS 遍历这棵树：在每个节点处「做选择」（进入某条路径），如果发现这条路径不可能产生合法答案，就「撤销选择」（剪枝，回到上一层），再尝试其他分支。
回溯与递归的区别：递归只关心「从这个节点能得到什么答案」，回溯还需要在递归返回后恢复现场（撤销刚才做的选择），以便探索其他路径。
回溯的三要素： 1. 路径（path）：已经做出的选择序列，代表决策树中从根到当前节点的路径。 2. 选择列表（choices）：当前节点可以做的选择。 3. 终止条件：到达决策树叶节点的条件，此时记录结果。
剪枝是回溯效率的关键：在进入递归前，如果能提前判断这条路径不可能产生合法答案，就 continue 跳过，避免无效搜索。
continue
result = [] # 存储所有满足条件的结果 def backtrack(path, start_or_used): """ 通用回溯框架 变量说明： path : 当前路径（已选择的元素列表），表示决策树中从根到当前位置的选择 start : 用于组合/子集问题，表示下次选择从哪个下标开始（避免重复选同一对） used : 用于排列问题，布尔数组，used[i]=True 表示 nums[i] 已在路径中 result : 全局结果列表，满足条件时将 path 的拷贝加入 """ # ① 终止条件：路径满足要求时，记录结果并返回 if 终止条件: result.append(path[:]) # 注意：必须用 path[:] 或 list(path) 拷贝， # 因为 path 是引用，后续修改会影响已记录的结果！ return # ② 遍历当前层的所有选择 for 选择 in 选择列表: if 不满足条件（剪枝）: # 提前排除不可能的选择 continue path.append(选择) # 做选择：将当前元素加入路径 backtrack(path, 下一层参数) # 递归：进入下一层决策 path.pop() # 撤销选择：恢复现场（回溯的关键！）
核心逻辑：对每个元素，决策是「选」还是「不选」。用 start 控制从哪个下标开始选，确保不重复（每次只从当前元素之后选，不回头）。
start
def subsets(nums): """ 求数组 nums 的所有子集（LC 78） 例如 nums=[1,2,3]，结果包含 [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3] 变量说明： nums : 输入数组（无重复元素） result : 存储所有子集 path : 当前子集（当前路径） start : 下次选择从 nums[start] 开始，防止重复 （如果选了 nums[1]，下次只能从 nums[2] 起选，不能再选 nums[0]） """ result = [] def backtrack(path, start): result.append(list(path)) # 每次进入函数都记录当前路径作为一个子集（包括空集） for i in range(start, len(nums)): # 从 start 开始，避免重复选取之前的元素 path.append(nums[i]) # 选择 nums[i] backtrack(path, i + 1) # 递归：下次从 i+1 开始选（不能重选 nums[i]） path.pop() # 撤销选择 backtrack([], 0) # 初始路径为空，从索引 0 开始选 return result
核心逻辑：排列中顺序有关，不能用 start 限制，改用 used 数组标记哪些元素已在当前路径中。去重时先排序，跳过「同层相邻重复元素」。
used
def permute_unique(nums): """ 含重复元素的全排列（LC 47） 例如 nums=[1,1,2]，结果为 [[1,1,2],[1,2,1],[2,1,1]]（去掉重复排列） 变量说明： nums : 可能含重复元素的数组，排序后便于去重 result : 存储所有不重复的全排列 path : 当前排列 used : 布尔数组，used[i]=True 表示 nums[i] 已出现在当前 path 中 去重关键： 对于相邻的相同元素 nums[i-1] == nums[i]： 如果 used[i-1] == False，说明 nums[i-1] 在本层决策中已被跳过（被撤销了）， 现在选 nums[i] 和之前选 nums[i-1] 会产生重复排列，所以跳过 nums[i]。 用 not used[i-1] 来判断：i-1 已被用过（used[i-1]=True）时， nums[i-1] 在路径更上层，nums[i] 在当前层，这是合法的不同排列； i-1 未被用（used[i-1]=False），说明是同层的重复，跳过。 """ nums.sort() # 排序，使相同元素相邻，方便去重 result = [] used = [False] * len(nums) # used[i] 表示 nums[i] 是否已在当前路径中 def backtrack(path): if len(path) == len(nums): # 路径长度等于数组长度，得到一个完整排列 result.append(list(path)) return for i in range(len(nums)): if used[i]: # nums[i] 已在当前路径中，跳过 continue # 去重剪枝：相邻相同元素，如果前一个未被使用（已在本层被撤销），跳过当前 if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]: continue used[i] = True # 标记 nums[i] 已使用 path.append(nums[i]) # 做选择 backtrack(path) # 递归进入下一层 path.pop() # 撤销选择 used[i] = False # 取消标记 backtrack([]) return result
nums[i]==nums[i-1] and not used[i-1]
动态规划（Dynamic Programming，DP） 是解决「具有重叠子问题和最优子结构」的优化问题的算法思想。
两个核心概念： - 重叠子问题：同一个子问题会被重复计算多次（如斐波那契数列中 fib(3) 会被多次调用）。DP 通过「记忆化」（将子问题结果存入数组）避免重复计算。 - 最优子结构：问题的最优解包含子问题的最优解（如「最长递增子序列」中，以 nums[i] 结尾的 LIS 依赖以 nums[j] 结尾的 LIS，其中 j < i）。
DP 解题四步法： 1. 定义状态：dp[i] 表示什么？这是最关键的一步，定义清楚了后面自然推导。 2. 写出转移方程：dp[i] 如何由更小规模的子问题（dp[0..i-1]）推导？ 3. 确定初始值（base case）：最小子问题的答案是什么？ 4. 确定遍历顺序：确保计算 dp[i] 时，它依赖的子问题已经计算完毕。
dp[i]
dp[0..i-1]
def climb_stairs(n): """ 爬楼梯：每次可以爬 1 或 2 步，到达第 n 阶有多少种方法（LC 70） 状态定义： dp[i] = 爬到第 i 阶楼梯的方法总数 转移方程： 到达第 i 阶，最后一步要么从第 i-1 阶迈一步，要么从第 i-2 阶迈两步。 因此 dp[i] = dp[i-1] + dp[i-2] 初始值（base case）： dp[0] = 1（站在地面，算 1 种方法——什么都不做） dp[1] = 1（到达第 1 阶只有 1 种方法：迈一步） 变量说明： n : 楼梯阶数（n >= 1） dp : dp[i] = 爬到第 i 阶的方法数，长度为 n+1 """ if n <= 1: return 1 dp = [0] * (n + 1) # 初始化 dp 数组，dp[0..n] 共 n+1 个位置 dp[0] = 1 # base case：地面（第 0 阶）有 1 种方法 dp[1] = 1 # base case：第 1 阶有 1 种方法 for i in range(2, n + 1): # 从第 2 阶开始，逐步推导 dp[i] = dp[i - 1] + dp[i - 2] # 转移方程 return dp[n] # 返回到达第 n 阶的方法数
def length_of_lis(nums): """ 最长递增子序列的长度（LC 300） 例如 nums=[10,9,2,5,3,7,101,18]，最长递增子序列为 [2,3,7,101]，长度为 4 状态定义： dp[i] = 以 nums[i] 为结尾的最长递增子序列的长度 注意：必须包含 nums[i]，不能跳过它 转移方程： 对于每个 j < i，如果 nums[j] < nums[i]（可以接在 nums[j] 后面）， 则 dp[i] = max(dp[i], dp[j] + 1) 含义：以 nums[i] 结尾的 LIS，可以在以 nums[j] 结尾的 LIS 后面追加 nums[i] 初始值： dp[i] = 1（每个元素本身就是长度为 1 的递增子序列） 变量说明： nums : 整数数组，例如 [10, 9, 2, 5, 3, 7, 101, 18] n : 数组长度 dp : dp[i] = 以 nums[i] 结尾的最长递增子序列长度，初始全为 1 过程示意（nums=[2,5,3,7]）： dp=[1,1,1,1]（初始） i=1(5)：j=0(2), 2<5，dp[1]=max(1,dp[0]+1)=2 i=2(3)：j=0(2), 2<3，dp[2]=max(1,dp[0]+1)=2；j=1(5), 5>3，跳过 i=3(7)：j=0(2), dp[3]=2；j=1(5), dp[3]=3；j=2(3), dp[3]=3 dp=[1,2,2,3]，max(dp)=3 """ n = len(nums) dp = [1] * n # 初始化：每个元素本身构成长度为 1 的递增子序列 for i in range(n): # 外层：枚举以 nums[i] 结尾的 LIS for j in range(i): # 内层：枚举 nums[i] 前面的每个元素 nums[j] if nums[j] < nums[i]: # nums[j] 可以接在 nums[i] 前面（严格递增） dp[i] = max(dp[i], dp[j] + 1) # 更新 dp[i] return max(dp) # 所有「以 nums[i] 结尾的 LIS 长度」中取最大值
def rob(nums): """ 打家劫舍：不能偷相邻的房子，求最大偷取金额（LC 198） 状态定义： dp[i] = 偷前 i 间房子（nums[0..i-1]）所能获得的最大金额 转移方程： 对第 i 间房子（nums[i-1]），有两种选择： ① 不偷第 i 间：dp[i] = dp[i-1]（和前 i-1 间的最优解相同） ② 偷第 i 间：dp[i] = dp[i-2] + nums[i-1]（上一次偷在第 i-2 间之前，加上本次） 取两者最大：dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]) 初始值： dp[0] = 0（0 间房子，收益为 0） dp[1] = nums[0]（只有 1 间房子，全偷） 变量说明： nums : 每间房子的金额，例如 [2, 7, 9, 3, 1] n : 房子数量 dp : dp[i] = 偷前 i 间房子的最大收益，长度为 n+1 """ n = len(nums) if n == 0: return 0 if n == 1: return nums[0] dp = [0] * (n + 1) # dp[0..n] dp[0] = 0 # base case：0 间房子，收益 0 dp[1] = nums[0] # base case：只有 1 间房子，偷它 for i in range(2, n + 1): # 从第 2 间开始 dp[i] = max(dp[i - 1], # ① 不偷第 i 间 dp[i - 2] + nums[i - 1]) # ② 偷第 i 间 return dp[n]
def min_path_sum(grid): """ 网格中从左上角到右下角的最小路径和（LC 64），只能向右或向下移动 状态定义： dp[i][j] = 从 grid[0][0] 走到 grid[i][j] 的最小路径和 转移方程： dp[i][j] 只能从上方 dp[i-1][j] 或左方 dp[i][j-1] 走来，取较小的： dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] 初始值（边界情况）： 第一行：只能从左侧到达，dp[0][j] = dp[0][j-1] + grid[0][j] 第一列：只能从上方到达，dp[i][0] = dp[i-1][0] + grid[i][0] 起点：dp[0][0] = grid[0][0] 变量说明： grid : m 行 n 列的二维数组，grid[i][j] 为该格子的代价 m, n : 行数和列数 dp : m×n 的二维 DP 数组 """ m = len(grid) # 行数 n = len(grid[0]) # 列数 # 初始化 dp 数组（二维列表，全为 0） dp = [[0] * n for _ in range(m)] dp[0][0] = grid[0][0] # 起点 # 初始化第一行（只能从左向右） for j in range(1, n): dp[0][j] = dp[0][j - 1] + grid[0][j] # 初始化第一列（只能从上向下） for i in range(1, m): dp[i][0] = dp[i - 1][0] + grid[i][0] # 填充剩余格子 for i in range(1, m): for j in range(1, n): # 从上方来 vs 从左方来，取代价较小的路径 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j] return dp[m - 1][n - 1] # 右下角即为答案
def min_distance(word1, word2): """ 编辑距离：将 word1 转换为 word2 所需的最少操作次数（LC 72） 操作：插入一个字符 / 删除一个字符 / 替换一个字符 例如 word1="horse", word2="ros"，最少需要 3 次操作 状态定义： dp[i][j] = 将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数 转移方程： 设 word1[i-1] 和 word2[j-1] 分别是当前两个字符（1-indexed 转 0-indexed）： ① 若 word1[i-1] == word2[j-1]：字符相同，无需操作，dp[i][j] = dp[i-1][j-1] ② 若 word1[i-1] != word2[j-1]：取以下三种操作的最小值 + 1： - 替换：dp[i-1][j-1] + 1（将 word1[i-1] 替换为 word2[j-1]） - 删除 word1[i-1]：dp[i-1][j] + 1（相当于 word1 少了一个字符） - 插入 word2[j-1]：dp[i][j-1] + 1（相当于 word2 多了一个字符） 初始值（边界情况）： dp[i][0] = i：word1 的前 i 个字符转换为空串，需要删除 i 次 dp[0][j] = j：空串转换为 word2 的前 j 个字符，需要插入 j 次 变量说明： word1, word2 : 两个字符串，例如 "horse", "ros" m, n : word1 和 word2 的长度 dp : (m+1)×(n+1) 的 DP 数组（+1 是为了处理空串的边界情况） """ m = len(word1) # word1 的长度 n = len(word2) # word2 的长度 # 初始化 dp，大小为 (m+1)×(n+1) dp = [[0] * (n + 1) for _ in range(m + 1)] # 初始化边界 for i in range(m + 1): dp[i][0] = i # word1 前 i 个字符 → 空串，需要 i 次删除 for j in range(n + 1): dp[0][j] = j # 空串 → word2 前 j 个字符，需要 j 次插入 # 填充 dp 表 for i in range(1, m + 1): for j in range(1, n + 1): if word1[i - 1] == word2[j - 1]: # 当前两字符相同，无需额外操作 dp[i][j] = dp[i - 1][j - 1] else: # 当前两字符不同，取三种操作的最小值 dp[i][j] = 1 + min( dp[i - 1][j - 1], # 替换操作 dp[i - 1][j], # 删除 word1[i-1] dp[i][j - 1] # 插入 word2[j-1] ) return dp[m][n]
💡 今日重点：编辑距离是字节/腾讯/阿里高频，状态定义和三种转移方向必须熟记。
背包问题是 DP 的经典模型，描述的是：有一个容量为 W 的背包，和若干物品（每件有重量和价值），如何选取物品放入背包使总价值最大。
0-1 背包：每件物品只能选 0 次或 1 次（要么不拿，要么拿一个）。
完全背包：每件物品可以选无限次（可以重复拿同一件）。
两者的区别在于遍历容量的顺序： - 0-1 背包：容量倒序遍历（从大到小）。原因：每件物品只能用一次，倒序遍历能确保计算 dp[j] 时，dp[j-weight] 还是「没用过当前物品」的状态，防止同一件物品被重复选取。 - 完全背包：容量正序遍历（从小到大）。原因：物品可以重复使用，正序遍历允许 dp[j-weight] 包含当前物品（即重复使用）。
dp[j]
dp[j-weight]
def knapsack_01(weights, values, capacity): """ 0-1 背包：每件物品只能选一次，求最大价值 状态定义： dp[j] = 背包容量为 j 时，能获得的最大价值（一维滚动数组优化） 转移方程： dp[j] = max(dp[j], # 不选当前物品 dp[j-w] + v) # 选当前物品（重量 w，价值 v） 关键：容量 j 必须倒序遍历（从 capacity 到 w）， 确保每件物品只被选一次（若正序，dp[j-w] 可能已经包含了当前物品） 变量说明： weights : 每件物品的重量列表，例如 [2, 3, 4] values : 每件物品的价值列表，例如 [3, 4, 5] capacity : 背包容量上限，例如 5 dp : dp[j] = 容量为 j 时的最大价值，长度为 capacity+1，初始全为 0 """ dp = [0] * (capacity + 1) # dp[0..capacity]，dp[0]=0（容量为 0，价值为 0） for w, v in zip(weights, values): # 遍历每件物品（重量 w，价值 v） for j in range(capacity, w - 1, -1): # 容量倒序遍历（从 capacity 降到 w） # j >= w 才能放入当前物品（容量足够） dp[j] = max(dp[j], # 不放当前物品：保持原有价值 dp[j - w] + v) # 放当前物品：空出 w 容量，加上当前价值 v return dp[capacity] # 最终答案：容量为 capacity 时的最大价值
def coin_change(coins, amount): """ 零钱兑换：用面值为 coins 的硬币凑成 amount，求最少硬币数（LC 322） 每种硬币可以用无限次（完全背包） 状态定义： dp[j] = 凑成金额 j 所需的最少硬币数 转移方程： dp[j] = min(dp[j], dp[j - coin] + 1) 含义：用一枚面值为 coin 的硬币，加上「凑成 j-coin 所需的最少硬币数」 初始值： dp[0] = 0（凑成金额 0 不需要任何硬币） dp[j] = 正无穷（初始表示凑不成，若遍历后仍为正无穷则无解） 关键：容量（金额）正序遍历，允许同一枚硬币被重复使用 变量说明： coins : 硬币面值列表，例如 [1, 5, 10, 25] amount : 目标金额，例如 11 dp : dp[j] = 凑成金额 j 的最少硬币数，初始 dp[0]=0，其余为正无穷 """ dp = [float('inf')] * (amount + 1) # 初始化为正无穷（表示暂时凑不成） dp[0] = 0 # base case：凑成 0 元需要 0 枚硬币 for coin in coins: # 遍历每种硬币面值 for j in range(coin, amount + 1): # 正序遍历金额（完全背包） if dp[j - coin] != float('inf'): # 确保 j-coin 是可达状态（能凑成） dp[j] = min(dp[j], # 不使用当前硬币 dp[j - coin] + 1) # 使用一枚当前硬币 # 如果 dp[amount] 仍为正无穷，说明凑不成，返回 -1 return dp[amount] if dp[amount] != float('inf') else -1
堆（Heap） 是一种完全二叉树，分为最小堆（父节点 ≤ 子节点，堆顶是最小值）和最大堆（父节点 ≥ 子节点，堆顶是最大值）。支持 O(log n) 的插入和删除，O(1) 获取最值。Python 的 heapq 模块实现的是最小堆，若需要最大堆，将所有值取负（存 -val）即可实现。
heapq
-val
堆的典型用途：动态维护「前 K 大/小」元素，或多路归并（如合并 K 个有序链表）。
图（Graph） 由节点（顶点）和边组成。在算法题中，图通常用邻接表表示：graph[u] 存储节点 u 的所有邻居节点。
graph[u]
拓扑排序（Topological Sort） 只适用于有向无环图（DAG），将节点排成一个线性序列，使得每条有向边 u→v 中，u 都在 v 之前。典型应用：课程先修关系、任务依赖关系。
Kahn 算法（BFS 版拓扑排序）： 1. 计算所有节点的入度（有多少条边指向它） 2. 将所有入度为 0 的节点加入队列（没有先修课的课程） 3. 每次从队列取出一个节点，将其所有邻居的入度 -1，若邻居入度变为 0，则加入队列 4. 若最终处理的节点数 = 总节点数，则图无环；否则有环（存在循环依赖）
import heapq def heap_operations_demo(nums, k): """ 堆的常用操作演示：求数组中前 K 个最大元素 策略：维护一个大小为 K 的最小堆 堆内始终保存当前遇到的最大的 K 个元素。 遍历数组时：若当前元素 > 堆顶（最小的），则弹出堆顶，将当前元素入堆。 最终堆内的 K 个元素就是最大的 K 个。 变量说明： nums : 整数数组 k : 要找的前 K 个最大值 min_heap: 最小堆（Python heapq 默认就是最小堆） 始终保持 k 个元素，堆顶是这 k 个元素中最小的 """ min_heap = [] # 初始空堆 for num in nums: heapq.heappush(min_heap, num) # 将元素入堆，自动维护堆结构，O(log n) if len(min_heap) > k: # 堆内元素超过 k 个 heapq.heappop(min_heap) # 弹出堆顶（当前 k+1 个元素中最小的） # 堆内剩余的 k 个元素就是最大的 k 个 return sorted(min_heap, reverse=True) # 返回降序排列的前 K 大元素 # 最大堆：存负值 def max_heap_demo(nums): """ Python 没有内置最大堆，用「存负值」来模拟： 将 val 取反后入堆，弹出时再取反还原 """ max_heap = [] for num in nums: heapq.heappush(max_heap, -num) # 存负值，相当于按最大堆排序 max_val = -heapq.heappop(max_heap) # 弹出最小负值，取反得最大正值 return max_val
from collections import deque, defaultdict def topological_sort(n, edges): """ 拓扑排序（Kahn 算法，BFS 版） 变量说明： n : 节点数量（节点编号 0 到 n-1） edges : 有向边列表，每条边 [u, v] 表示 u 必须在 v 之前（u → v） 例如 [[1,0],[2,0]] 表示 1→0，2→0 graph : 邻接表，graph[u] 存储 u 能到达的所有节点 in_degree : 入度数组，in_degree[v] = 有多少条边指向 v queue : BFS 队列，初始存入所有入度为 0 的节点 order : 拓扑排序结果（节点的合法线性排列） 核心思路： 入度为 0 的节点没有前驱依赖，可以最先处理。 每处理一个节点，相当于「去掉」它和它出发的所有边， 其邻居的入度 -1，若某邻居入度变为 0，说明它的所有依赖都已处理，可以入队。 """ graph = defaultdict(list) # 邻接表：graph[u] = [u 能到达的节点列表] in_degree = [0] * n # 入度数组，初始全为 0 for u, v in edges: graph[u].append(v) # 建立有向边 u → v in_degree[v] += 1 # v 的入度 +1 # 将所有入度为 0 的节点加入初始队列（这些节点没有任何先修依赖） queue = deque([i for i in range(n) if in_degree[i] == 0]) order = [] # 存储拓扑排序结果 while queue: node = queue.popleft() # 取出一个入度为 0 的节点 order.append(node) # 加入排序结果 for neighbor in graph[node]: # 遍历该节点的所有后继节点 in_degree[neighbor] -= 1 # 后继节点入度 -1（去掉 node→neighbor 这条边） if in_degree[neighbor] == 0: # 后继节点入度变为 0，可以处理了 queue.append(neighbor) # 若 order 长度等于节点总数，说明所有节点都被处理了（图无环） # 否则说明图中有环（存在循环依赖），无法完成拓扑排序 if len(order) == n: return order # 合法的拓扑排序结果 else: return [] # 有环，无法拓扑排序
并查集（Union-Find / Disjoint Set Union） 是一种专门处理「元素分组与合并」问题的数据结构，支持两种核心操作： - find(x)：找到 x 所在集合的「代表元素」（根节点）。路径压缩优化后近似 O(1)。 - union(x, y)：将 x 和 y 所在的两个集合合并为一个集合。
find(x)
union(x, y)
直觉理解：每个集合是一棵树，树的根节点是这个集合的「代表」。find 就是找到 x 的根节点；union 就是把两棵树合并（一棵的根指向另一棵的根）。「路径压缩」优化：在 find 过程中，把路径上的所有节点直接连到根节点，大幅减少后续查找的层数。
find
union
Trie（前缀树/字典树） 是一种专门用于字符串前缀匹配的树形数据结构。每个节点代表一个字符，从根到某个节点的路径表示一个字符串前缀。节点包含：children（子节点字典，key=字符，value=下一个 Trie 节点）和 is_end（布尔值，标记该节点是否是某个完整单词的结尾）。
children
is_end
class UnionFind: """ 并查集（Union-Find）完整实现 支持路径压缩（Path Compression）+ 按秩合并（Union by Rank） 路径压缩：find 时将路径上所有节点直接连到根节点，减少树高 按秩合并：rank 记录树的大概高度，将矮树接到高树下，避免树退化成链表 变量说明（__init__）： n : 初始有 n 个独立集合（节点编号 0 到 n-1） parent : parent[i] = i 的父节点编号 初始时每个节点的父节点是自己（自己是自己所在集合的根） rank : rank[i] = 以 i 为根的树的「秩」（大概高度），初始为 0 count : 当前集合的个数，初始为 n """ def __init__(self, n): self.parent = list(range(n)) # 初始：每个节点的父节点是自己（各自独立） self.rank = [0] * n # 初始：所有节点的秩为 0 self.count = n # 初始：n 个独立集合 def find(self, x): """ 找到 x 所在集合的根节点（代表元素） 路径压缩：递归过程中，将路径上所有节点直接指向根节点 例如：初始树为 1 → 2 → 3（根） find(1) 过程中：1 的父节点变为 3，2 的父节点变为 3 压缩后：1 → 3，2 → 3（树高从 2 变为 1） """ if self.parent[x] != x: # x 不是根节点 self.parent[x] = self.find(self.parent[x]) # 递归找根，并路径压缩 return self.parent[x] # 返回根节点 def union(self, x, y): """ 合并 x 和 y 所在的两个集合 按秩合并：将秩小的树接到秩大的树下，避免树太高 返回值： True = 成功合并（x 和 y 原来不在同一集合） False = 无需合并（x 和 y 已在同一集合） """ px = self.find(x) # x 所在集合的根 py = self.find(y) # y 所在集合的根 if px == py: # 已在同一集合，无需合并 return False # 按秩合并：将秩小的树接到秩大的树下 if self.rank[px] < self.rank[py]: px, py = py, px # 确保 px 的秩 >= py 的秩 self.parent[py] = px # 将 py 接到 px 下（矮树接到高树） if self.rank[px] == self.rank[py]: # 两树秩相等时，合并后秩 +1 self.rank[px] += 1 self.count -= 1 # 集合数 -1 return True def connected(self, x, y): """判断 x 和 y 是否在同一集合""" return self.find(x) == self.find(y)
class TrieNode: """ Trie 节点 变量说明： children : 字典，key = 字符（如 'a'~'z'），value = 对应的子 TrieNode 只有实际出现过的字符才会有对应的子节点（节省空间） is_end : 布尔值，标记从根到该节点的路径是否构成一个完整的单词 """ def __init__(self): self.children = {} # 子节点字典（稀疏存储，节省空间） self.is_end = False # 该节点是否是某个完整单词的结尾 class Trie: """ 前缀树（Trie）完整实现（LC 208） 结构示意（插入 "cat", "car", "dog" 后）： root ├── c │ └── a │ ├── t (is_end=True) ← "cat" │ └── r (is_end=True) ← "car" └── d └── o └── g (is_end=True) ← "dog" """ def __init__(self): self.root = TrieNode() # 根节点（不代表任何字符，只是入口） def insert(self, word): """ 向 Trie 中插入单词 word 过程：从根节点出发，对 word 的每个字符： 若对应子节点不存在，创建新节点； 移动到子节点； 最后标记末尾节点的 is_end = True 变量说明： word : 要插入的字符串，例如 "apple" node : 当前访问的 Trie 节点，从 root 出发逐层向下 ch : word 中当前处理的字符 """ node = self.root # 从根节点出发 for ch in word: # 遍历单词的每个字符 if ch not in node.children: # 当前字符在子节点中不存在 node.children[ch] = TrieNode() # 创建新的子节点 node = node.children[ch] # 移动到子节点 node.is_end = True # 标记该节点为某个完整单词的结尾 def search(self, word): """ 查询 word 是否完整存在于 Trie 中（必须是完整单词，不只是前缀） 变量说明： word : 要查询的字符串 node : 当前节点 返回 True 当且仅当：word 的所有字符都能在 Trie 中匹配，且末尾节点 is_end=True """ node = self.root for ch in word: if ch not in node.children: # 某个字符不存在，word 不在 Trie 中 return False node = node.children[ch] return node.is_end # 必须是完整单词结尾（is_end=True）才算找到 def starts_with(self, prefix): """ 查询是否存在以 prefix 开头的单词（只需匹配前缀，不要求 is_end） 返回 True 当且仅当：prefix 的所有字符都能在 Trie 中匹配 """ node = self.root for ch in prefix: if ch not in node.children: # 前缀某字符不存在 return False node = node.children[ch] return True # 前缀完整匹配（不要求 is_end）
模拟真实笔试环境，严格计时，检验两周训练成果。
上午（120 分钟，模拟真实笔试）：
从以下题目中随机选 3 道，不看提示，独立完成：
下午（90 分钟，定向复盘）： - 找出两周内最薄弱的 2 个题型，重做该题型最后一道 Hard 题 - 整理个人「解题模板速查卡」（一页纸，面试前翻看）
# ===== 常用导入 ===== from collections import defaultdict, Counter, deque from heapq import heappush, heappop, heapify import bisect # 二分插入：bisect.bisect_left(arr, x) # ===== 特殊值 ===== float('inf') # 正无穷（用于初始化最小值比较） float('-inf') # 负无穷（用于初始化最大值比较） # ===== 字符操作 ===== ord('a') # 字符转 ASCII：97 chr(97) # ASCII 转字符：'a' ''.join(sorted("eat")) # 字符串排序：'aet' # ===== 列表拷贝（回溯中必须用拷贝！）===== result.append(path[:]) # 浅拷贝（等价于 list(path)） # ===== 矩阵四方向移动 ===== dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 右、左、下、上 for dx, dy in dirs: nx, ny = x + dx, y + dy if 0 <= nx < m and 0 <= ny < n: # 边界检查 # 处理 (nx, ny) # ===== 排序技巧 ===== nums.sort(key=lambda x: -x) # 降序排序 intervals.sort(key=lambda x: x[0]) # 按区间左端点排序 items.sort(key=lambda x: (x[0], -x[1])) # 多关键字排序 # ===== 二维 DP 初始化 ===== dp = [[0] * n for _ in range(m)] # m×n 的全 0 二维列表（不能用 [[0]*n]*m！） # ===== Counter 常用操作 ===== count = Counter("aabbc") # Counter({'a':2,'b':2,'c':1}) count.most_common(2) # 出现频次最高的 2 个：[('a',2),('b',2)]
🎯 终极目标：两周后能做到「看到题目 → 30秒内识别题型 → 调用模板写代码 → 自信讲解思路」，这才是面试竞争力的核心。
计划制定 | 适用平台：LeetCode · 牛客网 · 剑指Offer
还没有评论，来抢沙发吧！
博客管理员
40 篇文章
admin
还没有评论，来抢沙发吧！