专为 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 篇文章
还没有评论,来抢沙发吧!