Dai Wei

字符串可视为字符序列，但工程上必须先确认字符模型：按字节、Unicode 码点还是用户看到的字素处理。纯 ASCII 题可用定长频次数组，字符集不确定时更适合哈希表，不能默认一个 char 就等于一个完整字符。 常见模型有四类。字符计数用于异位词和首次唯一字符；双指针适合回文、反转与有序字符串；滑动窗口维护连续子串的约束；模式匹配则关注如何避免主串指针反复回退。朴素匹配最坏 O(nm)，KMP 通过模式串的前缀信息，在失配时复用已知匹配，预处理与搜索合计 O(n+m)。 回文判断可从两端向中间走，忽略规则外字符后比较；最长回文子串可从每个中心向两侧扩展，时间 O(n²)、空间 O(1)。无重复最长子串用窗口记录字符最后位置，右端加入重复字符时，把左端跳到旧位置之后，整体 O(n)。 字符串拼接也有实践成本。循环中反复创建不可变字符串可能产生二次方复制，应使用可变缓冲区。哈希统计的空间是 O(字符集大小)，字符集固定时可视为常数，但表达时最好说明前提。 误区包括混淆子串与子序列、窗口收缩后忘记更新计数、Unicode 处理不当、KMP 前缀表定义前后不一致，以及使用切片导致隐藏...

链表题考查的不是随机访问，而是能否安全地改写连接关系。节点一旦断开，后续部分可能丢失，因此修改 next 前先保存下一节点，是最重要的操作纪律。哑节点能统一处理头节点被删除或替换的边界。 反转链表维护 prev、cur、next：保存 next=cur.next，令 cur.next=prev，再整体前移。循环结束后 prev 指向新头，时间 O(n)、空间 O(1)。合并两个有序链表则让尾指针每次接上较小节点，剩余链表最后整体接入。 快慢指针适合环与中点。快指针每次两步、慢指针一步，若相遇则有环；相遇后一个指针回到头部，二者同速前进，再次相遇点就是环入口。删除倒数第 k 个节点，可让快指针先走 k 步，再同步移动至慢指针位于待删节点前驱。 123456dummy.next = headfast = slow = dummyrepeat k times: fast = fast.nextwhile fast.next != null: fast = fast.next; slow = slow.nextslow.next = slow.next.next 多数操作只遍历一...

贪心算法在每一步选当前看来最有利的方案，并且不回头修改。它能成立的前提是局部最优可以扩展为全局最优；因此“看起来合理”不是证明，必须说明该选择不会排除更优答案。 区间调度是典型例子：希望选择最多个互不重叠区间，应按结束时间升序，每次选择与上一个不冲突且结束最早的区间。它给后续留下最大空间。交换论证可说明：任何最优解的第一个区间，都可替换为结束更早的选择而不减少后续数量。 跳跃类问题常维护当前能到达的最远位置。扫描到 i 时，若 i 已超过最远边界则不可达；否则更新 far=max(far,i+nums[i])。这不是枚举具体路径，而是压缩所有可达路径的信息。分配、合并和区间覆盖题也常通过排序后维护一个最有利边界解决。 排序通常占 O(n log n)，排序后的单次扫描为 O(n)；若输入已按需要排序，整体可降为线性。额外空间取决于排序实现和是否复制数据。 证明贪心可使用交换论证、领先性质或反证法。若无法证明，且早期选择会影响未来收益，就应考虑动态规划或搜索。误区是见到“最大、最小”便贪心、只凭样例确信策略，以及忽略相等端点是否冲突。小结：明确候选、选择标准和可行性边界，再给出...

