阿甘的博客 | Arganzheng's Blog

面试手撕代码（11）：动态规划（一）——线性与二维

Dynamic Programming I: Define the State, Then the Rest Follows

动态规划是面试里最让人紧张的一类题，但中等难度的 DP 只有两种形状：一维（状态是”前 \(i\) 个元素”或”到第 \(i\) 个位置”）和二维（状态是”前 \(i\) 个与前 \(j\) 个”或”格子 \((i, j)\)“）。这一篇讲这两种，下一篇讲背包、区间、状态机、树形。DP 题的难点从来不在代码——代码几乎都是两层循环加一个 max / min——而在状态的定义：定义对了转移是显然的，定义错了怎么凑都不对。所以这一篇先讲一套”五步法”，再用七道主讲题把它练熟。本篇要回答的核心问题是：怎样从题面推出 DP 的状态定义，而不是靠背题？1 最长递增子序列的 \(O(n \log n)\) 解法里 tails 数组存的是什么？2 编辑距离的三种操作...

Posted by arganzheng | December 12, 2025

面试手撕代码（10）：字符串

Strings: Palindromes, KMP, Parsing, Big Numbers and Custom Ordering

字符串题一半是前面几篇模式的字符版（滑动窗口、哈希计数、栈），另一半是这一篇要讲的字符串特有的技巧：回文的中心扩展与 Manacher、子串匹配的 KMP 失配表、手写解析（atoi）、大数的竖式运算、以及”拼起来最大”这类自定义排序。这些题代码都不长，但边界多——空串、前导零、符号、溢出、相等元素的排序稳定性——面试官正是靠这些边界筛人。本篇要回答的核心问题是：最长回文子串为什么中心扩展比区间 DP 更适合面试，Manacher 又改进了什么？1 KMP 的失配表 lps 到底存的是什么，为什么匹配失败时跳到 lps[k-1] 不会漏解？2 “拼接后最大的数”为什么排序比较器用 a+b 与 b+a 就是对的？3 一、识别信号 ...

Posted by arganzheng | December 11, 2025

面试手撕代码（09）：回溯

Backtracking: Choose, Recurse, Undo — and Prune

回溯是”枚举所有方案”的标准写法：排列、组合、子集、切分、棋盘放置。它的代码只有一个骨架——做选择、递归、撤销选择——所有题的差别只在三处：候选集合怎么定（从哪开始、能不能重复选）、怎么去重（排序后跳过同层相同值）、怎么剪枝（提前判断这条路不可能有答案）。这一篇把骨架和三处差别讲清，七组主讲题（排列 / 排列去重、子集 / 子集去重、组合总和 I / II、括号生成、回文切分、单词搜索、N 皇后）覆盖面试里能遇到的全部回溯形态。本篇要回答的核心问题是：排列、组合、子集三种题的递归参数差在哪里？1 “排序后跳过同层相同值”的去重为什么对排列要多加一个 not used[i-1] 条件？2 回溯的复杂度怎么估、剪枝能改变量级吗？3 一、识别信号 ...

Posted by arganzheng | December 10, 2025

面试手撕代码（08）：堆、Top-K、区间与贪心

Heaps, Top-K, Intervals and Greedy: Sort by the Right Key

这一篇把三类”看起来不同、写起来相似”的题放在一起：Top-K（第 K 大、前 K 个高频、数据流中位数）靠堆，区间（合并、插入、最少箭、会议室）靠按端点排序后一趟扫描，贪心（跳跃游戏、加油站、任务调度）靠一个能证明的局部最优选择。它们的共同点是——先决定按什么键排序或维护什么顺序，剩下的就是一趟循环。堆是”动态维护顺序”的工具；排序是”一次性确定顺序”；贪心是”证明这个顺序下的局部选择就是全局最优”。六道主讲题里，快速选择、双堆中位数、会议室 II 是面试的常客。本篇要回答的核心问题是：第 K 大用大小为 K 的最小堆还是快速选择？各在什么场景下更好？1 数据流中位数的两个堆怎样维持平衡、为什么每次插入要”先进一个堆再倒到另一个”？2 会议室 II ...

Posted by arganzheng | December 9, 2025

面试手撕代码（07）：二分——只有一个模板

Binary Search: One Template, First Position Where the Predicate Holds

二分是”人人都会、人人都写错”的算法：lo <= hi 还是 lo < hi、mid 还是 mid + 1、返回 lo 还是 hi，每次都要现场想一遍。根源在于把二分当成”在有序数组里找一个值”——那只是它最窄的用法。二分的本质是：在一个”假假假……真真真”的单调谓词序列上，找第一个真的位置。用这一个定义写一个 first_true(lo, hi, pred)，所有二分题——找值、找边界、旋转数组、找峰值、”答案二分”、值域二分——都变成”写出那个谓词”。这一篇七道主讲题全部用同一个函数。本篇要回答的核心问题是：为什么”第一个使谓词为真的位置”这一个模板能覆盖全部二分题？1 “答案二分”（吃香蕉、运输包裹、分割数组）怎样把最优化问题变成判定...

Posted by arganzheng | December 8, 2025

