Interview Practice · Python 3
100 道题、17 个模式类别。先学每类为何能缩小搜索，再看同一思路怎样适应不同约束。每题都给出题意、推导、具体步骤、可实现的 Python 代码、复杂度与失败边界。
这一节从零约定本书的语言。先看数组 [2,7,11]：它有3个元素，下标从0开始，nums[0] 是2、nums[1] 是7。问题说“返回下标”，答案便是0和1；说“返回数值”，才是2和7。下标是位置，值是位置里装的内容，两者不能混用。
total = 0 是把变量total设为0，total += 2 等同于 total = total + 2。if x > 0: 后缩进的代码只在条件成立时执行；== 判断相等，单个 = 则是赋值。and 要求两条件都真，or 要求至少一个真，not 取反。
nums = [2, 7, 11]
total = 0
for i, x in enumerate(nums):
total += x
# 三轮分别是 (i,x,total)=(0,2,2)、(1,7,9)、(2,11,20)enumerate 同时给下标i和元素x；range(1,4) 依次给1、2、3，右端4不包含。while 条件: 只要条件仍真就重复，因此循环体必须让状态朝结束方向改变。break 退出当前循环，continue 跳过本轮剩余代码，return 则立即结束整个函数并交回答案。a,b=b,a+b 的右边先用旧值计算，再同时赋值，不会先改a再算b。
列表 list 是有顺序的一排元素，a=[3,1,3] 保留两个3。a.append(5) 尾部追加，a.pop() 删除并返回末项；len(a) 求长度。a[l:r] 复制下标l到r之前的元素，故 a[0:2] 得到 [3,1]，复制多少项就花多少时间和空间。写成区间[l,r)同样表示含左端l、不含右端r，称“半开区间”；[l,r]则两端都含。sorted(a) 返回新排序列表，a.sort() 则修改原列表。
字典 dict 是“键→值”的查询表。seen={2:0,7:1} 表示值2曾在下标0、值7曾在下标1；seen[7] 得1，7 in seen 判断是否有键7，seen.get(11,0) 在键不存在时给默认0。这种默认值常用于计数：count[x]=count.get(x,0)+1。键必须能稳定散列，列表不能直接作键，可改用不允许修改的 tuple（元组）。
集合 set 只回答“在不在”，不记录重复次数。set([3,1,3]) 只有1和3两个成员；add 加成员、remove 删成员。哈希指把键计算成存储位置的办法，字典与集合借它跳到少量候选处，所以平均查询近似一步；若只用列表逐项找，则可能检查整排。需要“出现几次”用字典，需要“出现过没有”才用集合。
字符串可像列表一样按下标读取或切片，但不能执行 s[0]='a' 原地改字符。''.join(parts) 把若干字符串连接起来；ord('a') 为97，所以小写字母c用 ord(c)-97 映射到0至25的计数槽位。Counter 是标准库提供的计数字典，未出现的键读取为0；bisect_left 用二分找第一个大于等于目标的位置；heapq 提供堆，含义在堆章节说明。from collections import Counter 是取用库中已有工具，不是本题另藏一段推导。
列表推导 [x*2 for x in [1,3]] 是“对每项算一次再收集”，得 [2,6]；[0]*3 得三个0。二维表用 [[0]*3 for _ in range(2)] 新建两行，变量 _ 表示本轮序号用不上；不要写 [[0]*3]*2，后者让两行指向同一列表，改第一行会连第二行一起改。a[-1] 读末项；某下标可能是-1时要先判断边界，不能误把不存在的前驱当末项。
列表变量指向一个对象：a=[1,2]; b=a 后两变量指向同一列表，改 b[0]=9 会让a也变成 [9,2]；b=a.copy() 才新建外层列表。回溯记录答案用 path.copy()，是为了留下当前内容，而非一直指向正在变化的同一条path。
链表是一串结点对象，每个有 val 存数、next 指向下一个，末尾指向 None（没有对象）。对 1→2→3，变量cur若指着2，则 cur.next 指着3；把 cur.next=None 会断开通往3的链接。反转前先用nxt保存原后继，就不会找不到剩余链。a is b 问是否同一对象；两个分别新建的值8结点并不相交。
树把每个结点的后继改为 left 与 right 两个孩子；root是起点“根”，没有孩子的结点叫叶结点。parent是某结点的直接上层，祖先则包括更远上层。子树是某结点连同其所有后代。BST指二叉搜索树：左子树所有值比根小，右子树所有值比根大，后面的验证题会解释为何仅比较直接孩子还不够。
class 定义一类对象，把一份数据与操作它的函数放在一起。cache = LRUCache(2) 建立一个容量2的实例，初始化函数 __init__ 会运行；self.data 表示“这一个缓存自己的data”，另一个缓存有另一份。cache.get(1) 调用方法时，Python自动把cache作为self传进去；普通函数不用self。node.next 同样只是读取这个对象里名为next的字段。
def f(x): 定义函数，参数是本次输入，return y 把结果交给调用者。递归是函数把更小的同类问题交给自己，例如树高 height(node)=1+max(height(left),height(right))。到空结点时必须返回0，这个不再继续调用的条件叫“递归出口”。执行父结点时，程序会先等孩子返回，不能凭空同时知道所有子树答案。
栈 像叠盘子，最后放的最先取。求只有根2、左孩子1的树高时，根的调用先暂存“等左边答案”，孩子又暂存自己的现场；空孩子返回0后，孩子算出1交给根，根再算出2。程序保存这些未完成调用的地方是调用栈。nonlocal best 允许内部函数更新外层变量best，常用于“递归返回一条路径，同时更新整棵树答案”。
队列 像排队买票，最先进入的最先出去。deque.append(x) 加到尾部，deque.popleft() 从头取出，适合一层层处理树或图；双端队列 还允许从尾部 pop() 删除。不要把栈、队列与递归当成三个新算法，它们首先是不同的待办顺序：最新的先做，或最早的先做。
状态 是“此刻记住哪些信息，就足以继续计算”。例如当前读到第3项、此前总和5，便可用5继续加下一项；不必把前三项反复重加。不变量 是“每轮开始或结束都保证成立的事实”。移动零时可说“写指针w之前恰好存着已读到的全部非零数”，每写入一项就检查它仍成立；它用来解释代码为什么不会漏、乱或重复。
动态规划（DP） 把相同的小问题答案存起来，让大问题直接复用。比如到第4阶的最后一步，要么从第3阶走1步，要么从第2阶走2步，因此 f[4]=f[3]+f[2]。这里“状态”是到第i阶的方案数f[i]，“转移”是由旧答案算新答案的规则；“初始化”给最小问题答案。滚动数组 只是当新答案仅依赖前两项时，只保留那两项而不保存整张表，并非另一种推导。
n表示输入规模，例如数组长度。读 nums[3] 不必扫描前3项，访问次数不随n增长，记 O(1)。从头扫描一次需约n步，记 O(n)；两层各枚举n项共约n²对，记 O(n²)。输入从100变1000，一次扫描约放大10倍，枚举所有数对约放大100倍；这比纠结某一步多一次加法更重要。
每次排除一半候选：1024→512→…→1，仅10轮，这种增长记 O(log n)，本书对数可按以2为底理解。排序通常约 O(n log n)；枚举每项选/不选共有 2^n 种；排列n个不同数共有 n! 种（例如4!=4×3×2×1=24）。若输出本来就有这些数量，算法无法凭空省掉写出答案的代价。
额外空间 看除输入与返回结果外，运行时还保留多少东西。两个指针用常量空间，复制n项的列表要O(n)，递归同时挂起h层调用要O(h)。两次顺序扫描是2n，仍记O(n)；嵌套while也未必O(n²)，如果每项总共只进栈一次、出栈一次，合计仍只有约2n次。字典的O(1)通常是平均情形；Python大整数的位数变长后，算术本身也会更贵。
例如 LC 1 的暴力解要为每个数在其余数里寻找补数，哈希将这段重复搜索压成一次查询。LC 560 表面换成“连续区间和”，本质仍是找补数，只是被查询对象变成旧的前缀和，而且需要记录次数。学习时把这个映射讲出来，比记两段代码更有用。
建议顺序：先学习哈希、双指针、窗口、二分与线性 DP，再学链表、树、图；最后攻克回溯、单调栈、堆和困难题。每类先默写 1 道代表题，再用同类变体检查边界。目录按模式分组，题号保留官方编号，便于对照练习。
代码使用 Python 3 标准库，采用普通函数便于离线练习。提交平台时将函数放进 class Solution 并添加首参数 self；LC 48 的 rotateImage、LC 240 的 searchMatrixII 应分别改回题目要求的 rotate、searchMatrix。内部递归函数引用外层函数时也要相应改成 self.method(...)；辅助局部函数不变。四道设计题直接提供类。
ListNode(val=0,next=None)、TreeNode(val=0,left=None,right=None) 和随机链表的 Node(val,next=None,random=None) 使用平台定义；所有结点比较都指对象身份。复杂度默认按整数运算 O(1) 的面试模型；Python 大整数、字符串复制、排序和输出开销在相关题中单独说明。递归树题的栈深度是树高，极深输入可改迭代，不能用“理论正确”忽略运行时限制。
本书正文默认全部展开，可直接连续阅读与打印。搜索只帮助定位；打印会自动恢复全部题目。PDF 适合离线通读，在线版方便按锚点跳转。
先把这类话说懂：先把名字译成操作：哈希表就是按键快速查询的字典；“补数”是使和达到目标还缺的那一个数，如目标9、当前7，补数就是2。“规范键”是为同类对象生成同一个表示，例如eat与tea都排序成aet。
先问“我重复搜索的是什么？”两数之和存补数，异位词存规范表示，连续序列存成员关系。字典/集合的查询平均 O(1)，最坏情形取决于散列；遍历时明确表里是当前项之前的数据，还是完整数据。
1 两数之和 · 49 字母异位词分组 · 128 最长连续序列
题意：返回数组中两个不同下标，使对应数之和等于 target。题目保证恰有一解。
推导与核心思路：固定当前数 x 后，唯一需要寻找的是 target-x；用字典保存此前数值到下标。
走一遍：[2,7,11,15], target=9 → [0,1]；读到 7 时，字典已有 2。
def twoSum(nums, target):
seen = {}
for i, x in enumerate(nums):
if target - x in seen:
return [seen[target - x], i]
seen[x] = i复杂度：时间 O(n)，额外空间 O(n)。
易错点与适用边界：[3,3], target=6 需要两个不同位置；先存后查会错误地匹配自己。
题意：把只因字母排列不同的字符串放在同一组，组的顺序不限。
推导与核心思路：把字符串排序成同一个规范键；相同键对应相同的字母多重集合。
走一遍：["eat","tea","tan","ate"] → [["eat","tea","ate"],["tan"]]。
def groupAnagrams(strs):
groups = {}
for s in strs:
key = ''.join(sorted(s))
groups.setdefault(key, []).append(s)
return list(groups.values())复杂度：总字符数 L、最长词长 k：时间 O(L log k)，空间 O(L)。
易错点与适用边界：不能用字符集合做键，因为 ab 与 aab 的重复次数不同；空串也必须保留。
题意：无序整数数组中，求数值连续序列的最长长度，不要求原数组相邻。
推导与核心思路：只有没有前驱 x-1 的数才是序列起点；从起点扩张，每个唯一元素只被向后扫描一次。
走一遍：[100,4,200,1,3,2] → 4；只从 1 开始扫描 1,2,3,4。
def longestConsecutive(nums):
values = set(nums)
best = 0
for x in values:
if x - 1 not in values:
y = x
while y in values:
y += 1
best = max(best, y - x)
return best复杂度：平均时间 O(n)，空间 O(n)。
易错点与适用边界：必须遍历去重集合；若遍历带大量重复起点的原数组，可能退化为 O(n²)。
先把这类话说懂：这里“指针”通常只是一个下标变量，不是必须掌握的底层内存地址。相向指针从两端向中间走，例如l=0、r=5；同向指针都朝右，一个负责读取、一个负责写入。一次移动必须能说明：被丢掉的候选为什么不会更好。
相向指针依赖一个能证明的排除规则，而不是“两个指针看起来快”。同向指针维护已处理区间。排序常把三数问题降为两数问题；但排序会改变原下标，不能无条件用于返回下标的题。
283 移动零 · 11 盛最多水的容器 · 15 三数之和 · 42 接雨水
题意：原地把 0 移到末尾，非零元素相对顺序不变。
推导与核心思路：写指针 w 之前恰好是已经扫描到的全部非零元素。
走一遍：[0,1,0,3,12] → 原数组变成 [1,3,12,0,0]。
def moveZeroes(nums):
w = 0
for x in nums:
if x != 0:
nums[w] = x
w += 1
for i in range(w, len(nums)):
nums[i] = 0复杂度：时间 O(n)，额外空间 O(1)。
易错点与适用边界：不要边遍历边删除；本实现逐元素赋值，额外空间 O(1)。
题意：选两条竖线，与横轴组成容器，求最大容量；中间的线不影响容量。
推导与核心思路：面积由较短边和距离决定。固定短边、缩短距离不可能变好，所以舍弃短边是安全的。
走一遍：[1,8,6,2,5,4,8,3,7] → 49，由下标 1 和 8 的线组成。
def maxArea(height):
l, r, best = 0, len(height) - 1, 0
while l < r:
best = max(best, min(height[l], height[r]) * (r - l))
if height[l] <= height[r]:
l += 1
else:
r -= 1
return best复杂度：时间 O(n)，空间 O(1)。
易错点与适用边界：不能移动高边来赌更优解；盛水容器与接雨水的目标不同。
题意：返回和为 0 的不重复三元组，三元组内部顺序不限。
推导与核心思路：排序后固定第一个数，剩余两数和可用相向指针，数值过小左移大、过大右移小。
走一遍：[-1,0,1,2,-1,-4] → [[-1,-1,2],[-1,0,1]]。
def threeSum(nums):
nums = sorted(nums)
ans = []
for i in range(len(nums) - 2):
if i and nums[i] == nums[i - 1]:
continue
l, r = i + 1, len(nums) - 1
while l < r:
total = nums[i] + nums[l] + nums[r]
if total < 0:
l += 1
elif total > 0:
r -= 1
else:
ans.append([nums[i], nums[l], nums[r]])
a, b = nums[l], nums[r]
while l < r and nums[l] == a:
l += 1
while l < r and nums[r] == b:
r -= 1
return ans复杂度：时间 O(n²)，排序空间 O(n)（Python 排序最坏），结果另计。
易错点与适用边界：去重按数值，不是按下标；同一三元组中的两个 0 仍可以来自不同位置。
题意：每根柱宽为 1，下雨后所有凹槽共能积多少水。
推导与核心思路：某位置水量是两侧最高墙较小者减自身高度；维护两端已见最高墙，较小的最高墙一侧可以立刻结算。
走一遍：[4,2,0,3,2,5] → 9；各内部位置水量为 2,4,1,2。
def trap(height):
l, r = 0, len(height) - 1
left = right = ans = 0
while l <= r:
left = max(left, height[l])
right = max(right, height[r])
if left <= right:
ans += left - height[l]
l += 1
else:
ans += right - height[r]
r -= 1
return ans复杂度：时间 O(n)，空间 O(1)。
易错点与适用边界：当前柱高度与历史最高墙不是一个变量；高度差应在更新最高墙后计算，不产生负水量。
先把这类话说懂：窗口是一段连续位置，例如s[2:5]含下标2、3、4；滑动是每次增删两端少量元素。前缀和是从开头累加的和，例如[2,-1,3]的前缀为0、2、1、4，整段之外的一段可用两个前缀相减。单调队列是让候选值按一个方向排好、两端均可删除的队列。
窗口用于连续区间，但能否收缩取决于可维护的条件。含负数的和不单调，不能照搬正数窗口；改用前缀和差。固定窗维护增删，覆盖窗在满足条件后尽量缩短，极值窗删除永远不可能再最优的候选。
3 无重复字符的最长子串 · 438 找到字符串中所有字母异位词 · 560 和为 K 的子数组 · 239 滑动窗口最大值 · 76 最小覆盖子串
题意：求字符串中不含重复字符的最长连续子串长度。
推导与核心思路：窗口 [left,right] 始终无重复；新字符重复时把 left 跳到其上次位置后一位。
走一遍："abba" → 2；窗口先 ab，再 ba。
def lengthOfLongestSubstring(s):
last = {}
left = best = 0
for right, c in enumerate(s):
left = max(left, last.get(c, -1) + 1)
last[c] = right
best = max(best, right - left + 1)
return best复杂度：时间 O(n)，空间 O(min(n,字符集大小))。
易错点与适用边界：left 不能倒退：abba 读到最后的 a，不能把 left 从 2 改成 1。
题意：在小写字母字符串 s 中，返回所有长度为 len(p)、且字符计数等于 p 的窗口起点。
推导与核心思路：固定窗口长度后，只需维护 26 个计数，无需每个窗口重新排序。
走一遍：s="cbaebabacd", p="abc" → [0,6]。
def findAnagrams(s, p):
need, window = [0] * 26, [0] * 26
m = len(p)
for c in p:
need[ord(c) - 97] += 1
ans = []
for i, c in enumerate(s):
window[ord(c) - 97] += 1
if i >= m:
window[ord(s[i - m]) - 97] -= 1
if i >= m - 1 and window == need:
ans.append(i - m + 1)
return ans复杂度：时间 O(26n)=O(n)，空间 O(26)。
易错点与适用边界：右端为 i 时起点 i-m+1；当 s 比 p 短时不记录。
题意：整数数组中，统计和为 k 的非空连续子数组数量；允许负数。
推导与核心思路：若当前前缀和为 total，要找的旧前缀和就是 total-k；存出现次数而非单一位置。
走一遍：[1,1,1], k=2 → 2；两个位置不同的 [1,1]。
def subarraySum(nums, k):
freq = {0: 1}
total = ans = 0
for x in nums:
total += x
ans += freq.get(total - k, 0)
freq[total] = freq.get(total, 0) + 1
return ans复杂度：平均时间 O(n)，空间 O(n)。
易错点与适用边界：先记录当前前缀会在 k=0 时计入空子数组；负数使普通滑动窗口失效。
题意：返回每个长度为 k 的连续窗口的最大值。
推导与核心思路：双端队列存下标，数值从队首到队尾递减；新数更大时，旧的小数更早过期且永远不会再是最大值。
走一遍：[1,3,-1,-3,5,3,6,7], k=3 → [3,3,5,5,6,7]。
def maxSlidingWindow(nums, k):
from collections import deque
candidates, ans = deque(), []
for i, x in enumerate(nums):
while candidates and candidates[0] <= i - k:
candidates.popleft()
while candidates and nums[candidates[-1]] <= x:
candidates.pop()
candidates.append(i)
if i >= k - 1:
ans.append(nums[candidates[0]])
return ans复杂度：时间 O(n)，空间 O(k)。
易错点与适用边界：必须存下标才能判断过期；每个下标最多入队出队各一次，嵌套 while 仍为线性。
题意：在 s 中找包含 t 全部字符及其重复次数的最短子串，不存在返回空串。
推导与核心思路：need 保存尚缺数量，missing 保存尚缺的字符总数；右端扩张到覆盖后，左端尽可能收缩。
走一遍：s="ADOBECODEBANC", t="ABC" → "BANC"。
def minWindow(s, t):
from collections import Counter
if not t:
return ''
need = Counter(t)
missing, left = len(t), 0
start, best = 0, len(s) + 1
for right, c in enumerate(s):
if need[c] > 0:
missing -= 1
need[c] -= 1
while missing == 0:
if right - left + 1 < best:
start, best = left, right - left + 1
old = s[left]
need[old] += 1
if need[old] > 0:
missing += 1
left += 1
return '' if best > len(s) else s[start:start + best]复杂度：时间 O(len(s)+len(t))，空间 O(字符集大小)。
易错点与适用边界：t="AA" 需要两个 A；覆盖种类数与覆盖字符总数不是一回事。
先把这类话说懂：数组在本书中用Python列表表示，矩阵是“列表里再放每一行”。m行n列中的matrix[i][j]先取第i行，再取第j列。原地修改是直接改变输入对象；前缀是当前位置前面的部分，后缀是后面的部分；几何变换则是把旧坐标算成新坐标。
数组题先区分是否必须原地、能否排序、输出是否包含自身。前后缀可把“排除自身”分成两部分。原地哈希把值 x 放到下标 x-1；矩阵题用边界或坐标变换，不能把行列写反。
53 最大子数组和 · 56 合并区间 · 189 轮转数组 · 238 除了自身以外数组的乘积 · 41 缺失的第一个正数 · 73 矩阵置零 · 54 螺旋矩阵 · 48 旋转图像 · 240 搜索二维矩阵 II
题意：非空整数数组中，求非空连续子数组的最大和。
推导与核心思路：end 表示必须以当前位置结尾的最优和；前面的 end 为负时，接上它只会更差。
走一遍：[-2,1,-3,4,-1,2,1,-5,4] → 6，对应 [4,-1,2,1]。
def maxSubArray(nums):
end = best = nums[0]
for i in range(1, len(nums)):
x = nums[i]
end = max(x, end + x)
best = max(best, end)
return best复杂度：时间 O(n)，空间 O(1)。
易错点与适用边界：不能把 best 初始化为 0，否则全负数组会错误地选择空子数组。
题意：把所有有交集的闭区间合并，返回互不重叠的区间。
推导与核心思路：按左端点排序，当前区间只可能与最后一个已合并区间相交。
走一遍：[[1,3],[2,6],[8,10]] → [[1,6],[8,10]]。
def merge(intervals):
ans = []
for a, b in sorted(intervals):
if not ans or a > ans[-1][1]:
ans.append([a, b])
else:
ans[-1][1] = max(ans[-1][1], b)
return ans复杂度：时间 O(n log n)，空间 O(n) 含结果和排序。
易错点与适用边界：[1,4] 与 [4,5] 在闭区间语义下应合并；更新终点要取 max，不能直接覆盖。
题意：原地把数组向右移动 k 位。
推导与核心思路：整体反转会交换两段的位置，再分别反转两段恢复各自顺序。
走一遍：[1,2,3,4,5,6,7], k=3 → [5,6,7,1,2,3,4]。
def rotate(nums, k):
if not nums:
return
def reverse(l, r):
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1
k %= len(nums)
reverse(0, len(nums) - 1)
reverse(0, k - 1)
reverse(k, len(nums) - 1)复杂度：时间 O(n)，额外空间 O(1)。
易错点与适用边界：右移与左移方向不同；空数组先返回，避免模 0。
题意：不用除法，返回每个位置之外所有元素的乘积。
推导与核心思路：答案等于左侧全部乘积乘右侧全部乘积；输出数组先存左积，再用一个变量乘入右积。
走一遍：[1,2,3,4] → [24,12,8,6]；[0,2,3] → [6,0,0]。
def productExceptSelf(nums):
ans, prefix = [], 1
for x in nums:
ans.append(prefix)
prefix *= x
suffix = 1
for i in range(len(nums) - 1, -1, -1):
ans[i] *= suffix
suffix *= nums[i]
return ans复杂度：时间 O(n)，除输出外空间 O(1)。
易错点与适用边界：不能先乘自身；有一个或多个 0 的输入也应自然处理，无需除法特判。
题意：在 O(n) 时间、O(1) 额外空间内找未出现的最小正整数。
推导与核心思路：长度 n 的数组答案只可能在 1..n+1；将值 x 放到槽位 x-1，数组自己充当哈希表。
走一遍：[3,4,-1,1] 归位后 [1,-1,3,4] → 2。
def firstMissingPositive(nums):
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
j = nums[i] - 1
nums[i], nums[j] = nums[j], nums[i]
for i, x in enumerate(nums):
if x != i + 1:
return i + 1
return n + 1复杂度：时间 O(n)，额外空间 O(1)。
易错点与适用边界：重复数字必须检测目标槽已相等，否则无限交换；0 和负数无需归位。
题意：若某元素为 0，将其整行整列原地置 0。
推导与核心思路：第一行和第一列作标记，另用两个布尔值记下它们原本是否含 0。
走一遍：[[1,1,1],[1,0,1],[1,1,1]] → [[1,0,1],[0,0,0],[1,0,1]]。
def setZeroes(matrix):
m, n = len(matrix), len(matrix[0])
row0 = any(x == 0 for x in matrix[0])
col0 = any(matrix[i][0] == 0 for i in range(m))
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = matrix[0][j] = 0
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if row0:
for j in range(n):
matrix[0][j] = 0
if col0:
for i in range(m):
matrix[i][0] = 0复杂度：时间 O(mn)，额外空间 O(1)。
易错点与适用边界：边发现 0 边清整行会把新写的 0 当作原始 0 扩散；标记阶段与修改阶段分开。
题意：按顺时针由外向内输出矩阵元素。
推导与核心思路：维护尚未访问的上、下、左、右四条边，每走完一条就收缩对应边界。
走一遍：[[1,2,3],[4,5,6],[7,8,9]] → [1,2,3,6,9,8,7,4,5]。
def spiralOrder(matrix):
top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
ans = []
while top <= bottom and left <= right:
for j in range(left, right + 1):
ans.append(matrix[top][j])
top += 1
for i in range(top, bottom + 1):
ans.append(matrix[i][right])
right -= 1
if top <= bottom:
for j in range(right, left - 1, -1):
ans.append(matrix[bottom][j])
bottom -= 1
if left <= right:
for i in range(bottom, top - 1, -1):
ans.append(matrix[i][left])
left += 1
return ans复杂度：时间 O(mn)，除输出空间 O(1)。
易错点与适用边界：单行或单列时，后两条边必须检查边界，避免重复访问。
题意：将 n×n 矩阵顺时针旋转 90°，要求原地修改。
推导与核心思路：顺时针坐标变换 (i,j)→(j,n-1-i)，可分解为主对角线转置后逐行反转。
走一遍：[[1,2],[3,4]] → [[3,1],[4,2]]。
def rotateImage(matrix):
n = len(matrix)
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for row in matrix:
row.reverse()复杂度：时间 O(n²)，额外空间 O(1)。
易错点与适用边界：不要把矩阵行列都遍历后交换，那会交换两次回到原状；本题必须是方阵。
题意：每行从左到右、每列从上到下递增，判断 target 是否存在。
推导与核心思路：右上角同时具有本行最大、本列最小的性质，一次比较可以排除一整行或一整列。
走一遍：[[1,4,7],[2,5,8],[3,6,9]], target=6 → True。
def searchMatrixII(matrix, target):
if not matrix or not matrix[0]:
return False
i, j = 0, len(matrix[0]) - 1
while i < len(matrix) and j >= 0:
x = matrix[i][j]
if x == target:
return True
if x > target:
j -= 1
else:
i += 1
return False复杂度：时间 O(m+n)，空间 O(1)。
易错点与适用边界：不能把整个矩阵直接展平成有序数组；题目没有保证上一行末尾小于下一行开头。
先把这类话说懂：链表没有列表那样按下标直接跳到第i项的能力，只能顺着next走。虚拟头dummy是在真正头结点前临时放一个空结点，使“删第一个”也能写成“改前一个的next”。快慢指针是每轮分别走两步与一步的两个结点引用；归并是反复取两条有序链较小的头。
链表操作的单位是结点身份，不是数值。dummy 虚拟头可统一删除首结点与中间结点。修改 next 前先保存还要访问的结点；快慢指针解决中点和环，归并把有序链拆成能复用的原语。下面 Node、ListNode、TreeNode 由评测平台提供，离线测试中有等价定义。
160 相交链表 · 206 反转链表 · 234 回文链表 · 141 环形链表 · 142 环形链表 II · 21 合并两个有序链表 · 2 两数相加 · 19 删除链表的倒数第 N 个结点 · 24 两两交换链表中的节点 · 25 K 个一组翻转链表 · 138 随机链表的复制 · 148 排序链表 · 23 合并 K 个升序链表 · 146 LRU 缓存
题意：两条无环单链表若共享同一个尾部结点，返回第一个共享结点，否则返回 None。
推导与核心思路：各走完 A+B 与 B+A，总路程相同，较长链的长度差自动抵消。
走一遍：A=1→共享结点 8→9，B=2→3→同一个 8→9 → 返回共享的 8 结点。
def getIntersectionNode(headA, headB):
a, b = headA, headB
while a is not b:
a = a.next if a else headB
b = b.next if b else headA
return a复杂度：时间 O(m+n)，空间 O(1)。
易错点与适用边界：相交指同一个对象，数值相等不算；两条链无交点时会一起变为 None。
题意：原地反转单链表并返回新的头结点。
推导与核心思路：prev 是已反转前缀的头，cur 是还未处理的后缀头。
走一遍：1→2→3→None → 3→2→1→None。
def reverseList(head):
prev, cur = None, head
while cur:
nxt = cur.next
cur.next = prev
prev, cur = cur, nxt
return prev复杂度：时间 O(n)，空间 O(1)。
易错点与适用边界：先改 next 再读取 cur.next 会丢失后续链；最后返回 prev 而非 cur。
题意：判断单链表的结点值序列是否为回文。
推导与核心思路：快慢指针定位后半段；反转后半段后，两端即可同时向中间比较。
走一遍：1→2→2→1 → True；比较后仍保持原链。
def isPalindrome(head):
if not head or not head.next:
return True
def rev(node):
prev = None
while node:
nxt = node.next
node.next = prev
prev, node = node, nxt
return prev
slow = fast = head
while fast.next and fast.next.next:
slow, fast = slow.next, fast.next.next
half = rev(slow.next)
a, b, ok = head, half, True
while b:
if a.val != b.val:
ok = False
a, b = a.next, b.next
slow.next = rev(half)
return ok复杂度：时间 O(n)，额外空间 O(1)。
易错点与适用边界：只比较后半段长度；奇数长度的中点不影响；不要提前 return 而忘记恢复原链。
题意：判断单链表中是否存在环。
推导与核心思路：有环时快指针每轮比慢指针多走一步，相对距离会模环长循环，必然相遇。
走一遍：1→2→3→2（回到第二结点）→ True；普通 1→2→None → False。
def hasCycle(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
return True
return False复杂度：时间 O(n)，空间 O(1)。
易错点与适用边界：先移动再比较，否则刚初始化就在头结点相遇；访问 fast.next 前检查 fast。
题意：有环则返回入环的第一个结点，无环返回 None。
推导与核心思路：相遇时若入环前长 a、慢指针在环内走 b，则 a+b 是环长的整数倍；一个从头、一个从相遇点同步走会在入口相遇。
走一遍：3→2→0→-4→回到结点 2 → 返回 2 所在结点。
def detectCycle(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
entry = head
while entry is not slow:
entry, slow = entry.next, slow.next
return entry
return None复杂度：时间 O(n)，空间 O(1)。
易错点与适用边界：返回的是入口结点对象；不可用修改链表标记的办法破坏输入。
题意：把两个非降序链表合并为一个非降序链表。
推导与核心思路：当前最小值一定在两个头结点之一；不断把较小头接到答案尾部。
走一遍：1→2→4 与 1→3→4 → 1→1→2→3→4→4。
def mergeTwoLists(list1, list2):
dummy = tail = ListNode(0)
while list1 and list2:
if list1.val <= list2.val:
tail.next, list1 = list1, list1.next
else:
tail.next, list2 = list2, list2.next
tail = tail.next
tail.next = list1 or list2
return dummy.next复杂度：时间 O(m+n)，额外空间 O(1)。
易错点与适用边界：tail 每次必须推进；返回 dummy.next，不能返回虚拟结点。
题意：两个非负整数以逆序链表存储，每结点一位；返回和的逆序链表。
推导与核心思路：逐位相加并保留进位，长短不同的链用 0 补齐。
走一遍：2→4→3 表示 342，5→6→4 表示 465；输出 7→0→8 表示 807。
def addTwoNumbers(l1, l2):
dummy = tail = ListNode(0)
carry = 0
while l1 or l2 or carry:
total = carry + (l1.val if l1 else 0) + (l2.val if l2 else 0)
carry, digit = divmod(total, 10)
tail.next = ListNode(digit)
tail = tail.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.next复杂度：时间 O(max(m,n))，输出 O(max(m,n))，额外状态 O(1)。
易错点与适用边界：末尾进位必须生成新结点；不能把整条链直接转成整数来绕过题目。
题意：删除倒数第 n 个结点并返回头；保证 n 有效。
推导与核心思路：前后指针相隔 n 个结点；前指针到尾时，后指针恰好在待删除结点前。
走一遍：1→2→3→4→5, n=2 → 1→2→3→5。
def removeNthFromEnd(head, n):
dummy = ListNode(0, head)
fast = slow = dummy
for _ in range(n):
fast = fast.next
while fast.next:
slow, fast = slow.next, fast.next
slow.next = slow.next.next
return dummy.next复杂度：时间 O(n)，空间 O(1)。
易错点与适用边界：从 dummy 起步可覆盖删头；循环用 fast.next 与先走 n 步必须配套。
题意：交换每一对相邻结点，不能仅交换数值。
推导与核心思路：保存一对结点 a、b，重连 prev→b→a→后缀，再将 prev 移到 a。
走一遍：1→2→3→4→5 → 2→1→4→3→5。
def swapPairs(head):
dummy = ListNode(0, head)
prev = dummy
while prev.next and prev.next.next:
a, b = prev.next, prev.next.next
a.next = b.next
b.next = a
prev.next = b
prev = a
return dummy.next复杂度：时间 O(n)，空间 O(1)。
易错点与适用边界：重连 a.next 前要记住 b；修改的是链接，不是 val。
题意：每 k 个结点原地翻转，不满 k 个的尾段保留。
推导与核心思路：每轮先确认整组存在，再以组后结点为 prev 反转这一组，最后连接组前结点。
走一遍：1→2→3→4→5, k=3 → 3→2→1→4→5。
def reverseKGroup(head, k):
dummy = ListNode(0, head)
before = dummy
while True:
kth = before
for _ in range(k):
kth = kth.next
if kth is None:
return dummy.next
after, cur = kth.next, before.next
prev = after
while cur is not after:
nxt = cur.next
cur.next = prev
prev, cur = cur, nxt
old_head = before.next
before.next = kth
before = old_head复杂度：时间 O(n)，空间 O(1)。
易错点与适用边界：不能先翻转后才发现不足 k 个；反转期间 cur 与 after 比较身份。
题意：深拷贝带 next 和 random 指针的链表；新旧结点不能共享。
推导与核心思路：先建立原结点→新结点的映射，第二遍才能同时正确连接向前或向后的 random。
走一遍：两结点 7→13，13.random 指向 7；复制后新 13 指向新 7，不能指回旧 7。
def copyRandomList(head):
copies = {None: None}
cur = head
while cur:
copies[cur] = Node(cur.val)
cur = cur.next
cur = head
while cur:
copies[cur].next = copies[cur.next]
copies[cur].random = copies[cur.random]
cur = cur.next
return copies[head]复杂度：时间 O(n)，额外空间 O(n)。
易错点与适用边界：不能以值作映射键，因为值可重复；random 可以指向自身或任意先前结点。
题意：将链表升序排序。
推导与核心思路：链表没有随机访问，用快慢指针分半、递归排序、线性归并，得到 O(n log n)。
走一遍：4→2→1→3 → 1→2→3→4。
def sortList(head):
if not head or not head.next:
return head
slow, fast = head, head.next
while fast and fast.next:
slow, fast = slow.next, fast.next.next
second = slow.next
slow.next = None
a, b = sortList(head), sortList(second)
dummy = tail = ListNode(0)
while a and b:
if a.val <= b.val:
tail.next, a = a, a.next
else:
tail.next, b = b, b.next
tail = tail.next
tail.next = a or b
return dummy.next复杂度：时间 O(n log n)，额外空间 O(log n) 递归栈。
易错点与适用边界：必须断开 slow.next，否则递归区间不缩小；此教学版递归栈 O(log n)，不是严格 O(1) 空间。
题意：合并 k 条有序链，设所有结点总数为 N。
推导与核心思路：最小堆只保存每条链的当前头，堆顶就是全局下一个最小结点。
走一遍：[1→4→5, 1→3→4, 2→6] → 1→1→2→3→4→4→5→6。
def mergeKLists(lists):
import heapq
from itertools import count
serial, heap = count(), []
for node in lists:
if node:
heapq.heappush(heap, (node.val, next(serial), node))
dummy = tail = ListNode(0)
while heap:
_, _, node = heapq.heappop(heap)
tail.next = node
tail = node
if node.next:
heapq.heappush(heap, (node.next.val, next(serial), node.next))
return dummy.next复杂度：时间 O(N log k)，额外空间 O(k)。
易错点与适用边界：Python 的结点不能直接比较；堆元组增加唯一递增序号，避免相等 val 时比较结点。
题意：实现容量固定的缓存，get/put 平均 O(1)；满时淘汰最久未被访问的键。
推导与核心思路：字典把 key 映射到双向链表结点，可 O(1) 定位与删除；循环哨兵 root 的 next 为最旧、prev 为最新，省掉空链和头尾特判。
走一遍：容量 2；put(1,1),put(2,2),get(1),put(3,3) 后 get(2)=-1。
class LRUCache:
class _Link:
def __init__(self, key=None, value=None):
self.key, self.value = key, value
self.prev = self.next = self
def __init__(self, capacity):
self.capacity = capacity
self.data = {}
self.root = self._Link()
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _recent(self, node):
tail = self.root.prev
tail.next = node
node.prev = tail
node.next = self.root
self.root.prev = node
def get(self, key):
if key not in self.data:
return -1
node = self.data[key]
self._remove(node)
self._recent(node)
return node.value
def put(self, key, value):
if key in self.data:
node = self.data[key]
node.value = value
self._remove(node)
else:
node = self._Link(key, value)
self.data[key] = node
self._recent(node)
if len(self.data) > self.capacity:
oldest = self.root.next
self._remove(oldest)
del self.data[oldest.key]复杂度：get/put 平均 O(1)，空间 O(capacity)。
易错点与适用边界：更新已有键也算使用；双向连接要成对修改；淘汰时字典与链表必须同时移除，否则会保留失效结点。
先把这类话说懂：树高是根到最远叶结点的结点数；直径则是任意两结点间最长路径的边数。“遍历”指按某种顺序访问每个结点：中序是左子树→根→右子树，前序是根→左→右，后序是左→右→根；层序则先根，再其孩子，再孙子。BST即前文的二叉搜索树。
每道树题先写出递归函数“返回什么”。深度返回一条向下路径，直径/最大路径和却在当前结点把左右贡献合并；合并结果更新全局答案，不能继续向父结点返回分叉路径。层序遍历用队列按层处理；BST 的中序是递增序列。h 表示树高，最坏可等于 n。
94 二叉树的中序遍历 · 104 二叉树的最大深度 · 226 翻转二叉树 · 101 对称二叉树 · 543 二叉树的直径 · 102 二叉树的层序遍历 · 108 将有序数组转换为二叉搜索树 · 98 验证二叉搜索树 · 230 二叉搜索树中第 K 小的元素 · 199 二叉树的右视图 · 114 二叉树展开为链表 · 105 从前序与中序遍历序列构造二叉树 · 437 路径总和 III · 236 二叉树的最近公共祖先 · 124 二叉树中的最大路径和
题意：按左子树、根、右子树输出结点值。
推导与核心思路：显式栈模拟递归：先把所有左子孙压栈，弹出的结点就是下一个中序结点。
走一遍：根 1、右子 2、2 的左子 3 → [1,3,2]。
def inorderTraversal(root):
stack, ans, cur = [], [], root
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
ans.append(cur.val)
cur = cur.right
return ans复杂度：时间 O(n)，额外空间 O(h)，输出 O(n)。
易错点与适用边界：循环条件是 cur 非空或栈非空；遍历到空左孩子并不意味着结束。
题意：求从根到最远叶结点路径上的结点数。
推导与核心思路：空树深度 0；非空树深度等于左右最大深度加 1。
走一遍：根 3，左子 9，右子 20 且 20 有两孩子 → 3。
def maxDepth(root):
if root is None:
return 0
return 1 + max(maxDepth(root.left), maxDepth(root.right))复杂度：时间 O(n)，空间 O(h)。
易错点与适用边界：深度按结点数；只有根时返回 1。偏斜树很深时 Python 递归可能达栈限制，可改层序。
题意：交换每个结点的左右子树。
推导与核心思路：每个子树都执行同一交换，递归结构与问题一致。
走一遍：[4,2,7,1,3,6,9] → [4,7,2,9,6,3,1]（层序）。
def invertTree(root):
if root:
root.left, root.right = invertTree(root.right), invertTree(root.left)
return root复杂度：时间 O(n)，空间 O(h)。
易错点与适用边界：交换的是整棵子树引用；不能只交换孩子的数值。
题意：判断二叉树是否以根为中心镜像对称。
推导与核心思路：比较两个结点时，需要 a.left 对 b.right、a.right 对 b.left，而非同方向。
走一遍：[1,2,2,3,4,4,3] → True；[1,2,2,None,3,None,3] → False。
def isSymmetric(root):
def mirror(a, b):
if not a or not b:
return a is b
return (a.val == b.val and mirror(a.left, b.right)
and mirror(a.right, b.left))
return root is None or mirror(root.left, root.right)复杂度：时间 O(n)，空间 O(h)。
易错点与适用边界：仅比较每一层数值集合不够，空结点的位置也决定结构。
题意：求任意两个结点之间最长路径的边数，路径可以不经过根。
推导与核心思路：左右子树高度之和就是经过当前结点的最长路径边数；递归返回值只保留一边高度。
走一遍：[1,2,3,4,5] → 3，路径 4→2→1→3。
def diameterOfBinaryTree(root):
best = 0
def height(node):
nonlocal best
if not node:
return 0
left, right = height(node.left), height(node.right)
best = max(best, left + right)
return 1 + max(left, right)
height(root)
return best复杂度：时间 O(n)，空间 O(h)。
易错点与适用边界：直径按边数、高度按结点数，这里 left+right 已是边数，不再加 1。
题意：逐层从左到右输出结点值，每层单独一个列表。
推导与核心思路：处理本层前固定队列长度，新加入孩子留给下一层。
走一遍：[3,9,20,None,None,15,7] → [[3],[9,20],[15,7]]。
def levelOrder(root):
from collections import deque
queue = deque([root]) if root else deque()
ans = []
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
ans.append(level)
return ans复杂度：时间 O(n)，空间 O(w)，w 为最大层宽，输出另计。
易错点与适用边界：不能在本层循环中动态改变终止长度；list.pop(0) 会产生线性搬移，改用 deque。
题意：把严格递增数组转为高度平衡 BST。
推导与核心思路：中点作根，将左右半区分别转为左右子树，保证排序性质和高度平衡。
走一遍：[-10,-3,0,5,9] → 根可为 0，左右分别由两个半区构建。
def sortedArrayToBST(nums):
def build(l, r):
if l >= r:
return None
mid = (l + r) // 2
root = TreeNode(nums[mid])
root.left = build(l, mid)
root.right = build(mid + 1, r)
return root
return build(0, len(nums))复杂度：时间 O(n)，额外栈 O(log n)，树输出 O(n)。
易错点与适用边界：用区间下标而非切片，避免不必要复制；偶数长度可以选两个中点中的任一个。
题意：判断每个结点的左子树全部小于它、右子树全部大于它。
推导与核心思路：祖先传下来的上下界必须同时满足，不能只比较直接孩子。
走一遍：[2,1,3] → True；[2,2,3] → False。
def isValidBST(root):
def valid(node, low, high):
if not node:
return True
return (low < node.val < high
and valid(node.left, low, node.val)
and valid(node.right, node.val, high))
return valid(root, float('-inf'), float('inf'))复杂度：时间 O(n)，空间 O(h)。
易错点与适用边界：重复值不合法；[5,1,4,None,None,3,6] 的 4 虽局部孩子正确但小于祖先 5。
题意：合法 BST 中返回第 k 小的值，k 从 1 开始且有效。
推导与核心思路：BST 的中序遍历是升序，第 k 次弹栈即答案，无需遍历全部结点。
走一遍：[3,1,4,None,2], k=2 → 2。
def kthSmallest(root, k):
stack, cur = [], root
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
k -= 1
if k == 0:
return cur.val
cur = cur.right复杂度：时间 O(h+k)，空间 O(h)。
易错点与适用边界：若题目变成频繁更新和查询，需要维护子树大小；这里只解决静态单次查询。
题意：从右侧能看到的每层最右结点值。
推导与核心思路：层序遍历每层最后一个结点就是可见结点，右侧没有孩子时也可能由左子树贡献。
走一遍：[1,2,3,None,5,None,4] → [1,3,4]。
def rightSideView(root):
from collections import deque
queue = deque([root]) if root else deque()
ans = []
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
ans.append(node.val)
return ans复杂度：时间 O(n)，空间 O(w)，输出另计。
易错点与适用边界：不能只沿 right 指针走；右子树较浅时，更深层可能来自左边。
题意：原地把树按前序顺序展开，所有 left 置空，right 指向下一结点。
推导与核心思路：存在左子树时，把原右子树接到左子树最右结点，再把左子树搬到右边。
走一遍：[1,2,5,3,4,None,6] → right 链 1→2→3→4→5→6。
def flatten(root):
cur = root
while cur:
if cur.left:
tail = cur.left
while tail.right:
tail = tail.right
tail.right = cur.right
cur.right = cur.left
cur.left = None
cur = cur.right复杂度：时间 O(n)，额外空间 O(1)。
易错点与适用边界：最终必须清空每个 left；不能新建结点替代原树。所有前驱查找的右边合计线性。
题意：给定值互不重复的前序和中序序列，重建原树。
推导与核心思路：前序下一个元素是根；它在中序的位置将左右子树分开，按左后右消费前序。
走一遍：前序 [3,9,20,15,7]、中序 [9,3,15,20,7] → 根 3，左 9，右 20。
def buildTree(preorder, inorder):
positions = {x: i for i, x in enumerate(inorder)}
values = iter(preorder)
def build(l, r):
if l >= r:
return None
value = next(values)
mid = positions[value]
node = TreeNode(value)
node.left = build(l, mid)
node.right = build(mid + 1, r)
return node
return build(0, len(inorder))复杂度：时间 O(n)，额外空间 O(n) 含映射与栈。
易错点与适用边界：前序迭代器是共享状态，构造左右顺序不能颠倒；重复值不适用这张位置映射。
题意：统计所有从某结点向下延伸、和值为 targetSum 的非空路径，不要求从根开始。
推导与核心思路：根到当前结点的前缀和减某祖先前缀和等于目标，复用一维前缀和计数。
走一遍：[10,5,-3,3,2,None,11,3,-2,None,1], target=8 → 3。
def pathSum(root, targetSum):
counts = {0: 1}
def visit(node, total):
if not node:
return 0
total += node.val
ans = counts.get(total - targetSum, 0)
counts[total] = counts.get(total, 0) + 1
ans += visit(node.left, total) + visit(node.right, total)
counts[total] -= 1
return ans
return visit(root, 0)复杂度：平均时间 O(n)，空间 O(h)。
易错点与适用边界：回溯减计数必不可少，否则会把另一分支的前缀当作祖先；先查后加避免空路径。
题意：给定两个确实存在且不同的结点 p、q，返回最近公共祖先。
推导与核心思路：递归返回当前子树找到的目标或公共祖先；若左右各找到一个，当前根就是交汇点。
走一遍：根 3，左右子树分别含 5、1；p=5,q=1 → 3。
def lowestCommonAncestor(root, p, q):
if root is None or root is p or root is q:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left or right复杂度：时间 O(n)，空间 O(h)。
易错点与适用边界：比较结点身份；一个目标可能是另一个的祖先，此时应返回祖先目标本身。
题意：求任意非空简单路径的最大结点和值，路径不必经过根。
推导与核心思路：负贡献可以舍弃；经过当前根的答案可连接左右两边，但向父亲返回时只能选一边。
走一遍：[-10,9,20,None,None,15,7] → 42，路径 15→20→7。
def maxPathSum(root):
best = float('-inf')
def gain(node):
nonlocal best
if not node:
return 0
left = max(0, gain(node.left))
right = max(0, gain(node.right))
best = max(best, node.val + left + right)
return node.val + max(left, right)
gain(root)
return best复杂度：时间 O(n)，空间 O(h)。
易错点与适用边界：best 初始化为 -∞，才能处理全负树；不能把左右都返回给父结点，路径不能分叉。
先把这类话说懂：图由“点”和“边”组成，边表示可走通道或先后依赖。DFS（深度优先）沿一条路尽量走到底再回头；BFS（广度优先）先走完一步可达点，再两步可达点。连通块是一组能互相走到的点；入度是指向某点的依赖边数量；拓扑序是让所有先修任务都排在后修任务之前的顺序。Trie叫前缀树，单词共享的开头只存一份路径。
DFS/栈找连通块；多源 BFS 把所有起点同时入队，层数就是最短传播时间；有向依赖用入度消除，剩余结点意味着环。访问标记在入队时设置，避免重复入队。Trie 则把共享字符串前缀压成路径，末尾标记区分完整单词与前缀。
200 岛屿数量 · 994 腐烂的橘子 · 207 课程表 · 208 实现 Trie（前缀树）
题意：字符网格中 1 为陆地、0 为水，四方向相连算一座岛，求岛数。
推导与核心思路：每遇到尚未标记的陆地就新开一个连通块，用栈把整座岛淹掉。
走一遍：[["1","1","0"],["0","1","0"],["0","0","1"]] → 2。
def numIslands(grid):
if not grid:
return 0
m, n, ans = len(grid), len(grid[0]), 0
for i in range(m):
for j in range(n):
if grid[i][j] != '1':
continue
ans += 1
grid[i][j] = '0'
stack = [(i, j)]
while stack:
r, c = stack.pop()
for a, b in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
if 0 <= a < m and 0 <= b < n and grid[a][b] == '1':
grid[a][b] = '0'
stack.append((a, b))
return ans复杂度：时间 O(mn)，最坏额外空间 O(mn)。
易错点与适用边界：对角线不相连；本实现会修改输入；迭代栈避免巨大岛屿导致 Python 递归溢出。
题意：每分钟腐烂橘子使四邻新鲜橘子腐烂；返回全部腐烂的最少分钟，无法全部腐烂则 -1。
推导与核心思路：所有初始腐烂点同时做 BFS，传播层数等于最近腐烂源距离。
走一遍：[[2,1,1],[1,1,0],[0,1,1]] → 4。
def orangesRotting(grid):
from collections import deque
m, n = len(grid), len(grid[0])
queue = deque()
fresh = minutes = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
queue.append((i, j))
elif grid[i][j] == 1:
fresh += 1
while queue and fresh:
minutes += 1
for _ in range(len(queue)):
r, c = queue.popleft()
for a, b in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
if 0 <= a < m and 0 <= b < n and grid[a][b] == 1:
grid[a][b] = 2
fresh -= 1
queue.append((a, b))
return minutes if fresh == 0 else -1复杂度：时间 O(mn)，空间 O(mn)。
易错点与适用边界：没有新鲜橘子直接 0；不能从每个腐烂点分开 DFS 求时间。
题意：[a,b] 表示上 a 前必须先上 b，判断是否能完成全部课程。
推导与核心思路：有向图存在拓扑序等价于无环；反复删除入度 0 的结点，模拟选课。
走一遍：2 门课，[[1,0]] → True；[[1,0],[0,1]] → False。
def canFinish(numCourses, prerequisites):
from collections import deque
graph = [[] for _ in range(numCourses)]
degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
degree[a] += 1
queue = deque(i for i, d in enumerate(degree) if d == 0)
done = 0
while queue:
cur = queue.popleft()
done += 1
for nxt in graph[cur]:
degree[nxt] -= 1
if degree[nxt] == 0:
queue.append(nxt)
return done == numCourses复杂度：时间 O(V+E)，空间 O(V+E)。
易错点与适用边界：边方向要与入度一致；无依赖的孤立课程也应入队，不能只枚举边里出现的课程。
题意：支持 insert(word)、search(word) 与 startsWith(prefix)。
推导与核心思路：每条边表示一个字符；字典嵌套存孩子，特殊结束键表示某条路径也是完整单词。
走一遍：insert("apple") 后 search("apple")=True，search("app")=False。
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for c in word:
node = node.setdefault(c, {})
node['#'] = True
def _walk(self, text):
node = self.root
for c in text:
if c not in node:
return None
node = node[c]
return node
def search(self, word):
node = self._walk(word)
return node is not None and '#' in node
def startsWith(self, prefix):
return self._walk(prefix) is not None复杂度：每操作时间 O(L)，空间与所有不同前缀总长度成正比。
易错点与适用边界：插入 apple 后 search(app) 应为 False，startsWith(app) 为 True；结束标记不应与合法字符冲突。
先把这类话说懂：回溯就是试一个选择，继续往下试，再撤销这个选择试另一条路。全排列问不同的摆放顺序；组合只问选了哪些数，不区分[2,3]与[3,2]；剪枝是发现这条路已不可能合法后立即停止，而不是把所有结果生成后再删。
回溯是在一棵隐含决策树中枚举合法结果。排列维护“哪些位置已用”；组合维护起点避免不同顺序重复；路径每次修改后都要恢复。先用状态定义解释为什么不漏不重，再谈剪枝。输出规模常为指数，复杂度必须计入复制答案的代价。
46 全排列 · 78 子集 · 17 电话号码的字母组合 · 39 组合总和 · 22 括号生成 · 79 单词搜索 · 131 分割回文串 · 51 N 皇后
题意：对值互不相同的数组，返回所有排列。
推导与核心思路：每一层决定下一个位置选哪个尚未使用的原下标。
走一遍：[1,2,3] → 6 种排列；固定首位 1 后递归排列 [2,3]。
def permute(nums):
ans, path, used = [], [], [False] * len(nums)
def dfs():
if len(path) == len(nums):
ans.append(path.copy())
return
for i, x in enumerate(nums):
if not used[i]:
used[i] = True
path.append(x)
dfs()
path.pop()
used[i] = False
dfs()
return ans复杂度：时间 O(n·n!)，额外搜索栈与标记 O(n)，输出 O(n·n!)。
易错点与适用边界：append(path) 会引用同一个可变列表，必须 path.copy()；本题不处理重复输入去重。
题意：返回互不相同元素数组的所有子集，包括空集。
推导与核心思路：每个元素只有选与不选两种决定；逐轮将已有子集各复制一份并加上新元素。
走一遍：[1,2]：先 [[]]，加入 1 得 [[],[1]]，加入 2 得 [[],[1],[2],[1,2]]。
def subsets(nums):
ans = [[]]
for x in nums:
ans += [part + [x] for part in ans]
return ans复杂度：时间 O(n·2^n)，含输出空间 O(n·2^n)。
易错点与适用边界：遍历 ans 时不能同时无界追加；列表推导先计算新增结果再扩展。
题意：输入仅含 2..9 的数字串，返回电话按键可能对应的全部字母串；空输入返回空列表。
推导与核心思路：每一层对一个数字选择一个字母，结果是各按键候选集合的笛卡尔积。
走一遍："23" → ["ad","ae","af","bd","be","bf","cd","ce","cf"]。
def letterCombinations(digits):
if not digits:
return []
letters = dict(zip('23456789', ['abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']))
ans = ['']
for digit in digits:
ans = [prefix + c for prefix in ans for c in letters[digit]]
return ans复杂度：长度 d：最坏时间 O(d·4^d)，含输出空间 O(d·4^d)。
易错点与适用边界：空输入的输出是 []，不是 [""]；7 和 9 有四个字母。
题意：给定互不相同的正整数候选，每个可用无限次，返回和为 target 的不重复组合。
推导与核心思路：只选择下标不小于 start 的元素保证组合顺序固定；重复使用允许递归仍从 i 开始。
走一遍：[2,3,6,7], target=7 → [[2,2,3],[7]]。
def combinationSum(candidates, target):
values = sorted(candidates)
ans, path = [], []
def dfs(start, remain):
if remain == 0:
ans.append(path.copy())
return
for i in range(start, len(values)):
x = values[i]
if x > remain:
break
path.append(x)
dfs(i, remain - x)
path.pop()
dfs(0, target)
return ans复杂度：设最小候选 a、深度 D=target/a，最坏 O(k^D·D)，输出相关；栈 O(D)。
易错点与适用边界：如果传 i+1 就错误地变为每数只能用一次；剪枝依赖候选全为正数。
题意：生成 n 对括号构成的所有合法字符串。
推导与核心思路：任意前缀中，右括号数不能多于左括号数；左括号总数不能超过 n。
走一遍：n=3 → ["((()))","(()())","(())()","()(())","()()()"]。
def generateParenthesis(n):
ans = []
def dfs(text, left, right):
if len(text) == 2 * n:
ans.append(text)
return
if left < n:
dfs(text + '(', left + 1, right)
if right < left:
dfs(text + ')', left, right + 1)
dfs('', 0, 0)
return ans复杂度：结果数为 Catalan 数 Cn，时间 O(n·Cn)，额外栈 O(n)，输出另计。
易错点与适用边界：只检查最终左右数量相等不够，例如 )( 在中途已经非法。
题意：在字符网格四方向相邻走出 word，同一格在一条路径中不可重复。
推导与核心思路：状态为当前位置和已匹配长度；临时标记当前格防止路径重用，返回前必须恢复。
走一遍：[["A","B"],["C","D"]], "ABD" → True；"ABA" → False。
def exist(board, word):
m, n = len(board), len(board[0])
def dfs(r, c, k):
if not (0 <= r < m and 0 <= c < n) or board[r][c] != word[k]:
return False
if k == len(word) - 1:
return True
old = board[r][c]
board[r][c] = None
ok = any(dfs(a, b, k + 1) for a, b in
((r-1,c),(r+1,c),(r,c-1),(r,c+1)))
board[r][c] = old
return ok
return any(dfs(r, c, 0) for r in range(m) for c in range(n))复杂度：字长 L，时间上界 O(mn·4^L)，更紧可为 O(mn·3^L)，栈 O(L)。
易错点与适用边界：不能用全局 visited 永久屏蔽格子，不同起点和不同路径可重用；即使成功也要恢复。
题意：把字符串切成若干非空段，返回每段均为回文的全部切分方案。
推导与核心思路：先用区间 DP 预计算 s[i:j+1] 是否回文，回溯时只枚举合法切割终点。
走一遍："aab" → [["a","a","b"],["aa","b"]]。
def partition(s):
n = len(s)
pal = [[False] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i, n):
pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i+1][j-1])
ans, path = [], []
def dfs(start):
if start == n:
ans.append(path.copy())
return
for end in range(start, n):
if pal[start][end]:
path.append(s[start:end+1])
dfs(end + 1)
path.pop()
dfs(0)
return ans复杂度：时间 O(n²+n·2^n)，空间 O(n²) 预处理，输出另计。
易错点与适用边界：单字符都是回文；pal 计算必须先有内部区间；切片终点 j+1 才包含 j。
题意：在 n×n 棋盘放 n 个皇后，任意两个不同行、同列、同对角线；返回全部棋盘。
推导与核心思路：逐行放一个，自然保证不同行；列 c、主对角 r-c、副对角 r+c 三个集合判断冲突。
走一遍：n=4 → 两种棋盘，列号序列 [1,3,0,2] 与 [2,0,3,1]。
def solveNQueens(n):
cols, diag1, diag2 = set(), set(), set()
path, ans = [], []
def dfs(r):
if r == n:
ans.append(['.' * c + 'Q' + '.' * (n-c-1) for c in path])
return
for c in range(n):
if c in cols or r-c in diag1 or r+c in diag2:
continue
cols.add(c); diag1.add(r-c); diag2.add(r+c)
path.append(c)
dfs(r + 1)
path.pop()
cols.remove(c); diag1.remove(r-c); diag2.remove(r+c)
dfs(0)
return ans复杂度：候选搜索上界 O(n·n!)，每个输出棋盘 O(n²)，额外搜索空间 O(n)。
易错点与适用边界：对角线的编码是 r-c 与 r+c；所有集合都必须撤销。
先把这类话说懂：二分查找是在有序或能判断答案落在哪半边的候选中，每轮排除一半。区间[l,r)含l、不含r；[l,r]两端都含。lower_bound是“第一个大于等于目标的位置”，没有这样元素时返回n。旋转排序数组如[4,5,1,2,3]，来自把递增数组前面一段挪到末尾。
二分压缩的是答案区间，不只是“数组有序”。lower_bound 找第一个大于等于目标的位置，答案可等于 n。旋转数组要先判断哪一半有序；中位数则在较短数组上二分分割点，使左右数量平衡且左最大不超过右最小。
35 搜索插入位置 · 74 搜索二维矩阵 · 34 在排序数组中查找元素的第一个和最后一个位置 · 33 搜索旋转排序数组 · 153 寻找旋转排序数组中的最小值 · 4 寻找两个正序数组的中位数
题意：有序无重复数组中，返回 target 所在位置，不存在则返回保持有序的插入位置。
推导与核心思路：寻找第一个 nums[i]≥target 的下标，使用半开区间 [l,r)。
走一遍：[1,3,5,6], target=2 → 1；target=7 → 4。
def searchInsert(nums, target):
l, r = 0, len(nums)
while l < r:
mid = (l + r) // 2
if nums[mid] < target:
l = mid + 1
else:
r = mid
return l复杂度：时间 O(log n)，空间 O(1)。
易错点与适用边界：r 初始为 n，允许答案插到数组末尾；不要混用闭区间的更新规则。
题意：每行递增，且下一行第一个数大于上一行最后一个数，判断目标是否存在。
推导与核心思路：矩阵按行展开后整体有序；逻辑下标 mid 对应行 mid//n、列 mid%n。
走一遍：[[1,3,5],[7,9,11]], target=9 → True。
def searchMatrix(matrix, target):
if not matrix or not matrix[0]:
return False
m, n = len(matrix), len(matrix[0])
l, r = 0, m * n - 1
while l <= r:
mid = (l + r) // 2
value = matrix[mid // n][mid % n]
if value == target:
return True
if value < target:
l = mid + 1
else:
r = mid - 1
return False复杂度：时间 O(log(mn))，空间 O(1)。
易错点与适用边界：与第 240 题不同，本题有跨行有序保证；行列映射用列数 n。
题意：非降序数组中返回 target 首末下标，不存在则 [-1,-1]；要求 O(log n)。
推导与核心思路：首位置是第一个 ≥target，末位置是第一个 >target 再减 1。
走一遍：[5,7,7,8,8,10], target=8 → [3,4]。
def searchRange(nums, target):
def boundary(strict):
l, r = 0, len(nums)
while l < r:
mid = (l + r) // 2
if nums[mid] < target or (strict and nums[mid] == target):
l = mid + 1
else:
r = mid
return l
first = boundary(False)
if first == len(nums) or nums[first] != target:
return [-1, -1]
return [first, boundary(True) - 1]复杂度：时间 O(log n)，空间 O(1)。
易错点与适用边界：先验证存在性；不能用线性向两边扩展，否则全重复时退化 O(n)。
题意：严格递增数组经一次旋转，返回 target 下标或 -1。
推导与核心思路：每轮左半或右半至少有一半有序；先识别有序半，再判断目标是否落在其数值范围。
走一遍：[4,5,6,7,0,1,2], target=0 → 4。
def search(nums, target):
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return mid
if nums[l] <= nums[mid]:
if nums[l] <= target < nums[mid]:
r = mid - 1
else:
l = mid + 1
else:
if nums[mid] < target <= nums[r]:
l = mid + 1
else:
r = mid - 1
return -1复杂度：时间 O(log n)，空间 O(1)。
易错点与适用边界：区间端点不等号要与 mid 已排除相配套；本题无重复，有重复时不能直接保证二分效率。
题意：无重复递增数组旋转后，找最小值。
推导与核心思路：与右端点比较：mid 更大则最小值一定在右边；否则 mid 仍可能是最小值。
走一遍：[3,4,5,1,2] → 1；[1,2,3] → 1。
def findMin(nums):
l, r = 0, len(nums) - 1
while l < r:
mid = (l + r) // 2
if nums[mid] > nums[r]:
l = mid + 1
else:
r = mid
return nums[l]复杂度：时间 O(log n)，空间 O(1)。
易错点与适用边界：保留 mid 的分支用 r=mid，不能 mid-1；未经旋转的数组也适用。
题意：两个有序数组总长非零，求合并后中位数，要求对数时间。
推导与核心思路：二分短数组切点 i，长数组切点 j 由左半应有的元素数决定；合法切分满足两侧左最大≤右最小。
走一遍：[1,3] 与 [2] → 2；[1,2] 与 [3,4] → 2.5。
def findMedianSortedArrays(a, b):
if len(a) > len(b):
a, b = b, a
m, n = len(a), len(b)
l, r = 0, m
while l <= r:
i = (l + r) // 2
j = (m + n + 1) // 2 - i
al = a[i-1] if i else float('-inf')
ar = a[i] if i < m else float('inf')
bl = b[j-1] if j else float('-inf')
br = b[j] if j < n else float('inf')
if al > br:
r = i - 1
elif bl > ar:
l = i + 1
elif (m + n) % 2:
return max(al, bl)
else:
return (max(al, bl) + min(ar, br)) / 2复杂度：时间 O(log(min(m,n)+1))，空间 O(1)。
易错点与适用边界：空数组可处理；偶数时必须除以 2；比较的是跨数组相邻边界，不是两数组各自中位数。
先把这类话说懂：栈是后进先出的待办列表，append入栈、pop出栈。单调栈额外要求栈内对应数值总是递增或递减，例如待解温度[75,71,69]递减；遇到72便可处理并弹出69和71。保存的是下标时，还可算两天距离或矩形宽度。
普通栈保存尚未闭合的语法或上下文；单调栈保存尚未找到答案的候选。温度题中弹出结点时确定“右侧第一个更高”；柱状图中弹出高度时确定其最远横向范围。栈存下标通常比只存数值更有用。
20 有效的括号 · 155 最小栈 · 394 字符串解码 · 739 每日温度 · 84 柱状图中最大的矩形
题意：只含 ()[]{} 的字符串，判断是否正确嵌套且全部闭合。
推导与核心思路：每个右括号必须匹配最近的未闭合左括号，后进先出正好用栈。
走一遍："()[]{}" → True；"([)]" → False。
def isValid(s):
pair = {')': '(', ']': '[', '}': '{'}
stack = []
for c in s:
if c in pair:
if not stack or stack.pop() != pair[c]:
return False
else:
stack.append(c)
return not stack复杂度：时间 O(n)，空间 O(n)。
易错点与适用边界：数量相等不代表有效，如 ([)]；遇空栈右括号立即失败。
题意：支持 push、pop、top、getMin，全部 O(1)，查询和弹出时栈非空。
推导与核心思路：每个栈元素同时存当前值与加入后栈的最小值；删除时历史最小值自动恢复。
走一遍：push(-2),push(0),push(-3) 后最小 -3；pop 后最小恢复 -2。
class MinStack:
def __init__(self):
self.stack = []
def push(self, val):
minimum = min(val, self.stack[-1][1]) if self.stack else val
self.stack.append((val, minimum))
def pop(self):
self.stack.pop()
def top(self):
return self.stack[-1][0]
def getMin(self):
return self.stack[-1][1]复杂度：每操作时间 O(1)，空间 O(n)。
易错点与适用边界：重复最小值也要正确保留；只存一个全局最小值无法在 pop 后恢复。
题意：将 k[内容] 展开为重复 k 次的内容，允许嵌套和多位数字，输入合法。
推导与核心思路：遇 [ 保存外层已解码前缀和重复次数，转入新层；遇 ] 把内层结果乘次数再接回外层。
走一遍："3[a2[c]]" → "accaccacc"。
def decodeString(s):
stack, text, number = [], '', 0
for c in s:
if c.isdigit():
number = number * 10 + int(c)
elif c == '[':
stack.append((text, number))
text, number = '', 0
elif c == ']':
prefix, repeat = stack.pop()
text = prefix + text * repeat
else:
text += c
return text复杂度：最终输出长 L、最大嵌套 d，本字符串版本保守时间 O(L²)，空间 O(L+d)。
易错点与适用边界：次数不只一位；不能在嵌套层覆盖外层前缀。输出很大时本身就需要对应时间内存。
题意：对每一天，返回要等待几天才能遇到更高温度，没有则为 0。
推导与核心思路：单调递减栈保存尚未找到更高日的下标；新温度更高时，弹出日的答案已确定。
走一遍：[73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0]。
def dailyTemperatures(temperatures):
ans = [0] * len(temperatures)
stack = []
for i, x in enumerate(temperatures):
while stack and temperatures[stack[-1]] < x:
j = stack.pop()
ans[j] = i - j
stack.append(i)
return ans复杂度：时间 O(n)，空间 O(n)。
易错点与适用边界：相等不是更高，不弹相等温度；剩余栈元素保持答案 0。
题意：柱子宽为 1，求全部柱子围成区域内最大的矩形面积。
推导与核心思路：单调递增高度栈中，遇到更矮柱时，弹出柱的右边界确定；新栈顶给左侧更矮边界。
走一遍：[2,1,5,6,2,3] → 10，来自高度 5、宽度 2。
def largestRectangleArea(heights):
values = heights + [0]
stack, best = [-1], 0
for i, x in enumerate(values):
while stack[-1] != -1 and values[stack[-1]] > x:
h = values[stack.pop()]
best = max(best, h * (i - stack[-1] - 1))
stack.append(i)
return best复杂度：时间 O(n)，空间 O(n)。
易错点与适用边界：宽度要减 1；栈顶弹出后再读取左边界；相等高度可保留，最终仍会算到完整宽度。
先把这类话说懂：堆是一种能快速拿出当前最小或最大元素的结构，只保证顶端极值，不保证整个列表已排序。最小堆顶是最小值；每次插入或取出后用约log n步恢复这一性质。前k大若保留[4,5,6]，最小堆顶4正是这三名里最弱的一名，新来7才值得替换它。
前 k 大用大小 k 的最小堆，堆顶是入选集合最弱的一项；中位数用两个堆把数据分成较小一半和较大一半。堆并不保证整体有序，只保证堆顶是极值。Python heapq 是最小堆，最大堆可存负数。
215 数组中的第 K 个最大元素 · 347 前 K 个高频元素 · 295 数据流的中位数
题意：找排序意义下第 k 大元素，重复值分别计数。
推导与核心思路：保留当前最大的 k 个数，最小堆堆顶就是第 k 大。
走一遍：[3,2,1,5,6,4], k=2 → 5。
def findKthLargest(nums, k):
import heapq
heap = nums[:k]
heapq.heapify(heap)
for i in range(k, len(nums)):
if nums[i] > heap[0]:
heapq.heapreplace(heap, nums[i])
return heap[0]复杂度：时间 O(n log k)，空间 O(k)。
易错点与适用边界：不是第 k 个不同值；本版优先易记和稳定性，时间 O(n log k)，不是平均线性快选。
题意：返回出现次数最高的 k 个不同元素，保证答案唯一，顺序不限。
推导与核心思路：先计频，再按频次用大小 k 的堆选取。
走一遍：[1,1,1,2,2,3], k=2 → [1,2]。
def topKFrequent(nums, k):
from collections import Counter
from heapq import nlargest
counts = Counter(nums)
return nlargest(k, counts, key=counts.get)复杂度：时间 O(n+u log k)，空间 O(u+k)，u 为不同元素数。
易错点与适用边界：不要按数值大小选；频次统计后只有 u 个候选。桶排序可进一步做到 O(n)。
题意：支持持续插入整数和随时查询中位数。
推导与核心思路：小半区用最大堆 low，大半区用最小堆 high；保持 low 元素数等于 high 或多 1，且 low 最大≤high 最小。
走一遍：插入 1,2 → 1.5；再插入 3 → 2。
class MedianFinder:
def __init__(self):
self.low, self.high = [], []
def addNum(self, num):
import heapq
heapq.heappush(self.low, -num)
heapq.heappush(self.high, -heapq.heappop(self.low))
if len(self.high) > len(self.low):
heapq.heappush(self.low, -heapq.heappop(self.high))
def findMedian(self):
if len(self.low) > len(self.high):
return -self.low[0]
return (-self.low[0] + self.high[0]) / 2复杂度：插入 O(log n)，查询 O(1)，空间 O(n)。
易错点与适用边界：low 存负数，取值要取反；空流不查询，避免未定义中位数。
先把这类话说懂：贪心是每步立即作一个局部选择，不回头枚举所有组合；正确前提是这个选择不会挡住某个更优答案。“支配”指一个候选在所有后续情况下都不差于另一个；“交换论证”是把最优方案的第一步换成贪心这一步，证明总结果不变差。
贪心能省掉 DP 状态，但必须有支配或交换论证。股票只需此前最低价；跳跃只需最远可达范围；最少跳跃按可达区间分层；字母区间只有收集完当前出现字母的最后位置才可切分。
121 买卖股票的最佳时机 · 55 跳跃游戏 · 45 跳跃游戏 II · 763 划分字母区间
题意：最多完成一次先买后卖交易，返回最大利润，允许不交易。
推导与核心思路：固定卖出日，最优买入价是此前的最低价。
走一遍：[7,1,5,3,6,4] → 5，在 1 买、6 卖。
def maxProfit(prices):
low, best = float('inf'), 0
for price in prices:
low = min(low, price)
best = max(best, price - low)
return best复杂度：时间 O(n)，空间 O(1)。
易错点与适用边界：不能用未来最低价配过去卖价；价格单调下降时返回 0。
题意：nums[i] 是从 i 最远可跳的步数，判断从 0 能否到末尾。
推导与核心思路：在已可达区域内，维护能扩展的最远位置；若当前下标已超过最远位置则不可达。
走一遍：[2,3,1,1,4] → True；[3,2,1,0,4] → False。
def canJump(nums):
reach = 0
for i, step in enumerate(nums):
if i > reach:
return False
reach = max(reach, i + step)
return True复杂度：时间 O(n)，空间 O(1)。
易错点与适用边界：不能用最后一步恰好落在末尾作条件，可以选择小于最大步数的跳跃。
题意：保证能到末尾，求最少跳跃次数。
推导与核心思路：当前跳数可到达的区间是一层，扫描整层后选择下一层最远边界，相当于压缩后的 BFS。
走一遍：[2,3,1,1,4] → 2，可按 0→1→4 跳。
def jump(nums):
end = farthest = jumps = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == end:
jumps += 1
end = farthest
return jumps复杂度：时间 O(n)，空间 O(1)。
易错点与适用边界：不要扫描末尾后再多加一次；不能每步只跳到 nums[i] 最大的位置，要比较 i+nums[i]。
题意：把字符串切成尽可能多段，使每个字符只出现在一段中，返回每段长度。
推导与核心思路：段内任意字符最后出现的位置都必须包含；不断扩展当前段终点，扫描点到达终点时才能切。
走一遍："ababcbacadefegdehijhklij" → [9,7,8]。
def partitionLabels(s):
last = {c: i for i, c in enumerate(s)}
start = end = 0
ans = []
for i, c in enumerate(s):
end = max(end, last[c])
if i == end:
ans.append(end - start + 1)
start = i + 1
return ans复杂度：时间 O(n)，空间 O(字符集大小)。
易错点与适用边界：不能遇到字符第一次重复就切；只有所有段内字符均不再出现时才安全。
先把这类话说懂：DP是前文的动态规划；线性指按一排位置从前向后计算。有限状态指每个位置只需几种含义明确的数字，例如“以这里结尾的最大乘积/最小乘积”，而非记住此前所有子数组。“互斥选择”就是每个答案只属于一种分支，不重复相加。
动态规划先写状态的中文含义，再列最后一步的互斥选择，最后写初始化和计算顺序。爬楼梯按最后一步分解；打家劫舍按最后一家是否偷分解；乘积最大子数组需要最大和最小两个状态，因为乘负数会交换大小。滚动数组只在理解完整状态依赖后使用。
70 爬楼梯 · 118 杨辉三角 · 198 打家劫舍 · 152 乘积最大子数组 · 32 最长有效括号
题意：每次可走 1 或 2 阶，问到达第 n 阶有多少种不同走法。
推导与核心思路：到第 i 阶的最后一步要么从 i-1 走 1 阶，要么从 i-2 走 2 阶，两类不重叠，所以 f[i]=f[i-1]+f[i-2]。
走一遍：n=4：f0=1,f1=1,f2=2,f3=3,f4=5；最后一步分成 3+2 种。
def climbStairs(n):
a, b = 1, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b复杂度：时间 O(n)，额外空间 O(1)。
易错点与适用边界：f[0]=1 是计数的单位元；若误设为 0，会少算从起点一次走 2 阶的路径。
题意：返回杨辉三角前 numRows 行，每行两端为 1，中间等于上一行相邻两项之和。
推导与核心思路：状态 row[i][j] 表示第 i 行第 j 项，转移只依赖上一行 j-1 与 j。
走一遍：5 行 → [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]。
def generate(numRows):
ans = []
for i in range(numRows):
row = [1] * (i + 1)
for j in range(1, i):
row[j] = ans[-1][j-1] + ans[-1][j]
ans.append(row)
return ans复杂度：时间 O(r²)，输出空间 O(r²)，r=numRows。
易错点与适用边界：边界不能访问上一行越界位置；每行要新建列表，避免多行共享同一对象。
题意：一排房屋各有非负金额，不能偷相邻两家，求最多金额。
推导与核心思路：设 f[i] 为前 i 家最优。最后一家不偷得 f[i-1]；偷则前一家不能偷，得 f[i-2]+nums[i-1]。
走一遍：[2,7,9,3,1]：逐步最优 2,7,11,11,12，最终选 2+9+1。
def rob(nums):
prev2 = prev1 = 0
for x in nums:
prev2, prev1 = prev1, max(prev1, prev2 + x)
return prev1复杂度：时间 O(n)，空间 O(1)。
易错点与适用边界：选择“偷第 i 家”时接的是前 i-2 家最优，不是简单把奇数或偶数位置相加。
题意：非空整数数组中求非空连续子数组的最大乘积。
推导与核心思路：必须以当前数结尾的最大积 hi 与最小积 lo 同时维护；负数乘 lo 可变成最大正数。
走一遍：[-2,3,-4]：读 3 后 hi=3,lo=-6；再乘 -4 得 hi=24。
def maxProduct(nums):
hi = lo = best = nums[0]
for i in range(1, len(nums)):
x = nums[i]
hi, lo = max(x, hi*x, lo*x), min(x, hi*x, lo*x)
best = max(best, hi)
return best复杂度：时间 O(n)，空间 O(1)。
易错点与适用边界：不能先改 hi 再用新 hi 算 lo；0 会自然重启，不需要删除 0。
题意：只含左右括号的字符串，求最长合法连续子串长度。
推导与核心思路：dp[i] 为以 i 结尾的最长合法段。仅 s[i] 为右括号才可能非零；跳过紧邻合法段后，检查前一个字符能否与当前配对。
走一遍：")()())" → 4；"()(())" 末位跨过内部 () 后匹配，再接左边 ()，得 6。
def longestValidParentheses(s):
dp = [0] * len(s)
best = 0
for i in range(1, len(s)):
if s[i] == ')':
j = i - dp[i-1] - 1
if j >= 0 and s[j] == '(':
dp[i] = dp[i-1] + 2 + (dp[j-1] if j > 0 else 0)
best = max(best, dp[i])
return best复杂度：时间 O(n)，空间 O(n)。
易错点与适用边界：必须把相邻合法段接上，例如 ()()；j<0 要先判断，避免 Python 负下标误读尾部。
先把这类话说懂：背包只是把限制想成容量：有目标金额6，每选一个值2便占去2容量。完全背包允许同一个元素用多次，0/1背包只允许每个输入元素选或不选一次。可行性只问能否做到，用True/False；最优化问最少几次，用min；计数则把所有不同方案相加。
容量 DP 问“恰好达到状态 i 时，最少几步/是否可行”。完全背包允许重复选择，金额从小到大；0/1 背包每项最多一次，压缩后容量倒序。单词拆分把每个可匹配单词视为一条从前缀 j 到 i 的边。区分求最小值、求可行性和求方案数，初始化与聚合运算不同。
279 完全平方数 · 322 零钱兑换 · 416 分割等和子集 · 139 单词拆分
题意：正整数 n，求和为 n 的完全平方数的最少数量，平方数可重复使用。
推导与核心思路：dp[i] 为凑成 i 的最少数量；最后选 j²，则来自 dp[i-j²]+1，对所有平方数取最小。
走一遍：n=12：最大平方贪心 9+1+1+1 共 4 个，DP 找到 4+4+4 共 3 个。
def numSquares(n):
dp = [0] + [float('inf')] * n
for i in range(1, n + 1):
j = 1
while j * j <= i:
dp[i] = min(dp[i], dp[i - j*j] + 1)
j += 1
return dp[n]复杂度：时间 O(n√n)，空间 O(n)。
易错点与适用边界：允许平方数重复，例如 12=4+4+4；不是贪心地每次取最大平方数。
题意：每种正面额硬币无限枚，求凑成 amount 的最少硬币数，无法凑成返回 -1。
推导与核心思路：dp[x] 表示恰好凑成 x 的最少枚数；最后一枚面额 c，则候选 dp[x-c]+1。
走一遍：[1,2,5], amount=11 → 3，最后一枚可选 1/2/5，最优为 5+5+1。
def coinChange(coins, amount):
dp = [0] + [amount + 1] * amount
for total in range(1, amount + 1):
for c in coins:
if c <= total:
dp[total] = min(dp[total], dp[total-c] + 1)
return dp[amount] if dp[amount] <= amount else -1复杂度：时间 O(amount·k)，空间 O(amount)。
易错点与适用边界：这是最少枚数，不是组合数；[2],amount=3 必须 -1；金额 0 需要 0 枚。
题意：正整数数组能否分成两个元素和相等的子集，每元素恰用一次。
推导与核心思路：总和必须为偶数；问题化为 0/1 背包能否恰好装满 total/2。dp[s] 表示使用已扫描元素能否凑出 s。
走一遍：[1,5,11,5] → True；一组 [11]，另一组 [1,5,5]。
def canPartition(nums):
total = sum(nums)
if total % 2:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for x in nums:
for s in range(target, x - 1, -1):
dp[s] = dp[s] or dp[s-x]
return dp[target]复杂度：时间 O(n·S)，空间 O(S)，S=总和/2。
易错点与适用边界：容量必须倒序，保证 dp[s-x] 来自加入 x 之前；正序会把同一元素重复使用。
题意：判断 s 能否由字典中若干非空单词连接而成，单词可重复。
推导与核心思路：dp[i] 表示前 i 个字符可被完全拆分；若某词 w 是以 i 结尾的后缀，且 dp[i-len(w)] 成立，就能转移到 i。
走一遍："leetcode", ["leet","code"]：dp[4] 由 dp[0] 转移，dp[8] 由 dp[4] 转移。
def wordBreak(s, wordDict):
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for word in wordDict:
length = len(word)
if i >= length and dp[i-length] and s[i-length:i] == word:
dp[i] = True
break
return dp[-1]复杂度：字典 k 词、最大词长 L：时间 O(nkL)，空间 O(n)。
易错点与适用边界：“出现过字典里的词”不等于整个字符串能覆盖；不能漏掉 dp[0]。
先把这类话说懂：子串必须连续，例如abcde中的bcd；子序列可以跳字符但不能换顺序，例如ace。LIS是“最长严格递增子序列”，LCS是“两串的最长公共子序列”。区间DP把一段起终点作为状态；二维前缀DP用“第一串前i项、第二串前j项”作状态，依赖较短前缀的答案。
连续子串不能跳字符，子序列允许跳。LIS 用“长度相同，末尾越小越容易续接”的支配关系压缩状态；最长回文子串按内部区间递推；LCS 和编辑距离按两个前缀对齐。二维 DP 先明确 dp[i][j] 对应前 i 个/前 j 个元素，避免状态下标和字符下标混淆。
300 最长递增子序列 · 5 最长回文子串 · 1143 最长公共子序列 · 72 编辑距离
题意：求严格递增子序列的最长长度，不要求连续。
推导与核心思路：基础 DP：f[i]=1+max(f[j])，其中 j<i 且 nums[j]<nums[i]。优化保存 tails[len-1] 为该长度递增序列的最小结尾；新 x 替换第一个≥x 的结尾。
走一遍：[10,9,2,5,3,7,101,18]：tails 最终 [2,3,7,18]，长度 4。
def lengthOfLIS(nums):
from bisect import bisect_left
tails = []
for x in nums:
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = x
return len(tails)复杂度：时间 O(n log n)，空间 O(n)；基础 DP 为 O(n²)。
易错点与适用边界：严格递增应找 ≥x，重复数不能增加长度；tails 的值序列不一定是原数组中的同一条实际子序列。
题意：求最长的连续回文子串，若并列可返回任意一个。
推导与核心思路：区间 DP 定义 pal[l][r]=(s[l]=s[r]) 且（长度≤2 或 pal[l+1][r-1]）。等价的中心扩展从单字符和字符间隙出发，省去整张表。
走一遍："babad" → "bab" 或 "aba"；"cbbd" → "bb"，必须考虑偶数中心。
def longestPalindrome(s):
start = length = 0
for i in range(len(s)):
for l, r in ((i, i), (i, i+1)):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
if r - l - 1 > length:
start, length = l + 1, r - l - 1
return s[start:start+length]复杂度：时间 O(n²)，额外空间 O(1)（不计返回字符串）。
易错点与适用边界：退出循环时 l、r 已越出合法回文，正确区间是 [l+1,r)，长度 r-l-1。
题意：两个字符串中找最长的公共子序列长度，字符可不连续但相对顺序不变。
推导与核心思路：dp[i][j] 表示两个前缀的 LCS。末字符相同则 dp[i-1][j-1]+1；不同则舍弃一边末字符取 max(dp[i-1][j],dp[i][j-1])。
走一遍："abcde" 与 "ace" → 3；ace 可以跳过 b、d。
def longestCommonSubsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]复杂度：时间 O(mn)，空间 O(mn)，可滚动压成 O(min(m,n))。
易错点与适用边界：不是最长公共子串，不同时不能直接清零；字符访问用 i-1,j-1。
题意：用插入、删除、替换，每步代价 1，把 word1 变成 word2 的最少操作数。
推导与核心思路：dp[i][j] 是两个前缀的转换代价。末字符相等时沿对角；否则在删除 dp[i-1][j]、插入 dp[i][j-1]、替换 dp[i-1][j-1] 中取最小再加 1。
走一遍："horse"→"ros"：替换 h→r、删掉第三位 r、删 e，共 3 步。
def minDistance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(m+1):
dp[i][0] = i
for j in range(n+1):
dp[0][j] = j
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], dp[i][j-1], dp[i-1][j-1])
return dp[m][n]复杂度：时间 O(mn)，空间 O(mn)，可滚动压缩。
易错点与适用边界：不同字符时三种操作不能漏；相同字符直接沿对角，不额外加 1。
先把这类话说懂：网格DP把每格的答案写在同尺寸表里。只能右走或下走意味着不会走回已处理行列，依赖不会形成环。二维表可逐行压成一行，更新前的dp[j]还是上面格子的值，更新后的dp[j-1]则是左边格子的值；计数相加，路径代价则先取min再加本格。
网格只能向右或向下时，依赖图无环，每格只由上方和左方转移。计数题用加法，最短代价用 min 后加当前权重。滚动行中 dp[j] 更新前是上方，dp[j-1] 更新后是左方；循环方向就是状态语义的一部分。
题意：m×n 网格从左上走到右下，每步只能向右或向下，求路径条数。
推导与核心思路：到 (i,j) 的最后一步只有从上或从左两种，故 ways[i][j]=ways[i-1][j]+ways[i][j-1]。首行首列各只有 1 条路。
走一遍：m=3,n=3：首行 [1,1,1]，第二行 [1,2,3]，第三行 [1,3,6]。
def uniquePaths(m, n):
dp = [1] * n
for _ in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1]
return dp[-1]复杂度：时间 O(mn)，空间 O(n)。
易错点与适用边界：不能把 dp[0] 改成 0，第一列仍只有一种走法；m,n 的 1×n 边界应返回 1。
题意：非负权重网格，只能右移或下移，求左上到右下的最小权重和，含起终点。
推导与核心思路：dp[i][j]=grid[i][j]+min(上方最优,左方最优)，最优子结构来自最后一步只有两个来源。
走一遍：[[1,3,1],[1,5,1],[4,2,1]] → 7，路径 1→3→1→1→1。
def minPathSum(grid):
n = len(grid[0])
dp = [float('inf')] * n
for i, row in enumerate(grid):
for j, value in enumerate(row):
if i == 0 and j == 0:
dp[j] = value
else:
left = dp[j-1] if j else float('inf')
dp[j] = value + min(dp[j], left)
return dp[-1]复杂度：时间 O(mn)，空间 O(n)，不修改输入。
易错点与适用边界：边界不存在的来源应设无穷，而非 0；起点不能重复累加。
先把这类话说懂：异或^逐二进制位计算，同位相同为0、不同为1，所以x^x=0。投票通过配对抵消不同数，找数量超过一半的元素。分区是把数组划成几段、每段只放某类数；荷兰旗是0/1/2三段。字典序像查字典，从左找到第一个不同位置决定大小；函数图则把“下标i连到nums[i]”当成一条有向边。
技巧不是背口令：异或抵消要求成对出现；投票要求多数元素确实存在；荷兰旗维护三个已分类区间；下一个排列只改变尽可能靠右的后缀；找重复数把数组下标看作函数图结点，重复值对应环入口。
136 只出现一次的数字 · 169 多数元素 · 75 颜色分类 · 31 下一个排列 · 287 寻找重复数
题意：除一个元素只出现一次外，其余均恰出现两次，找单个元素。
推导与核心思路：异或满足 x^x=0、x^0=x、结合交换律，成对元素全部抵消。
走一遍：[4,1,2,1,2] → 4，因为 1 与 2 各抵消一次。
def singleNumber(nums):
ans = 0
for x in nums:
ans ^= x
return ans复杂度：时间 O(n)，空间 O(1)。
易错点与适用边界：如果其他元素出现三次，这个方法不成立；负整数在 Python 中也可用异或抵消。
题意：保证有一个元素出现次数大于 n/2，返回它。
推导与核心思路：Boyer–Moore 投票每次抵消一对不同元素，多数元素的剩余票不可能被全部抵消。
走一遍：[2,2,1,1,1,2,2] → 2，票数抵消后候选仍为 2。
def majorityElement(nums):
candidate, count = None, 0
for x in nums:
if count == 0:
candidate = x
count += 1 if x == candidate else -1
return candidate复杂度：时间 O(n)，空间 O(1)。
易错点与适用边界：如果题目不保证多数存在，必须再扫描计数验证；不要把“众数”与超过一半的多数混同。
题意：只含 0、1、2 的数组，一趟原地排成 0 区、1 区、2 区。
推导与核心思路：维护 [0,low) 为 0，[low,i) 为 1，(high,n) 为 2，[i,high] 未知。
走一遍：[2,0,2,1,1,0] → [0,0,1,1,2,2]。
def sortColors(nums):
low = i = 0
high = len(nums) - 1
while i <= high:
if nums[i] == 0:
nums[low], nums[i] = nums[i], nums[low]
low += 1
i += 1
elif nums[i] == 2:
nums[i], nums[high] = nums[high], nums[i]
high -= 1
else:
i += 1复杂度：时间 O(n)，空间 O(1)。
易错点与适用边界：交换过来的末尾元素尚未分类，遇 2 后不能立刻 i++；这是最常见漏元素原因。
题意：原地改为字典序紧邻的下一个排列；若已最大则变为最小。
推导与核心思路：尽量保持左侧不变：从右找到首个上升对的左元素 pivot，以右侧刚好更大的数替换，再把降序后缀反转成最小。
走一遍：[1,3,2] → [2,1,3]；[3,2,1] → [1,2,3]。
def nextPermutation(nums):
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i+1]:
i -= 1
if i >= 0:
j = len(nums) - 1
while nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
l, r = i + 1, len(nums) - 1
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1复杂度：时间 O(n)，空间 O(1)。
易错点与适用边界：比较必须严格；全降序时 i=-1，反转整个数组；重复值也能正确处理。
题意：长度 n+1 的数组，每项在 1..n，只有一个重复值但可多次出现；不改数组、O(1) 空间找它。
推导与核心思路：把 i→nums[i] 看成函数图。从 0 出发必入环；0 无入边，重复值对应路径进入环的结点，使用 Floyd 找入口。
走一遍：[1,3,4,2,2] → 函数路径 0→1→3→2→4→2，入口 2 即重复数。
def findDuplicate(nums):
slow = fast = 0
while True:
slow, fast = nums[slow], nums[nums[fast]]
if slow == fast:
break
entry = 0
while entry != slow:
entry, slow = nums[entry], nums[slow]
return entry复杂度：时间 O(n)，空间 O(1)，不修改输入。
易错点与适用边界：这是数值作为下一结点下标，不是对数组排序；值域 1..n 和 n+1 长度是论证关键。
题目范围对应力扣“LeetCode 热题 100”学习计划，100 个题号与类别覆盖该计划的当前公开清单；为帮助迁移学习，本书将动态规划重新细分为四类，并保留每题官方题面链接。题意是必要条件的原创自述，代码与教学步骤为独立编写，并非官方题解逐字转录。平台可能调整题单、限制或函数签名，练习时以对应官方题面为准。题目测试通过代表用例与小规模交叉检查，不能替代完整平台隐藏用例评测。