DFS 沿一条路径深入到底再回退，BFS 按距离一层层扩展。二者都在遍历状态图，差别主要是待访问节点的组织方式：DFS 使用递归栈或显式栈，BFS 使用队列。 搜索前应定义三件事：一个状态包含什么、如何生成邻居、何时算访问过。图中必须用 visited 防止环；矩阵可用坐标集合或原地标记；树若只从父到子走，天然无环。DFS 适合连通块、路径枚举、拓扑相关探索；BFS 在每条边权相同的图中首次到达目标时即可得到最少边数。 1234567queue <- [start]; mark(start)while queue not empty: x <- pop_front() for y in neighbors(x): if not marked(y): mark(y) queue.push(y) 标记通常要在入队时完成，而不是出队时，否则同一节点可能被多个前驱重复加入。多源 BFS 可以把所有起点同时入队，常用于最近距离扩散。若边有非负不同权重，应改用 Dijkstra；存在负权边时，普通 BFS 更不适用。 邻接表表示下，DFS 与 ...

刷数据结构题应围绕“操作成本”展开。数组支持 O(1) 下标访问却不擅长中间插入；链表反之。哈希表用空间换平均常数查找；栈表达后进先出和未完成状态；队列表达层次与到达顺序；堆持续维护极值；树与图表示层级和一般关系。 数组训练可覆盖原地去重、区间合并、前缀和与双指针；链表重点是反转、环、合并和倒数节点；栈适合括号匹配、表达式、单调栈；队列适合 BFS 和滑动窗口；哈希表练计数、去重与映射；树要掌握前中后序、层序、递归信息汇总；图则练连通块、拓扑和最短路；堆用于 Top K 与多路归并。 解题步骤是先列出所需操作：是否频繁查键、取得最值、两端进出、按层扩展或保持有序。再选择让核心操作便宜的数据结构，并核算维护代价。例如优先队列取顶是 O(1)，但插入和删除顶通常是 O(log n)；哈希查找平均 O(1)，并不保证顺序和最坏性能。 训练同一结构时应加入变式：输入是否有序、数据是否流式、能否修改原数组、是否允许额外空间。这样才能理解方案适用范围。实现后至少测试空集合、单元素、重复元素、极值和退化结构。 误区包括按题目名猜结构、只记 API 不懂内部成本、遇到树就递归却忽略栈深，以及...

经典题的价值是覆盖可复用思想，而非提供待背答案。二分利用单调性缩小范围；分治把问题拆成独立子问题再合并；回溯枚举决策树；贪心做可证明安全的局部选择；动态规划缓存重复状态；DFS 与 BFS 负责遍历隐式或显式图。 训练时可按“识别—实现—证明—变式”推进。看到有序数组，先问能否二分或双指针；看到连续区间，考虑滑动窗口、前缀和；看到前 K 个，比较堆和快速选择；看到连通关系，考虑 DFS、BFS、并查集；看到最少次数，判断是否是无权最短路或 DP；看到所有组合，则画回溯树。 每题先给出暴力解和复杂度，再定位瓶颈。例如重复查询区间和，可用前缀和把单次查询从 O(n) 降为 O(1)，代价是 O(n) 预处理与空间；重复求同一递归状态，可记忆化；每次扫描极值，可用堆或单调结构。优化必须说明利用了何种约束。 复盘记录应包含：题目模型、关键不变量、易错边界、时间空间复杂度，以及如果条件变化方案会怎样。隔几天脱离答案重写，比连续刷相似题更能检验迁移能力。 误区是以题号替代知识结构、只追求最优代码、忽略数据规模提示，以及把模板当作正确性证明。小结：经典题应成为概念索引。能用自己的话说明为什...

回溯是深度优先搜索的一种写法：把候选方案看成一棵决策树，每层做一次选择，发现不可行就撤销，回到上一个分叉。组合关心选哪些，排列还关心顺序，子集则常在每个节点都收集答案。 统一步骤是：判断终止并记录快照；枚举当前层候选；跳过不合法选择；加入路径；递归下一层；撤销路径。伪代码如下： 1234567search(state): if complete(state): save(copy(path)) for choice in candidates(state): if invalid(choice): continue apply(choice) search(nextState) undo(choice) 去重必须分清层级。同一树层避免选相同值，可在排序后跳过相邻重复候选；同一路径避免重复使用元素，则用 used 数组。剪枝来自约束：剩余元素不足、当前和已超目标、当前方案不会优于最优解时，应提前返回。排序往往让这些判断更早生效。 若每个元素都有选或不选两种可能，搜索规模约 O(2^n)；全排列可达 O(n!)，保存每个答案还要乘路径复制成本。递归栈...

