LeetCode Hot 100
用模式压缩记忆，用不变量解释代码

先补最少的基础：能看懂代码，再学解题模式

这一节从零约定本书的语言。先看数组 [2,7,11]：它有3个元素，下标从0开始，nums[0] 是2、nums[1] 是7。问题说“返回下标”，答案便是0和1；说“返回数值”，才是2和7。下标是位置，值是位置里装的内容，两者不能混用。

1. 变量、条件与循环：程序怎样一步步执行

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。

2. 列表、字典和集合：分别解决什么问题

列表 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时要先判断边界，不能误把不存在的前驱当末项。

3. 引用、链表与树：为什么值一样不等于同一个结点

列表变量指向一个对象：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的字段。

4. 函数、递归、栈与队列：暂存的到底是什么

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() 删除。不要把栈、队列与递归当成三个新算法，它们首先是不同的待办顺序：最新的先做，或最早的先做。

5. 状态、不变量与动态规划：把术语换成可以检查的话

状态 是“此刻记住哪些信息，就足以继续计算”。例如当前读到第3项、此前总和5，便可用5继续加下一项；不必把前三项反复重加。不变量 是“每轮开始或结束都保证成立的事实”。移动零时可说“写指针w之前恰好存着已读到的全部非零数”，每写入一项就检查它仍成立；它用来解释代码为什么不会漏、乱或重复。

动态规划（DP） 把相同的小问题答案存起来，让大问题直接复用。比如到第4阶的最后一步，要么从第3阶走1步，要么从第2阶走2步，因此 f[4]=f[3]+f[2]。这里“状态”是到第i阶的方案数f[i]，“转移”是由旧答案算新答案的规则；“初始化”给最小问题答案。滚动数组 只是当新答案仅依赖前两项时，只保留那两项而不保存整张表，并非另一种推导。

6. 大 O：看输入扩大后，操作次数怎样增长

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 道代表题，再用同类变体检查边界。目录按模式分组，题号保留官方编号，便于对照练习。

1. 第一轮：只读“题意→推导→走一遍”，遮住代码，口头说明状态与不变量。
2. 第二轮：按步骤独立写代码，拿空/单元素、重复值、全负数、最短边界检查。
3. 第三轮：改变约束：能否含负数？能否重复选？要求连续还是子序列？根据失效条件切换模式。

学完后回来看：五组可以一起记的题

• 两数之和 → 前缀和计数 → 树上的路径总和：都是“当前累积值减目标，再查询此前出现过的值”；树题退出某条分支时还需撤销该分支的记录。
• 二叉树深度 → 直径 → 最大路径和：向父结点返回一条向下路线的贡献，整棵树的最佳答案则可以在某结点处连接左右两条。
• 每日温度 → 柱状图矩形 → 窗口最大值：删去以后再也不必保留的候选，分别在等到更高温、遇到更矮柱、或离开窗口时处理它。
• 爬楼梯 → 零钱兑换 → 分割等和：都按最后一步拆问题，计算规则分别是相加、取最少、判断能否做到；允许同一项重复使用与否，决定能否读本轮刚更新的状态。
• 最长公共子序列（LCS）→ 编辑距离：都比较“第一串前i字与第二串前j字”，一个求最多保留多少共同字，一个求最少改动多少次。

代码约定与复杂度记法

代码使用 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 适合离线通读，在线版方便按锚点跳转。