面试手撕代码（06）：图——BFS / DFS / 拓扑排序 / 并查集 / 最短路

Graphs: BFS, DFS, Topological Sort, Union-Find and Dijkstra

面试里的图题很少给你一张”图”——给的是网格、课程依赖、单词列表、账户邮箱，第一步是看出它是图：格子是节点、四邻是边；课程是节点、先修关系是有向边；单词是节点、改一个字母能到达是边。看出来之后，可用的算法只有五个：BFS（最短步数、按层扩散）、DFS（连通块、路径存在性）、拓扑排序（有向无环图的依赖顺序）、并查集（动态连通性）、Dijkstra（带权最短路）。这一篇六道主讲题每种一到两道，重点是建图和visited 放在哪——图题的 bug 多半出在这两处。本篇要回答的核心问题是： BFS 的 visited 标记应该在入队时打还是出队时打？1 拓扑排序怎样同时判断有没有环？2 并查集的路径压缩和按大小合并各起什么作用，写哪一个就够？3 一、识别信号...

Posted by arganzheng | December 7, 2025

面试手撕代码（05）：二叉树

Binary Trees: Three Questions Every Recursion Must Answer

二叉树是面试里出题最多的一类结构，因为它天然是递归的：一个节点的答案 = 用左右子树的答案拼出来。几乎所有树题都能用同一个框架写完——决定递归函数返回什么、在哪个位置（前 / 中 / 后序）处理当前节点、递归的终点是什么。难点不在代码长度（多数树题十行以内），而在返回值和”要更新的全局答案”不是一回事：直径、最大路径和、LCA 这类题，递归返回的是”向下的一条链”，答案在合并处产生。这一篇用七道主讲题把这个框架讲透，顺带把迭代遍历、层序、序列化、BST 的性质讲清。本篇要回答的核心问题是：递归函数”返回什么”和”更新什么”为什么常常不是同一个量？1 验证 BST 为什么不能只比较父子节点？2 前序 + 中序建树时，哈希表和递归指针各解决什么问题？3 ...

Posted by arganzheng | December 6, 2025

面试手撕代码（04）：链表

Linked Lists: Dummy Heads, Three Pointers and the Tortoise–Hare Proof

链表题不考算法，考手稳：指针改错一个顺序就丢掉半条链。它在面试里出现频率极高，因为十分钟内能看出一个人写代码是不是有章法——有没有用哑节点统一头节点的特殊情况、反转时三个指针的赋值顺序对不对、边界（空链表、单节点、恰好整除）有没有想到。这一篇把链表题的三个骨架（哑节点、三指针反转、快慢指针）讲透，六道主讲题覆盖反转家族、环、合并与排序，每道都画出指针的移动。本篇要回答的核心问题是：哑节点到底省掉了哪些特判？1 快慢指针相遇后，为什么一个指针回到头、两个同速再走就在环入口相遇？2 K 个一组反转怎样做到 O(1) 空间且代码不失控？3 一、识别信号题面里出现想到骨架 ...

Posted by arganzheng | December 5, 2025

面试手撕代码（03）：栈、单调栈与单调队列

Stacks, Monotonic Stacks and Monotonic Queues: Settle When You Pop

栈解决的是”最近的未完成事项“：括号匹配里最近一个没配对的左括号、表达式里最近一个还没结算的运算数、嵌套字符串里最近一个还没展开的 [。单调栈是它的特化——栈里的元素保持单调，于是”弹出”这个动作有了新含义：被弹出的元素在此刻找到了它右侧第一个更大（或更小）的数，左侧第一个更大的就是新栈顶。每日温度、柱状图最大矩形、接雨水都是这一句话。单调队列把同样的想法用在滑动窗口上：队首永远是窗口最值。这一篇的六道主讲题，前三道是普通栈（括号、解码、计算器），后三道是单调结构（每日温度、柱状图、滑窗最大值）。每道题的代码都短，但”弹出时结算什么”这一句必须想清楚。本篇要回答的核心问题是：单调栈里的元素弹出时，为什么左右两侧的边界同时确定了？1 柱状图最大矩形的...

Posted by arganzheng | December 4, 2025

面试手撕代码（02）：双指针与滑动窗口

Two Pointers and Sliding Windows: Monotonicity Turns O(n²) into O(n)

上一篇用哈希表换掉一层循环；这一篇不用额外空间，靠单调性做同一件事。两个指针都只往一个方向走，每个元素最多被每个指针经过一次，\(O(n^2)\) 的枚举就变成了 \(O(n)\)。它有三种形态：同向的滑动窗口（子串、子数组问题）、相向的对撞指针（有序数组的配对、面积、接雨水）、同向不同速的快慢指针（原地分区、链表中点）。三种形态的代码骨架都不到十行，难点全在什么时候动哪个指针——这个决定必须能用一句话证明”不动的那种情况不可能更优”。本篇要回答的核心问题是：滑动窗口的”右扩左收”什么时候成立、什么时候不成立？1 最小覆盖子串里”已满足的字符数”怎样让每一步都是 O(1)？2 接雨水的双指针为什么可以只看自己这一侧的最大值？3 一、识别信号 ...

Posted by arganzheng | December 3, 2025

Arganzheng's Blog