排序的本质是建立元素次序。评价算法不能只看速度，还要看是否稳定、是否原地、输入是否接近有序。冒泡、选择、插入都以两两比较为主，平均为 O(n²)；其中插入排序对近乎有序的小数组很友好，冒泡稳定但交换多，选择排序交换少却不稳定。 归并排序把序列递归拆半，再线性合并，时间始终为 O(n log n)，稳定但需 O(n) 辅助空间。快速排序选枢轴并分区，使较小元素在左、较大元素在右，再处理两侧；平均 O(n log n)、最坏 O(n²)，随机选枢轴和三数取中能降低退化概率。堆排序先建最大堆，反复把堆顶换到末尾并下沉，时间 O(n log n)、额外空间 O(1)，但不稳定。 希尔排序按逐渐缩小的步长做分组插入，表现依赖步长；计数排序统计每个值出现次数，适合值域不大的整数；桶排序先按区间分桶再分别排序；基数排序从低位或高位逐轮分配。这三类不是比较排序，条件合适时可接近 O(n+k)。 实践选择可概括为：小规模或近有序用插入；需要稳定且内存允许用归并；通用内存排序常用优化快排；要求稳定上界且空间紧张可考虑堆。误区是把“平均最快”当成任何数据都最快，也不要忽略稳定性——同分学生按原时间...

算法学习不是记答案，而是把题目翻译成模型。数组与字符串常对应双指针、滑动窗口和前缀和；有序性提示二分；“所有方案”常用回溯；局部选择可能是贪心；重复子问题则指向动态规划。树和图的核心是 DFS、BFS，优先队列适合持续取得极值，并查集适合动态连通。 一条有效路线是先掌握复杂度、数组、链表、栈、队列和哈希表，再学习排序、二分、递归与树遍历，最后进入回溯、贪心、动态规划和图算法。每学一种方法，都应整理四件事：适用信号、不变量、标准步骤、时间与空间代价。做题时先写暴力方案，它给出正确性基线；随后寻找重复计算、无效枚举或可利用的顺序。 通用过程可写成：明确输入输出和边界；估算规模允许的复杂度；选择数据结构；写出循环或递归不变量；用空输入、单元素、重复值和极端值验证；最后分析复杂度。错题复盘应记录“为何没识别模型”，而不是抄代码。 常见误区包括只刷数量、不隔日重做；背模板却不知道退出条件；把哈希操作永远视为 O(1)；过早追求最优而没有可运行基线。面试表达也应先说思路与正确性，再写代码和测试。 小结：题库只是训练素材，真正可迁移的是模型、不变量和复杂度意识。能从新题中识别旧结构，才算形...

复杂度描述输入规模增长时资源消耗的趋势，而不是程序精确运行秒数。Big O 给出渐近上界，分析时通常忽略常数和低阶项，因此 3n+20 记作 O(n)，但工程上常数、缓存和数据分布仍会影响真实表现。 顺序语句复杂度相加后取主导项；独立嵌套循环通常相乘；每轮将规模减半的循环是 O(log n)。不过不能只数循环层数：内层若总共只移动 n 次，双层写法仍可能是 O(n)。递归可画递归树：二分每层一个规模减半的问题，共 log n 层；归并每层总工作量为 n，有 log n 层，所以是 O(n log n)。 空间复杂度只统计随输入增长的额外空间。固定数量变量是 O(1)；长度为 n 的辅助数组是 O(n)；递归即便没有容器，也要计算调用栈。例如深度为 n 的递归占 O(n) 栈空间，平衡树递归深度通常为 O(log n)。输出本身是否计入，要在表达时说明口径。 最好、平均和最坏复杂度不可混为一谈。哈希表查询平均接近 O(1)，碰撞严重时可能退化；快速排序平均 O(n log n)，极端分区会到 O(n²)。摊还分析则把偶尔昂贵的扩容分摊到多次操作，动态数组追加因而可称摊还 O(1...