去年冬天我把左程云的算法笔记重新翻出来刷了一遍起因很朴素面试里被一道看着像二分、写起来像模拟的题卡了四十分钟回来一查发现这道题的骨架在他基础篇里就讲过只是当时我看完就划过去了。这次重刷我做了很多笔记之外的事——把每类问题的判定入口单独抄成一页把对数器写成了固定模板把踩过的边界坑记在代码注释里。这篇就是我这一轮复盘下来的东西主要面向刚开始系统学算法、或者刷了几十道题但总觉得脑子里没骨架的人。左程云的算法笔记基础篇覆盖的东西不算花哨复杂度分析、排序、二分、位运算、链表、二叉树、字符串匹配、贪心但你真按顺序走一遍会发现它不是知识点清单而是一套遇到陌生题从哪下嘴的方法论。我下面不会按课程顺序复述而是按我自己重新理解了一遍的路径来写。每个模块我都会说清楚三件事这个东西解决的是哪一类问题、我当初在哪一步理解错了、现在我会怎么用。代码统一给 Java因为原笔记是 Java 体系习惯 Python 的读者把数组和下标逻辑看明白就行换语言只是语法成本。1. 复杂度不是背出来的是从数据规模反推出来的1.1 先看 n 的量级再决定敢不敢写双重循环我见过太多人写完代码才去算复杂度其实顺序应该反过来。左程云在基础篇反复强调的一件事是看到题目先看数据范围数据范围直接告诉你哪一档算法是够用的。这一步做对了你至少不会在 n 10⁵ 的题上写 O(n²) 然后对着超时提示发呆。我把这套反查关系整理成了表做题时扫一眼就能定位数据规模 n时间预算 1 秒内可接受的复杂度这时你该想到的解法形态n ≤ 20O(2ⁿ)、O(n!)暴力枚举、状态压缩、全排列n ≤ 100O(n³) 或 O(n⁴)三重循环 DP、Floydn ≤ 2000O(n²)二维 DP、朴素配对、双重循环n ≤ 10⁵O(n log n)排序、二分、堆、归并思想n ≤ 10⁶O(n)一次遍历、前缀和、双指针、单调栈n ≤ 10⁸O(n) 且常数极小位运算、简单计数慎用容器这张表的用法不是死记而是形成条件反射。我现在读题的第一分钟不做别的就盯着数据范围看然后用它排除掉一整片不合适的思路。排除法的价值比想到正确解法高得多因为它能把搜索空间从几十种压到两三种。提示数据范围是出题人给你的最大善意。n 写 10⁵ 基本等于在明示别写 n²n 写 20 基本等于在明示随便暴力。忽略这个信号等于主动放弃一条捷径。1.2 常数项、递归展开和看起来一样其实差一倍复杂度只描述增长趋势但工程实现里常数项是真实存在的。基础篇里有一段容易被跳过同样的 O(n log n)归并排序要额外开数组拷贝快速排序基本原地交换在 n 10⁶ 这个量级上两者的实测差距能有 30% 以上。这不是复杂度理论错了而是理论不负责常数。递归的时间复杂度估算我用的是最朴素的三步法写出递归式、算出每层的总工作量、用 master 公式或者画递归树定档。以归并排序为例规模 N 的问题拆成两个 N/2 的子问题合并那一步要扫一遍整个区间于是T(N) 2 * T(N/2) O(N)每层总工作量都是 O(N)一共 log N 层结论就是 O(N log N)。这个推导的价值在于当你以后看到拆两半 线性合并的结构你会直接条件反射出 N log N而不是每次重推一遍。空间复杂度方面我踩过一个很典型的坑写递归函数时只算了递归栈的深度忘了每层里开的临时数组。递归栈深度是 O(log N)但所有层的临时数组加起来峰值也是 O(N)实际占用比直觉高一截。后来我养成一个习惯递归函数里凡是开了堆上对象都在注释里标一句这层的额外空间是多少。1.3 对数器把我觉得对了换成它确实对了如果只让我从左程云的算法笔记里挑一个最有价值的工具我选对数器。它的思路简单到粗暴写一个绝对正确但可能很慢的暴力解再写一个你优化后的解用随机数据大量对撞只要有一组输出不一致就说明优化版有 bug。对数器的骨架我固定成了下面这样每次换题只改排序函数和比较逻辑// 1. 随机样本生成器可以生成重复值、负数、边界长度 public static int[] generateRandomArray(int maxSize, int maxValue) { int[] arr new int[(int) ((maxSize 1) * Math.random())]; for (int i 0; i arr.length; i) { arr[i] (int) ((maxValue 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } // 2. 拷贝工具保证两个解法吃到的输入完全一样 public static int[] copyArray(int[] arr) { if (arr null) return null; int[] res new int[arr.length]; for (int i 0; i arr.length; i) res[i] arr[i]; return res; } // 3. 主流程小样本高频对撞 public static void main(String[] args) { int testTime 500000; int maxSize 100; int maxValue 100; boolean succeed true; for (int i 0; i testTime; i) { int[] arr1 generateRandomArray(maxSize, maxValue); int[] arr2 copyArray(arr1); yourSort(arr1); // 你的解法 bruteForceSort(arr2); // 绝对正确的暴力解 if (!isEqual(arr1, arr2)) { succeed false; printArray(arr1); printArray(arr2); break; } } System.out.println(succeed ? Nice! : Fucking fucked!); }这个模板的杀伤力在于它能抓出你自己根本想不到的 case。我曾经在一个局部最小值的题上自认为边界处理得很好对数器跑了不到两千次就抓到一组长度为 2 且两个数相等的数组——我从头到尾没考虑过重复元素。人工构造测试用例时人是会护着自己思路的随机对撞不会。提示对数器的样本量要小规模、高次数。maxSize 控制小一点循环次数拉大比一次性跑几个大数据更能暴露逻辑漏洞。另外记住先写暴力解哪怕它慢得像 O(n³)因为暴力解本身也是你的题目理解检查器。2. 排序这一关真正值钱的不是代码本身2.1 三个 O(n²) 排序是理解有序区概念的起点冒泡、选择、插入这三个算法很多人背完就扔但左程云讲它们的顺序不是按难度而是按有序区的形成方式来编排的。冒泡每一次外层循环把最大值冒到末尾有序区从右往左长选择排序每次找出剩余部分的最小值有序区从左往右长插入排序则是维护左侧一段有序区每次把新的元素插到正确位置。插入排序有个性质值得单独记住当数据接近有序时它的实际表现会退化到接近 O(n)因为内层交换次数很少。这就是为什么很多工业级排序在数据规模小比如 16 个元素以下时会退化成插入排序——常数小、缓存友好、几乎有序时极快。public static void insertionSort(int[] arr) { if (arr null || arr.length 2) return; for (int i 1; i arr.length; i) { // 向左找位置只要左边比自己大就交换 for (int j i - 1; j 0 arr[j] arr[j 1]; j--) { swap(arr, j, j 1); } } }注意这个写法的内层循环条件是arr[j] arr[j1]而不是arr[j] arr[i]。新手很容易写成后者然后在下标处理上绕半天。用相邻交换的写法虽然多几次赋值但边界逻辑简单不容易错。2.2 归并排序分治的第一次真正交手归并排序是基础篇里我花时间最多的部分不是因为代码难而是它带出了分治这个可以套用到无数题上的思维框架。它的结构就是三行拆半、递归、合并。public static void mergeSort(int[] arr) { if (arr null || arr.length 2) return; process(arr, 0, arr.length - 1); } private static void process(int[] arr, int l, int r) { if (l r) return; int mid l ((r - l) 1); // 这样写不会溢出 process(arr, l, mid); process(arr, mid 1, r); merge(arr, l, mid, r); } private static void merge(int[] arr, int l, int m, int r) { int[] help new int[r - l 1]; int i 0, p1 l, p2 m 1; while (p1 m p2 r) { help[i] arr[p1] arr[p2] ? arr[p1] : arr[p2]; } while (p1 m) help[i] arr[p1]; while (p2 r) help[i] arr[p2]; for (i 0; i help.length; i) arr[l i] help[i]; }这里mid l ((r - l) 1)的写法必须养成习惯。用(l r) / 2在 l 和 r 都接近整数上限时会溢出成负数进而在某些语言里直接导致数组越界。这种 bug 在本地小数据上永远复现不了一旦上线就炸。归并思想真正的价值在后面小和问题、逆序对问题、区间内个数统计本质上都是在 merge 那一步顺手统计跨左右两半的信息。我最初做小和问题时死活想不通为什么在 merge 里累加是对的后来画了一次递归树才明白——每次 merge 处理的是右半部分某个元素与左半部分所有比它小的元素的贡献而每一对 (i, j) 只会在某一次 merge 中被统计一次既不重不漏。2.3 快速排序随机化 pivot 解决了什么快速排序的核心是 partition。基础篇里讲的是荷兰国旗版本的三分法把数组分成小于区、等于区、大于区这一步对重复元素极其友好因为等于区一次成型后续递归不再碰。// 返回等于区的左右边界 public static int[] netherlandsFlag(int[] arr, int l, int r) { if (l r) return new int[]{-1, -1}; if (l r) return new int[]{l, r}; int less l - 1, more r, index l; while (index more) { if (arr[index] arr[r]) swap(arr, less, index); else if (arr[index] arr[r]) swap(arr, index, --more); else index; } swap(arr, more, r); return new int[]{less 1, more}; }为什么要在 partition 之前随机挑一个位置和末尾交换因为固定选末尾作为基准时遇到已经有序的数组会退化成 O(n²)每次只搞定一个元素。随机化之后最坏情况在数学上仍然存在但概率极低期望复杂度稳定在 O(n log N)。我用对数器专门验证过这一点不随机化时输入一个升序数组递归深度直接到 n在某些语言里会栈溢出。提示快排的随机不是为了让平均更快而是为了打散输入分布把最坏情况从你一定会遇到变成理论上存在但几乎遇不到。这是算法设计里一个很典型的手法——用随机性换稳定性。2.4 堆结构heapInsert 与 heapify 的分工堆在基础篇里出现得很早讲得也细。它是一棵完全二叉树用数组存下标关系是父节点 i 的左孩子 2i1右孩子 2i2。所有操作就靠两个动作支撑// 新元素上浮用于建堆、往堆里加元素 public static void heapInsert(int[] arr, int index) { while (arr[index] arr[(index - 1) / 2]) { swap(arr, index, (index - 1) / 2); index (index - 1) / 2; } } // 元素下沉用于堆顶被取走后重新调整 public static void heapify(int[] arr, int index, int heapSize) { int left index * 2 1; while (left heapSize) { int largest left 1 heapSize arr[left 1] arr[left] ? left 1 : left; largest arr[largest] arr[index] ? largest : index; if (largest index) break; swap(arr, index, largest); index largest; left index * 2 1; } }这两个函数的分工很容易搞混heapInsert是自下而上修复heapify是自上而下修复。建堆用哪个两种都能建但heapify从最后一个非叶节点往前扫整体复杂度是 O(n)而heapInsert一个个插入是 O(n log n)。这个建堆可以做到 O(n)的结论在面试里被问到的频率不低理由是越靠近底层的节点越多但它们的下沉距离越短加权求和后收敛到 O(n)。堆排序的做法是把堆顶和末尾交换堆大小减一再对堆顶做一次 heapify。至于优先队列Java 的PriorityQueue默认是小根堆要大根堆就传Comparator反转或者自己往里面塞相反数。手写堆的意义在于你能实现改堆中某个元素的值这种优先队列不提供的操作。2.5 稳定性工程上和理论上是两个问题排序的稳定性在纯算法题里不怎么考但在真实系统里是硬要求。所谓稳定就是相等元素的相对顺序在排序后保持不变。你给一批订单按金额排序金额相同的那些原本按时间排好的顺序不能被打破否则用户看到的列表会莫名跳动。排序算法平均时间最坏时间额外空间是否稳定冒泡排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定归并排序O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(1)不稳定记忆的技巧是抓住交换方式凡是跳跃式交换的选择、快排、堆排都可能把相等元素甩到后面去因此不稳定凡是相邻交换或者额外数组归并的通常稳定。归并排序是唯一同时满足 O(n log n) 和稳定的通用排序这也是它在实际工程中被大量使用的原因。Java 里对象数组排序用的是归并的变体TimSort保证稳定基本类型数组用的是双轴快排不保证稳定但更快。这个区别不是随手写的是因为基本类型没有身份概念两个相等的 int 谁在前谁在后无所谓而对象通常有关联的其他字段顺序就变得有意义了。3. 二分法的本质是单调性不是有序数组3.1 判定函数把二分答案翻译成人话我一开始对二分的理解停留在有序数组里找某个数直到做了一道求最小可行容量的题才开窍。二分真正的适用条件是存在一个判定函数 f(x)使得 f(x) 随着 x 增大呈现出单一方向的变化先假后真或者先真后假。数组有序只是这个条件的一个特例——因为下标 i 处的值是否小于目标值这个判定函数是单调的。把这个抽象套回具体问题你会发现一大批看起来不像二分的题都能二分求平方根的整数部分、找最小耗时、求最大可分配的最小值、找峰值、找局部最小值。解题的关键变成两步一是写出判定函数二是确定答案的搜索范围。判定函数写完之后模板就固定了// 求满足 check(x) true 的最小 x public static int binarySearchAnswer(int lo, int hi) { while (lo hi) { int mid lo ((hi - lo) 1); if (check(mid)) hi mid; // mid 可行尝试更小 else lo mid 1; // mid 不可行必须更大 } return lo; }这段代码值得逐字看。while (lo hi)而不是是因为循环退出时 lo hi答案唯一hi mid而不是mid - 1是因为 mid 本身可能就是答案不能丢lo mid 1则是因为 mid 已经确定不可行。3.2 局部最小值一个反直觉的二分场景基础篇里有一道经典题给定一个任意数组任意两个相邻元素不相等求任意一个局部最小值比左右邻居都小。下标 0 处只要小于下标 1 就是局部最小末尾同理。我第一次做的时候完全懵——数组是无序的怎么二分关键在于这题的答案存在性是可以证明的而且证明过程本身就给出了二分的方向如果 0 处不是局部最小即 arr[0] arr[1]末尾也不是局部最小即 arr[n-2] arr[n-1]那么从下标 0 开始值是下降趋势到末尾变成上升趋势中间必然有一个由降转升的转折点那个点就是局部最小。于是我们可以看中点如果中点比它的右邻居大说明下降趋势还在延续答案在右半边否则答案在左半边。这题给我的启发很大二分的依据可以是趋势的单调性而不必是值的单调性。这种思维方式在后面的找峰值找旋转数组中的最小值里会反复出现。提示判断一道题能不能二分问自己一句话——我能不能用 O(1) 的时间判断答案在中点的左边还是右边。能就是二分不能就换个方向想。3.3 边界与死循环我在二分上踩过的三种坑二分的边界是新手翻车率最高的地方我总结了自己踩过的三类坑症状原因修复方式mid 计算溢出大数据量时数组越界或死循环用 (lo hi) / 2两数相加溢出改成 lo (hi - lo) / 2区间不收缩循环永不退出写成了 lo mid 或 hi mid 但没有保证收缩保证每轮区间长度严格减小边界值漏判结果是答案 ±1取整方向搞错或漏了 lo hi 的检查用固定模板不要临场发挥第三种最隐蔽。比如在求满足条件的最大值这类问题里mid 的计算要用上取整lo (hi - lo 1) / 2否则当区间长度为 2 时 mid 恒等于 lolo mid会导致死循环。我现在的做法是所有二分题都先用模板把 lo、hi、mid 三者的更新写死再去调 check 函数绝不一边想逻辑一边改边界。4. 位运算、哈希表、前缀和三个被低估的小工具4.1 异或运算不用临时变量换值和找奇数次元素异或的性质在基础篇里被拎出来单独讲因为它太好用了。核心三条a ^ a 0、a ^ 0 a、异或满足交换律和结合律。由这三条可以推出两个高频用法。第一交换两个数a a ^ b; b a ^ b; // 相当于 (a^b)^b a a a ^ b; // 相当于 (a^b)^a b第二一堆数里只有一个数出现了奇数次其余都是偶数次求这个数。全部异或一遍偶数次的都抵消成 0剩下的就是答案。进阶版是有两个数出现了奇数次做法是先全部异或得到eor a ^ b然后取出eor最右侧的那个 1用它把所有数分成两组这样 a 和 b 一定被分到了不同组两组分别异或就得到答案int eor 0; for (int num : arr) eor ^ num; int rightOne eor (-eor); // 提取最右侧的 1等价于 eor (~eor 1) int onlyOne 0; for (int num : arr) { if ((num rightOne) ! 0) onlyOne ^ num; } int otherOne eor ^ onlyOne;eor (-eor)这个技巧本身就是位运算里的常客用途是取出一个整数二进制表示中最右边的 1。判断一个数是不是 2 的幂也可以用它n 0 (n (n - 1)) 0。顺带提一下位运算在状态压缩里是基础设施。n ≤ 20 的题目常见做法是把选没选编成一个整数的二进制位用位运算做集合的增删查配合 DP 处理集合类问题。4.2 哈希表和有序表什么时候必须用 TreeMap哈希表和有序表都是查得快的结构但能力边界完全不同。基础篇里讲得比较细的一点是哈希表的 key 一旦放进去之后修改 key 关联的内容没问题但修改 key 本身的值会导致它再也找不到因为哈希值变了。维度哈希表HashMap有序表TreeMap / 平衡树单次操作复杂度O(1) 期望O(log n)是否按 key 排序否是中序遍历即有序范围查询不支持支持找前驱后继、找区间key 的类型要求需要提供哈希与相等判断需要提供比较规则典型使用场景计数、去重、缓存映射需要按序取、需要邻居元素、需要排名我的经验是只要题目里出现比某个值小的最大元素排名第几区间内有多少个元素这类描述哈希表就直接出局必须上有序表。Java 里的TreeMap提供了floorKey、ceilingKey、firstKey、lastKey这一整套接口配合哈希表一起用可以解决数组中出现次数最多的前 k 个LRU 的变体这类题。自定义对象作为 key 时一定要同时重写equals和hashCode。只重写一个是新手最常见的 bug症状是明明放了进去却取不出来。规则是equals判定相等的两个对象hashCode必须相同反过来不要求成立。4.3 前缀和与差分把区间问题压成一次遍历前缀和的思想很简单预处理出一个数组pre[i]表示前 i 个元素的累加和那么任意区间[l, r]的和就是pre[r1] - pre[l]查询降到 O(1)。我在做子数组和等于目标值这类题时反复用这个技巧配合哈希表统计前缀和出现次数可以把 O(n²) 的枚举压成 O(n)。差分是前缀和的逆操作适用于多次区间加同一个值最后统一查询的场景。比如一堆操作给区间[l, r]每个元素加 v做了 m 次。朴素做法是每次循环一遍复杂度 O(nm)差分的做法是只改两个点diff[l] v、diff[r1] - v最后对 diff 数组求一次前缀和还原。这个技巧在二维场景下同样成立处理矩形区域加值的时候尤其省事。提示前缀和、差分、滑动窗口、双指针这四样东西本质上都是在利用区间操作的局部性。当你在题目里看到大量重复的区间查询或区间修改先想想能不能把它们聚合成边界上的少量操作。5. 链表与二叉树指针操作的肌肉记忆5.1 快慢指针能解决的几个经典判断链表题在基础篇里占了不小篇幅核心原因不是难而是它训练指针改写的顺序感。快慢指针是最常用的套路能覆盖一大类问题找中点、判断是否有环、找入环点、判断回文。判断有环的做法是快指针一次走两步、慢指针一次走一步如果两者相遇说明有环。找入环点的逻辑稍微绕相遇之后让快指针回到头部并改成一次走一步两个指针再次相遇的位置就是入环点。这个结论的证明依赖一个等式——设头到入环点距离为 a入环点到相遇点为 b相遇点绕回入环点为 c快指针走的距离是慢指针的两倍化简后得到 a c n*(bc)所以从头和从相遇点同时出发必然在入环点相遇。回文链表的做法是先快慢指针找到中点把后半段反转然后从两头往中间比较最后把链表恢复原状。最后这步恢复经常被忽略但在实际工程里很重要——你处理别人的数据时不应该改变它的结构。5.2 二叉树的递归套路先问我需要子树给我什么二叉树的题我原来是一道一道背的后来发现左程云给的那个套路能统一大部分题目假设以某个节点为头的子树能返回一个信息结构体你只需要确定两件事——这个结构体里放什么字段以及怎么用左右子树返回的信息合并出当前节点的答案。以判断二叉树是否平衡为例我需要从每棵子树拿到两个信息它的高度、它本身是否平衡。于是定义一个 Info 类static class Info { boolean isBalanced; int height; Info(boolean b, int h) { isBalanced b; height h; } } public static Info process(Node head) { if (head null) return new Info(true, 0); Info left process(head.left); Info right process(head.right); int height Math.max(left.height, right.height) 1; boolean isBalanced left.isBalanced right.isBalanced Math.abs(left.height - right.height) 1; return new Info(isBalanced, height); }这个套路的通用性极强。最大距离问题返回高度 最大距离最大搜索子树问题返回是否是 BST 大小 最大值 最小值满二叉树和完全二叉树的判断同理。我现在做二叉树题的第一步就是写下Info的字段定义写出来了题目基本就破了一半。5.3 Morris 遍历O(1) 空间的诱惑与代价Morris 遍历能在 O(1) 额外空间下完成二叉树的前中后序遍历原理是利用叶子节点的空右指针临时指回中序后继用完再改回去。基础篇里讲它重点不是让你在工程里用而是让你理解用空指针省空间这个思路。它的代价也很明确过程中链表结构被临时修改了如果在遍历期间有其他线程或者逻辑读取这棵树会读到错误的结构。所以我在实际项目里几乎不用 Morris只有在内存受限、且树是独占的场景下才会考虑。理解原理的价值在于遇到如何不用栈实现遍历这类问题时你能答上来而不是真的把它当默认方案。6. KMP 与滑动窗口字符串题的两把钥匙6.1 next 数组到底在记录什么KMP 的核心是 next 数组我一开始总记不住它的定义后来换了个说法就好记了next[i]表示从 0 到 i-1 这一段子串里最长相等前后缀的长度。注意范围是 i 之前不含 i 本身。它解决的问题是当主串和模式串在某个位置匹配失败时模式串不必回到开头重新比因为前缀信息告诉我们前面有一段已经和主串匹配上了直接跳到那段的后面位置继续比就行。public static int[] getNextArray(char[] ms) { if (ms.length 1) return new int[]{-1}; int[] next new int[ms.length]; next[0] -1; // 人为规定 next[1] 0; // 只有一个字符时没有前后缀 int i 2; // 从下标 2 开始求 int cn 0; // 当前要和 i-1 位置比较的位置 while (i ms.length) { if (ms[i - 1] ms[cn]) { next[i] cn; } else if (cn 0) { cn next[cn]; // 回退 } else { next[i] 0; } } return next; }next[0] -1是一个哨兵表示模式串第一个字符就匹配失败主串指针必须往前走一位。这个哨兵设计让主循环里不用写额外的边界判断是一个很典型的工程技巧。KMP 的时间复杂度是 O(n m)关键在于看起来内层的cn next[cn]好像在反复回退但回退的总次数被主指针的前进次数限制住了是均摊 O(n) 而不是 O(nm)。这个均摊分析的思路值得记住它和后面滑动窗口、单调栈的复杂度分析是一脉相承的。6.2 滑动窗口的可行性来自单调性滑动窗口不是万能工具它的适用前提是窗口扩大时某个指标单调变化。比如求最长无重复字符子串窗口扩大会让重复字符数从 0 变成 1缩小时又会降回 0这个单调性保证了右指针只前进不后退的做法是正确的。一个高频配套结构是单调双端队列用来求窗口内的最大值public static int[] getMaxWindow(int[] arr, int w) { if (arr null || w 1 || arr.length w) return null; LinkedListInteger qmax new LinkedList(); // 存下标值从大到小 int[] res new int[arr.length - w 1]; int index 0; for (int i 0; i arr.length; i) { while (!qmax.isEmpty() arr[qmax.peekLast()] arr[i]) { qmax.pollLast(); // 淘汰比新元素小的 } qmax.addLast(i); if (qmax.peekFirst() i - w) qmax.pollFirst(); // 过期出队 if (i w - 1) res[index] arr[qmax.peekFirst()]; } return res; }队列里存的是下标而不是值这是为了判断过期。之所以能保证队首是最大值是因为任何一个又小又靠前的元素都不可能再成为答案——它既比后面的元素小又比后面的元素先过期直接被淘汰掉不亏。这个淘汰不可能成为答案的元素的思想和单调栈是一回事。提示写滑动窗口时把窗口的定义先写死比如左闭右开再决定什么时候扩、什么时候缩。定义模糊是滑动窗口写错的第一大原因比逻辑错误更常见。7. 贪心与尝试模型基础篇的最后一道坎7.1 贪心的正确性只能验证不能感觉贪心是基础篇里最玄的部分因为它的难点不在写代码而在证明每一步取局部最优能导出全局最优。我的做法是先猜一个贪心策略然后用对数器和小规模穷举去验证。如果策略错了随机数据几百次就能打出来。几个经典模型的贪心策略值得记住。会议安排问题按结束时间升序排能安排最多的不冲突会议字符串拼接求最小字典序比较规则是a b b a注意这个比较规则是可以传递的所以能作为排序依据金条分割问题反过来想等价于哈夫曼树每次合并最小的两块。这里的经验是贪心策略往往有交换论证的味道——假设最优解里某一步不是贪心选择我能不能把这一步换成贪心选择而不让结果变差。能换策略就对换不了就要重新想。7.2 从尝试模型到动态规划的那一步基础篇的收尾部分讲了递归的尝试模型。这个说法的意思是不去想状态转移方程而是先写出一个暴力递归把每个位置有哪些选择表达清楚。比如背包问题暴力递归就是第 i 个物品要或不要分别递归。// 尝试模型从左往右决定每个物品拿不拿 public static int process(int[] weight, int[] value, int i, int alreadyWeight, int bag) { if (alreadyWeight bag) return -1; // 超重无效解 if (i weight.length) return 0; // 没物品可选了 int p1 process(weight, value, i 1, alreadyWeight, bag); // 不要 int p2next process(weight, value, i 1, alreadyWeight weight[i], bag); int p2 p2next -1 ? -1 : value[i] p2next; return Math.max(p1, p2); }写出暴力递归之后动态规划就是机械翻译把变化的参数这里是 i 和 alreadyWeight作为维度建表把递归的返回值填进去注意依赖顺序。这一步我原来总觉得玄学后来发现只要暴力递归写对了翻译过程几乎不需要思考只需要耐心。这也解释了为什么左程云在基础篇反复强调先写暴力递归。动态规划难的不是方程是你能不能把问题的决策结构表达清楚。递归是表达DP 是优化。8. 我的练习节奏与复盘方式8.1 一天两道题但每道题写三遍我试过一天刷十道题结果一周后回头一看能独立写出来的不到三道。后来改成一天两道但每道题写三遍第一遍照着思路写边写边注释每一步在干什么第二遍关掉参考凭记忆重写卡住的地方做标记第三遍只写核心函数练手速和肌肉记忆。这个节奏看着慢但一周下来能扎实拿下十道题的变形。算法这东西的记忆方式和背单词不一样它靠的是结构识别——你要能把新题映射回已知的模板。刷十道浅题的效果远不如把三道题吃透。8.2 复盘表格把踩过的坑变成资产我从第二轮复习开始维护一张复盘表每条记录包含五个字段写满一百多条之后很多错误就不再重复犯了字段填写内容示例题目特征一句话描述题型入口数组无序但要求 O(log n)用到的模板对应的算法骨架判定函数二分卡住的点具体在哪一步想不通判定函数怎么构造根因是知识盲区还是思维定势以为二分必须有序变形方向这类题还能怎么变求最大的最小值这张表最大的价值在于根因那一列。写多了你会发现自己的错误高度集中在少数几个模式上边界处理、复杂度误判、把相似题的做法直接套用。找准了模式改进才有靶子。提示复盘表里不要只记这题不会要记我为什么会往错误的方向想。前者是结果后者才是可复用的经验。8.3 关于工具与环境的几个实际建议写算法练习时本地环境的准备程度直接影响效率。我的习惯是建一个工程把对数器、随机数组生成、打印工具、常用模板全部封装成静态方法新建题目时直接复制模板文件五秒钟进入编码状态。这个投入一次性收益是长期的。另外调试的时候不要急着打日志。先用手写的小样例在脑子里跑一遍流程尤其是涉及指针移动和下标变化的代码用纸笔画出每一轮的状态。我用这个笨办法定位过一个快排的 bug随机交换的位置写成了l而不是r导致每次都用同一个基准代码看着没问题但退化了。这种错误在断点调试里反而难发现因为每一步都是对的。最后一点关于进度的心态算法基础篇的内容不算少但真正难啃的只有归并、快排、KMP 这几块需要严格推导的部分其余的更多是套路和熟练度。我当时花了大概六周过完第一遍后面又用了三周做变形题第二遍重刷的时候速度明显快了一档。慢没关系只要每一轮都在把看懂了变成写出来了就是在往前走。 左程云算法笔记基础篇复盘：复杂度到KMP的刷题方法论
去年冬天我把左程云的算法笔记重新翻出来刷了一遍起因很朴素面试里被一道看着像二分、写起来像模拟的题卡了四十分钟回来一查发现这道题的骨架在他基础篇里就讲过只是当时我看完就划过去了。这次重刷我做了很多笔记之外的事——把每类问题的判定入口单独抄成一页把对数器写成了固定模板把踩过的边界坑记在代码注释里。这篇就是我这一轮复盘下来的东西主要面向刚开始系统学算法、或者刷了几十道题但总觉得脑子里没骨架的人。左程云的算法笔记基础篇覆盖的东西不算花哨复杂度分析、排序、二分、位运算、链表、二叉树、字符串匹配、贪心但你真按顺序走一遍会发现它不是知识点清单而是一套遇到陌生题从哪下嘴的方法论。我下面不会按课程顺序复述而是按我自己重新理解了一遍的路径来写。每个模块我都会说清楚三件事这个东西解决的是哪一类问题、我当初在哪一步理解错了、现在我会怎么用。代码统一给 Java因为原笔记是 Java 体系习惯 Python 的读者把数组和下标逻辑看明白就行换语言只是语法成本。1. 复杂度不是背出来的是从数据规模反推出来的1.1 先看 n 的量级再决定敢不敢写双重循环我见过太多人写完代码才去算复杂度其实顺序应该反过来。左程云在基础篇反复强调的一件事是看到题目先看数据范围数据范围直接告诉你哪一档算法是够用的。这一步做对了你至少不会在 n 10⁵ 的题上写 O(n²) 然后对着超时提示发呆。我把这套反查关系整理成了表做题时扫一眼就能定位数据规模 n时间预算 1 秒内可接受的复杂度这时你该想到的解法形态n ≤ 20O(2ⁿ)、O(n!)暴力枚举、状态压缩、全排列n ≤ 100O(n³) 或 O(n⁴)三重循环 DP、Floydn ≤ 2000O(n²)二维 DP、朴素配对、双重循环n ≤ 10⁵O(n log n)排序、二分、堆、归并思想n ≤ 10⁶O(n)一次遍历、前缀和、双指针、单调栈n ≤ 10⁸O(n) 且常数极小位运算、简单计数慎用容器这张表的用法不是死记而是形成条件反射。我现在读题的第一分钟不做别的就盯着数据范围看然后用它排除掉一整片不合适的思路。排除法的价值比想到正确解法高得多因为它能把搜索空间从几十种压到两三种。提示数据范围是出题人给你的最大善意。n 写 10⁵ 基本等于在明示别写 n²n 写 20 基本等于在明示随便暴力。忽略这个信号等于主动放弃一条捷径。1.2 常数项、递归展开和看起来一样其实差一倍复杂度只描述增长趋势但工程实现里常数项是真实存在的。基础篇里有一段容易被跳过同样的 O(n log n)归并排序要额外开数组拷贝快速排序基本原地交换在 n 10⁶ 这个量级上两者的实测差距能有 30% 以上。这不是复杂度理论错了而是理论不负责常数。递归的时间复杂度估算我用的是最朴素的三步法写出递归式、算出每层的总工作量、用 master 公式或者画递归树定档。以归并排序为例规模 N 的问题拆成两个 N/2 的子问题合并那一步要扫一遍整个区间于是T(N) 2 * T(N/2) O(N)每层总工作量都是 O(N)一共 log N 层结论就是 O(N log N)。这个推导的价值在于当你以后看到拆两半 线性合并的结构你会直接条件反射出 N log N而不是每次重推一遍。空间复杂度方面我踩过一个很典型的坑写递归函数时只算了递归栈的深度忘了每层里开的临时数组。递归栈深度是 O(log N)但所有层的临时数组加起来峰值也是 O(N)实际占用比直觉高一截。后来我养成一个习惯递归函数里凡是开了堆上对象都在注释里标一句这层的额外空间是多少。1.3 对数器把我觉得对了换成它确实对了如果只让我从左程云的算法笔记里挑一个最有价值的工具我选对数器。它的思路简单到粗暴写一个绝对正确但可能很慢的暴力解再写一个你优化后的解用随机数据大量对撞只要有一组输出不一致就说明优化版有 bug。对数器的骨架我固定成了下面这样每次换题只改排序函数和比较逻辑// 1. 随机样本生成器可以生成重复值、负数、边界长度 public static int[] generateRandomArray(int maxSize, int maxValue) { int[] arr new int[(int) ((maxSize 1) * Math.random())]; for (int i 0; i arr.length; i) { arr[i] (int) ((maxValue 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } // 2. 拷贝工具保证两个解法吃到的输入完全一样 public static int[] copyArray(int[] arr) { if (arr null) return null; int[] res new int[arr.length]; for (int i 0; i arr.length; i) res[i] arr[i]; return res; } // 3. 主流程小样本高频对撞 public static void main(String[] args) { int testTime 500000; int maxSize 100; int maxValue 100; boolean succeed true; for (int i 0; i testTime; i) { int[] arr1 generateRandomArray(maxSize, maxValue); int[] arr2 copyArray(arr1); yourSort(arr1); // 你的解法 bruteForceSort(arr2); // 绝对正确的暴力解 if (!isEqual(arr1, arr2)) { succeed false; printArray(arr1); printArray(arr2); break; } } System.out.println(succeed ? Nice! : Fucking fucked!); }这个模板的杀伤力在于它能抓出你自己根本想不到的 case。我曾经在一个局部最小值的题上自认为边界处理得很好对数器跑了不到两千次就抓到一组长度为 2 且两个数相等的数组——我从头到尾没考虑过重复元素。人工构造测试用例时人是会护着自己思路的随机对撞不会。提示对数器的样本量要小规模、高次数。maxSize 控制小一点循环次数拉大比一次性跑几个大数据更能暴露逻辑漏洞。另外记住先写暴力解哪怕它慢得像 O(n³)因为暴力解本身也是你的题目理解检查器。2. 排序这一关真正值钱的不是代码本身2.1 三个 O(n²) 排序是理解有序区概念的起点冒泡、选择、插入这三个算法很多人背完就扔但左程云讲它们的顺序不是按难度而是按有序区的形成方式来编排的。冒泡每一次外层循环把最大值冒到末尾有序区从右往左长选择排序每次找出剩余部分的最小值有序区从左往右长插入排序则是维护左侧一段有序区每次把新的元素插到正确位置。插入排序有个性质值得单独记住当数据接近有序时它的实际表现会退化到接近 O(n)因为内层交换次数很少。这就是为什么很多工业级排序在数据规模小比如 16 个元素以下时会退化成插入排序——常数小、缓存友好、几乎有序时极快。public static void insertionSort(int[] arr) { if (arr null || arr.length 2) return; for (int i 1; i arr.length; i) { // 向左找位置只要左边比自己大就交换 for (int j i - 1; j 0 arr[j] arr[j 1]; j--) { swap(arr, j, j 1); } } }注意这个写法的内层循环条件是arr[j] arr[j1]而不是arr[j] arr[i]。新手很容易写成后者然后在下标处理上绕半天。用相邻交换的写法虽然多几次赋值但边界逻辑简单不容易错。2.2 归并排序分治的第一次真正交手归并排序是基础篇里我花时间最多的部分不是因为代码难而是它带出了分治这个可以套用到无数题上的思维框架。它的结构就是三行拆半、递归、合并。public static void mergeSort(int[] arr) { if (arr null || arr.length 2) return; process(arr, 0, arr.length - 1); } private static void process(int[] arr, int l, int r) { if (l r) return; int mid l ((r - l) 1); // 这样写不会溢出 process(arr, l, mid); process(arr, mid 1, r); merge(arr, l, mid, r); } private static void merge(int[] arr, int l, int m, int r) { int[] help new int[r - l 1]; int i 0, p1 l, p2 m 1; while (p1 m p2 r) { help[i] arr[p1] arr[p2] ? arr[p1] : arr[p2]; } while (p1 m) help[i] arr[p1]; while (p2 r) help[i] arr[p2]; for (i 0; i help.length; i) arr[l i] help[i]; }这里mid l ((r - l) 1)的写法必须养成习惯。用(l r) / 2在 l 和 r 都接近整数上限时会溢出成负数进而在某些语言里直接导致数组越界。这种 bug 在本地小数据上永远复现不了一旦上线就炸。归并思想真正的价值在后面小和问题、逆序对问题、区间内个数统计本质上都是在 merge 那一步顺手统计跨左右两半的信息。我最初做小和问题时死活想不通为什么在 merge 里累加是对的后来画了一次递归树才明白——每次 merge 处理的是右半部分某个元素与左半部分所有比它小的元素的贡献而每一对 (i, j) 只会在某一次 merge 中被统计一次既不重不漏。2.3 快速排序随机化 pivot 解决了什么快速排序的核心是 partition。基础篇里讲的是荷兰国旗版本的三分法把数组分成小于区、等于区、大于区这一步对重复元素极其友好因为等于区一次成型后续递归不再碰。// 返回等于区的左右边界 public static int[] netherlandsFlag(int[] arr, int l, int r) { if (l r) return new int[]{-1, -1}; if (l r) return new int[]{l, r}; int less l - 1, more r, index l; while (index more) { if (arr[index] arr[r]) swap(arr, less, index); else if (arr[index] arr[r]) swap(arr, index, --more); else index; } swap(arr, more, r); return new int[]{less 1, more}; }为什么要在 partition 之前随机挑一个位置和末尾交换因为固定选末尾作为基准时遇到已经有序的数组会退化成 O(n²)每次只搞定一个元素。随机化之后最坏情况在数学上仍然存在但概率极低期望复杂度稳定在 O(n log N)。我用对数器专门验证过这一点不随机化时输入一个升序数组递归深度直接到 n在某些语言里会栈溢出。提示快排的随机不是为了让平均更快而是为了打散输入分布把最坏情况从你一定会遇到变成理论上存在但几乎遇不到。这是算法设计里一个很典型的手法——用随机性换稳定性。2.4 堆结构heapInsert 与 heapify 的分工堆在基础篇里出现得很早讲得也细。它是一棵完全二叉树用数组存下标关系是父节点 i 的左孩子 2i1右孩子 2i2。所有操作就靠两个动作支撑// 新元素上浮用于建堆、往堆里加元素 public static void heapInsert(int[] arr, int index) { while (arr[index] arr[(index - 1) / 2]) { swap(arr, index, (index - 1) / 2); index (index - 1) / 2; } } // 元素下沉用于堆顶被取走后重新调整 public static void heapify(int[] arr, int index, int heapSize) { int left index * 2 1; while (left heapSize) { int largest left 1 heapSize arr[left 1] arr[left] ? left 1 : left; largest arr[largest] arr[index] ? largest : index; if (largest index) break; swap(arr, index, largest); index largest; left index * 2 1; } }这两个函数的分工很容易搞混heapInsert是自下而上修复heapify是自上而下修复。建堆用哪个两种都能建但heapify从最后一个非叶节点往前扫整体复杂度是 O(n)而heapInsert一个个插入是 O(n log n)。这个建堆可以做到 O(n)的结论在面试里被问到的频率不低理由是越靠近底层的节点越多但它们的下沉距离越短加权求和后收敛到 O(n)。堆排序的做法是把堆顶和末尾交换堆大小减一再对堆顶做一次 heapify。至于优先队列Java 的PriorityQueue默认是小根堆要大根堆就传Comparator反转或者自己往里面塞相反数。手写堆的意义在于你能实现改堆中某个元素的值这种优先队列不提供的操作。2.5 稳定性工程上和理论上是两个问题排序的稳定性在纯算法题里不怎么考但在真实系统里是硬要求。所谓稳定就是相等元素的相对顺序在排序后保持不变。你给一批订单按金额排序金额相同的那些原本按时间排好的顺序不能被打破否则用户看到的列表会莫名跳动。排序算法平均时间最坏时间额外空间是否稳定冒泡排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定归并排序O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(1)不稳定记忆的技巧是抓住交换方式凡是跳跃式交换的选择、快排、堆排都可能把相等元素甩到后面去因此不稳定凡是相邻交换或者额外数组归并的通常稳定。归并排序是唯一同时满足 O(n log n) 和稳定的通用排序这也是它在实际工程中被大量使用的原因。Java 里对象数组排序用的是归并的变体TimSort保证稳定基本类型数组用的是双轴快排不保证稳定但更快。这个区别不是随手写的是因为基本类型没有身份概念两个相等的 int 谁在前谁在后无所谓而对象通常有关联的其他字段顺序就变得有意义了。3. 二分法的本质是单调性不是有序数组3.1 判定函数把二分答案翻译成人话我一开始对二分的理解停留在有序数组里找某个数直到做了一道求最小可行容量的题才开窍。二分真正的适用条件是存在一个判定函数 f(x)使得 f(x) 随着 x 增大呈现出单一方向的变化先假后真或者先真后假。数组有序只是这个条件的一个特例——因为下标 i 处的值是否小于目标值这个判定函数是单调的。把这个抽象套回具体问题你会发现一大批看起来不像二分的题都能二分求平方根的整数部分、找最小耗时、求最大可分配的最小值、找峰值、找局部最小值。解题的关键变成两步一是写出判定函数二是确定答案的搜索范围。判定函数写完之后模板就固定了// 求满足 check(x) true 的最小 x public static int binarySearchAnswer(int lo, int hi) { while (lo hi) { int mid lo ((hi - lo) 1); if (check(mid)) hi mid; // mid 可行尝试更小 else lo mid 1; // mid 不可行必须更大 } return lo; }这段代码值得逐字看。while (lo hi)而不是是因为循环退出时 lo hi答案唯一hi mid而不是mid - 1是因为 mid 本身可能就是答案不能丢lo mid 1则是因为 mid 已经确定不可行。3.2 局部最小值一个反直觉的二分场景基础篇里有一道经典题给定一个任意数组任意两个相邻元素不相等求任意一个局部最小值比左右邻居都小。下标 0 处只要小于下标 1 就是局部最小末尾同理。我第一次做的时候完全懵——数组是无序的怎么二分关键在于这题的答案存在性是可以证明的而且证明过程本身就给出了二分的方向如果 0 处不是局部最小即 arr[0] arr[1]末尾也不是局部最小即 arr[n-2] arr[n-1]那么从下标 0 开始值是下降趋势到末尾变成上升趋势中间必然有一个由降转升的转折点那个点就是局部最小。于是我们可以看中点如果中点比它的右邻居大说明下降趋势还在延续答案在右半边否则答案在左半边。这题给我的启发很大二分的依据可以是趋势的单调性而不必是值的单调性。这种思维方式在后面的找峰值找旋转数组中的最小值里会反复出现。提示判断一道题能不能二分问自己一句话——我能不能用 O(1) 的时间判断答案在中点的左边还是右边。能就是二分不能就换个方向想。3.3 边界与死循环我在二分上踩过的三种坑二分的边界是新手翻车率最高的地方我总结了自己踩过的三类坑症状原因修复方式mid 计算溢出大数据量时数组越界或死循环用 (lo hi) / 2两数相加溢出改成 lo (hi - lo) / 2区间不收缩循环永不退出写成了 lo mid 或 hi mid 但没有保证收缩保证每轮区间长度严格减小边界值漏判结果是答案 ±1取整方向搞错或漏了 lo hi 的检查用固定模板不要临场发挥第三种最隐蔽。比如在求满足条件的最大值这类问题里mid 的计算要用上取整lo (hi - lo 1) / 2否则当区间长度为 2 时 mid 恒等于 lolo mid会导致死循环。我现在的做法是所有二分题都先用模板把 lo、hi、mid 三者的更新写死再去调 check 函数绝不一边想逻辑一边改边界。4. 位运算、哈希表、前缀和三个被低估的小工具4.1 异或运算不用临时变量换值和找奇数次元素异或的性质在基础篇里被拎出来单独讲因为它太好用了。核心三条a ^ a 0、a ^ 0 a、异或满足交换律和结合律。由这三条可以推出两个高频用法。第一交换两个数a a ^ b; b a ^ b; // 相当于 (a^b)^b a a a ^ b; // 相当于 (a^b)^a b第二一堆数里只有一个数出现了奇数次其余都是偶数次求这个数。全部异或一遍偶数次的都抵消成 0剩下的就是答案。进阶版是有两个数出现了奇数次做法是先全部异或得到eor a ^ b然后取出eor最右侧的那个 1用它把所有数分成两组这样 a 和 b 一定被分到了不同组两组分别异或就得到答案int eor 0; for (int num : arr) eor ^ num; int rightOne eor (-eor); // 提取最右侧的 1等价于 eor (~eor 1) int onlyOne 0; for (int num : arr) { if ((num rightOne) ! 0) onlyOne ^ num; } int otherOne eor ^ onlyOne;eor (-eor)这个技巧本身就是位运算里的常客用途是取出一个整数二进制表示中最右边的 1。判断一个数是不是 2 的幂也可以用它n 0 (n (n - 1)) 0。顺带提一下位运算在状态压缩里是基础设施。n ≤ 20 的题目常见做法是把选没选编成一个整数的二进制位用位运算做集合的增删查配合 DP 处理集合类问题。4.2 哈希表和有序表什么时候必须用 TreeMap哈希表和有序表都是查得快的结构但能力边界完全不同。基础篇里讲得比较细的一点是哈希表的 key 一旦放进去之后修改 key 关联的内容没问题但修改 key 本身的值会导致它再也找不到因为哈希值变了。维度哈希表HashMap有序表TreeMap / 平衡树单次操作复杂度O(1) 期望O(log n)是否按 key 排序否是中序遍历即有序范围查询不支持支持找前驱后继、找区间key 的类型要求需要提供哈希与相等判断需要提供比较规则典型使用场景计数、去重、缓存映射需要按序取、需要邻居元素、需要排名我的经验是只要题目里出现比某个值小的最大元素排名第几区间内有多少个元素这类描述哈希表就直接出局必须上有序表。Java 里的TreeMap提供了floorKey、ceilingKey、firstKey、lastKey这一整套接口配合哈希表一起用可以解决数组中出现次数最多的前 k 个LRU 的变体这类题。自定义对象作为 key 时一定要同时重写equals和hashCode。只重写一个是新手最常见的 bug症状是明明放了进去却取不出来。规则是equals判定相等的两个对象hashCode必须相同反过来不要求成立。4.3 前缀和与差分把区间问题压成一次遍历前缀和的思想很简单预处理出一个数组pre[i]表示前 i 个元素的累加和那么任意区间[l, r]的和就是pre[r1] - pre[l]查询降到 O(1)。我在做子数组和等于目标值这类题时反复用这个技巧配合哈希表统计前缀和出现次数可以把 O(n²) 的枚举压成 O(n)。差分是前缀和的逆操作适用于多次区间加同一个值最后统一查询的场景。比如一堆操作给区间[l, r]每个元素加 v做了 m 次。朴素做法是每次循环一遍复杂度 O(nm)差分的做法是只改两个点diff[l] v、diff[r1] - v最后对 diff 数组求一次前缀和还原。这个技巧在二维场景下同样成立处理矩形区域加值的时候尤其省事。提示前缀和、差分、滑动窗口、双指针这四样东西本质上都是在利用区间操作的局部性。当你在题目里看到大量重复的区间查询或区间修改先想想能不能把它们聚合成边界上的少量操作。5. 链表与二叉树指针操作的肌肉记忆5.1 快慢指针能解决的几个经典判断链表题在基础篇里占了不小篇幅核心原因不是难而是它训练指针改写的顺序感。快慢指针是最常用的套路能覆盖一大类问题找中点、判断是否有环、找入环点、判断回文。判断有环的做法是快指针一次走两步、慢指针一次走一步如果两者相遇说明有环。找入环点的逻辑稍微绕相遇之后让快指针回到头部并改成一次走一步两个指针再次相遇的位置就是入环点。这个结论的证明依赖一个等式——设头到入环点距离为 a入环点到相遇点为 b相遇点绕回入环点为 c快指针走的距离是慢指针的两倍化简后得到 a c n*(bc)所以从头和从相遇点同时出发必然在入环点相遇。回文链表的做法是先快慢指针找到中点把后半段反转然后从两头往中间比较最后把链表恢复原状。最后这步恢复经常被忽略但在实际工程里很重要——你处理别人的数据时不应该改变它的结构。5.2 二叉树的递归套路先问我需要子树给我什么二叉树的题我原来是一道一道背的后来发现左程云给的那个套路能统一大部分题目假设以某个节点为头的子树能返回一个信息结构体你只需要确定两件事——这个结构体里放什么字段以及怎么用左右子树返回的信息合并出当前节点的答案。以判断二叉树是否平衡为例我需要从每棵子树拿到两个信息它的高度、它本身是否平衡。于是定义一个 Info 类static class Info { boolean isBalanced; int height; Info(boolean b, int h) { isBalanced b; height h; } } public static Info process(Node head) { if (head null) return new Info(true, 0); Info left process(head.left); Info right process(head.right); int height Math.max(left.height, right.height) 1; boolean isBalanced left.isBalanced right.isBalanced Math.abs(left.height - right.height) 1; return new Info(isBalanced, height); }这个套路的通用性极强。最大距离问题返回高度 最大距离最大搜索子树问题返回是否是 BST 大小 最大值 最小值满二叉树和完全二叉树的判断同理。我现在做二叉树题的第一步就是写下Info的字段定义写出来了题目基本就破了一半。5.3 Morris 遍历O(1) 空间的诱惑与代价Morris 遍历能在 O(1) 额外空间下完成二叉树的前中后序遍历原理是利用叶子节点的空右指针临时指回中序后继用完再改回去。基础篇里讲它重点不是让你在工程里用而是让你理解用空指针省空间这个思路。它的代价也很明确过程中链表结构被临时修改了如果在遍历期间有其他线程或者逻辑读取这棵树会读到错误的结构。所以我在实际项目里几乎不用 Morris只有在内存受限、且树是独占的场景下才会考虑。理解原理的价值在于遇到如何不用栈实现遍历这类问题时你能答上来而不是真的把它当默认方案。6. KMP 与滑动窗口字符串题的两把钥匙6.1 next 数组到底在记录什么KMP 的核心是 next 数组我一开始总记不住它的定义后来换了个说法就好记了next[i]表示从 0 到 i-1 这一段子串里最长相等前后缀的长度。注意范围是 i 之前不含 i 本身。它解决的问题是当主串和模式串在某个位置匹配失败时模式串不必回到开头重新比因为前缀信息告诉我们前面有一段已经和主串匹配上了直接跳到那段的后面位置继续比就行。public static int[] getNextArray(char[] ms) { if (ms.length 1) return new int[]{-1}; int[] next new int[ms.length]; next[0] -1; // 人为规定 next[1] 0; // 只有一个字符时没有前后缀 int i 2; // 从下标 2 开始求 int cn 0; // 当前要和 i-1 位置比较的位置 while (i ms.length) { if (ms[i - 1] ms[cn]) { next[i] cn; } else if (cn 0) { cn next[cn]; // 回退 } else { next[i] 0; } } return next; }next[0] -1是一个哨兵表示模式串第一个字符就匹配失败主串指针必须往前走一位。这个哨兵设计让主循环里不用写额外的边界判断是一个很典型的工程技巧。KMP 的时间复杂度是 O(n m)关键在于看起来内层的cn next[cn]好像在反复回退但回退的总次数被主指针的前进次数限制住了是均摊 O(n) 而不是 O(nm)。这个均摊分析的思路值得记住它和后面滑动窗口、单调栈的复杂度分析是一脉相承的。6.2 滑动窗口的可行性来自单调性滑动窗口不是万能工具它的适用前提是窗口扩大时某个指标单调变化。比如求最长无重复字符子串窗口扩大会让重复字符数从 0 变成 1缩小时又会降回 0这个单调性保证了右指针只前进不后退的做法是正确的。一个高频配套结构是单调双端队列用来求窗口内的最大值public static int[] getMaxWindow(int[] arr, int w) { if (arr null || w 1 || arr.length w) return null; LinkedListInteger qmax new LinkedList(); // 存下标值从大到小 int[] res new int[arr.length - w 1]; int index 0; for (int i 0; i arr.length; i) { while (!qmax.isEmpty() arr[qmax.peekLast()] arr[i]) { qmax.pollLast(); // 淘汰比新元素小的 } qmax.addLast(i); if (qmax.peekFirst() i - w) qmax.pollFirst(); // 过期出队 if (i w - 1) res[index] arr[qmax.peekFirst()]; } return res; }队列里存的是下标而不是值这是为了判断过期。之所以能保证队首是最大值是因为任何一个又小又靠前的元素都不可能再成为答案——它既比后面的元素小又比后面的元素先过期直接被淘汰掉不亏。这个淘汰不可能成为答案的元素的思想和单调栈是一回事。提示写滑动窗口时把窗口的定义先写死比如左闭右开再决定什么时候扩、什么时候缩。定义模糊是滑动窗口写错的第一大原因比逻辑错误更常见。7. 贪心与尝试模型基础篇的最后一道坎7.1 贪心的正确性只能验证不能感觉贪心是基础篇里最玄的部分因为它的难点不在写代码而在证明每一步取局部最优能导出全局最优。我的做法是先猜一个贪心策略然后用对数器和小规模穷举去验证。如果策略错了随机数据几百次就能打出来。几个经典模型的贪心策略值得记住。会议安排问题按结束时间升序排能安排最多的不冲突会议字符串拼接求最小字典序比较规则是a b b a注意这个比较规则是可以传递的所以能作为排序依据金条分割问题反过来想等价于哈夫曼树每次合并最小的两块。这里的经验是贪心策略往往有交换论证的味道——假设最优解里某一步不是贪心选择我能不能把这一步换成贪心选择而不让结果变差。能换策略就对换不了就要重新想。7.2 从尝试模型到动态规划的那一步基础篇的收尾部分讲了递归的尝试模型。这个说法的意思是不去想状态转移方程而是先写出一个暴力递归把每个位置有哪些选择表达清楚。比如背包问题暴力递归就是第 i 个物品要或不要分别递归。// 尝试模型从左往右决定每个物品拿不拿 public static int process(int[] weight, int[] value, int i, int alreadyWeight, int bag) { if (alreadyWeight bag) return -1; // 超重无效解 if (i weight.length) return 0; // 没物品可选了 int p1 process(weight, value, i 1, alreadyWeight, bag); // 不要 int p2next process(weight, value, i 1, alreadyWeight weight[i], bag); int p2 p2next -1 ? -1 : value[i] p2next; return Math.max(p1, p2); }写出暴力递归之后动态规划就是机械翻译把变化的参数这里是 i 和 alreadyWeight作为维度建表把递归的返回值填进去注意依赖顺序。这一步我原来总觉得玄学后来发现只要暴力递归写对了翻译过程几乎不需要思考只需要耐心。这也解释了为什么左程云在基础篇反复强调先写暴力递归。动态规划难的不是方程是你能不能把问题的决策结构表达清楚。递归是表达DP 是优化。8. 我的练习节奏与复盘方式8.1 一天两道题但每道题写三遍我试过一天刷十道题结果一周后回头一看能独立写出来的不到三道。后来改成一天两道但每道题写三遍第一遍照着思路写边写边注释每一步在干什么第二遍关掉参考凭记忆重写卡住的地方做标记第三遍只写核心函数练手速和肌肉记忆。这个节奏看着慢但一周下来能扎实拿下十道题的变形。算法这东西的记忆方式和背单词不一样它靠的是结构识别——你要能把新题映射回已知的模板。刷十道浅题的效果远不如把三道题吃透。8.2 复盘表格把踩过的坑变成资产我从第二轮复习开始维护一张复盘表每条记录包含五个字段写满一百多条之后很多错误就不再重复犯了字段填写内容示例题目特征一句话描述题型入口数组无序但要求 O(log n)用到的模板对应的算法骨架判定函数二分卡住的点具体在哪一步想不通判定函数怎么构造根因是知识盲区还是思维定势以为二分必须有序变形方向这类题还能怎么变求最大的最小值这张表最大的价值在于根因那一列。写多了你会发现自己的错误高度集中在少数几个模式上边界处理、复杂度误判、把相似题的做法直接套用。找准了模式改进才有靶子。提示复盘表里不要只记这题不会要记我为什么会往错误的方向想。前者是结果后者才是可复用的经验。8.3 关于工具与环境的几个实际建议写算法练习时本地环境的准备程度直接影响效率。我的习惯是建一个工程把对数器、随机数组生成、打印工具、常用模板全部封装成静态方法新建题目时直接复制模板文件五秒钟进入编码状态。这个投入一次性收益是长期的。另外调试的时候不要急着打日志。先用手写的小样例在脑子里跑一遍流程尤其是涉及指针移动和下标变化的代码用纸笔画出每一轮的状态。我用这个笨办法定位过一个快排的 bug随机交换的位置写成了l而不是r导致每次都用同一个基准代码看着没问题但退化了。这种错误在断点调试里反而难发现因为每一步都是对的。最后一点关于进度的心态算法基础篇的内容不算少但真正难啃的只有归并、快排、KMP 这几块需要严格推导的部分其余的更多是套路和熟练度。我当时花了大概六周过完第一遍后面又用了三周做变形题第二遍重刷的时候速度明显快了一档。慢没关系只要每一轮都在把看懂了变成写出来了就是在往前走。