cswork / 解题思路打开题单

解题思路 · 决策树

读完题不知道用什么方法？回答几个是或否。

先看输入长什么样，再看题目问什么。几个回答之后，你会落到灵神题单精选 35 个专题中的一站：为什么是它、去哪刷题、读哪篇教程。这只是第一猜测，不是定理，有些题要组合两种方法。

查看全部 39 个问题

  1. Q01 题目要你实现一个类，它的几个方法会被反复调用吗？

    如 LRU 缓存、最小栈、迭代器

  2. Q02 要按 key 或按时间戳快速查询，或者维护一个不断流入的数据流（缓存、快照、中位数、第 k 大）？

    如 LRU 缓存、O(1) 时间插入删除和随机取值、基于时间的键值存储、数据流的中位数

    是

    第 33 站：缓存索引

    哈希表负责 O(1) 定位，双向链表或“和末尾交换”负责 O(1) 删除；按时间查就在有序列表上二分，数据流的中位数和第 k 大交给堆。

    去第 33 站刷题 教程：哈希表

  3. Q03 操作围绕字符串前缀或文件路径，或者要把一个结构编码成字符串再还原？

    如前缀树、内存文件系统、序列化二叉树

    是

    第 34 站：字典树序列化

    按字符或路径一层层往下建节点就是字典树；序列化时把空孩子也写出来，才能唯一还原。

    去第 34 站刷题 教程：字典树（Trie）

    否

    第 32 站：迭代器设计

    用栈、队列、数组和链表把接口拼出来，关键在摊还复杂度和空、满这些边界。

    去第 32 站刷题 教程：队列与双端队列

  4. Q04 输入描述的是“谁和谁相连”吗：树、图、网格，或者 A 依赖 B？

    给了 root、边列表、邻接表，或一个二维字符矩阵

  5. Q05 是一棵二叉树吗（给了 root，每个节点最多两个孩子）？

    节点类型是 TreeNode

  6. Q06 是二叉搜索树，并且可以利用“左小右大”的顺序？

    如二叉搜索树中第 K 小的元素、验证二叉搜索树

    是

    第 13 站：二叉搜索树

    BST 的中序遍历就是升序序列；查找、插入和第 k 小都只需沿一条路径往下走。

    去第 13 站刷题 教程：二叉搜索树

  7. Q07 要根据遍历序列把树建出来，或者把树改造成另一种形状？

    如从前序与中序遍历序列构造二叉树、二叉树展开为链表

    是

    第 12 站：树的构造

    前序（或后序）定根，中序分出左右子树，递归下去；改造类题先想清楚每个节点的指针最后指向哪里。

    去第 12 站刷题 教程：树的基础与遍历

  8. Q08 答案和路径有关吗：根到叶、路径和、两个节点的最近公共祖先、任意两点之间的最大路径？

    如路径总和 III、二叉树中的最大路径和

    是

    第 11 站：树上路径

    DFS 时把“当前路径的状态”往下传，把“子树里最好的结果”往上返回，答案在两者交汇的节点更新。

    去第 11 站刷题 教程：树形 DP：子树状态、路径和、树上背包与换根

  9. Q09 每个节点都要决定选或不选，而且父子之间互相限制？

    如打家劫舍 III

    是

    第 31 站：树形博弈

    后序遍历，每个节点返回“选它”和“不选它”两个值，父节点据此组合，这就是树形 DP。

    去第 31 站刷题 教程：树形 DP：子树状态、路径和、树上背包与换根

    否

    第 10 站：树的遍历

    先决定用前序、中序、后序还是层序，再想清楚递归函数返回什么，多数题就是一次遍历。

    去第 10 站刷题 教程：树的基础与遍历

  10. Q10 要在棋盘或字符矩阵上试着填数、放子或走一条路，走不通就撤回重来？

    如单词搜索、单词搜索 II、解数独

    是

    第 21 站：剪枝搜索

    DFS 前先标记当前格子，这条路失败就恢复原状，再试下一个方向或数字；用集合或位掩码记下每行、每列、每宫已用的数字，尽早剪枝。

    去第 21 站刷题 教程：回溯与 DFS 搜索（含剪枝）

  11. Q11 是二维网格，每个格子只和上下左右相邻？

    如岛屿数量、腐烂的橘子、不同路径

  12. Q12 每个格子的答案只取决于它上方和左方的格子（比如只能向右或向下走）？

    如不同路径、最小路径和、最大正方形

    是

    第 23 站：网格动规

    dp[i][j] 由上方和左方推出，按行填表；通常只留一行也够。

    去第 23 站刷题 教程：动态规划基础：状态、转移、LCS 与 LIS

    否

    第 14 站：网格搜索

    数连通块就用 DFS 或 BFS 把整块“淹掉”；求最少步数或同时扩散，用（多源）BFS 一层层推进。

    去第 14 站刷题 教程：图与网格上的广度优先搜索（BFS）

  13. Q13 边表示先后依赖，要排出一个合法顺序，或者判断依赖里有没有环？

    如课程表、火星词典

    是

    第 16 站：拓扑排序

    反复取出入度为 0 的点（Kahn 算法）；如果有点始终取不出来，说明有环。

    去第 16 站刷题 教程：拓扑排序（Kahn 算法与 DFS）

  14. Q14 要求从起点到终点的最少步数或最小代价？

    如单词接龙、网络延迟时间、K 站中转内最便宜的航班

    是

    第 17 站：最短路

    边权都一样用 BFS，非负权用 Dijkstra；状态可以是“位置 + 额外信息”，比如还剩几次中转。

    去第 17 站刷题 教程：最短路：Dijkstra、Bellman-Ford 与 Floyd-Warshall

  15. Q15 要挑一些边把所有点连起来，并让总代价最小？

    如连接所有点的最小费用

    是

    第 18 站：生成树

    把边按代价排序，用并查集逐条加入不会成环的边（Kruskal）；稠密图也可以用 Prim。

    去第 18 站刷题 教程：最小生成树：Kruskal 与 Prim

    否

    第 15 站：并查集

    只关心谁和谁连通、有几个连通块，或者边一条条加进来时，用并查集；一次 DFS 也常常够用。

    去第 15 站刷题 教程：并查集

  16. Q16 输入是链表吗？

    如反转链表、环形链表、删除链表的倒数第 N 个结点

    是

    第 09 站：链表

    哑节点省掉头节点的特判，快慢指针找中点和环，三个指针原地反转，几乎覆盖所有链表题。

    去第 09 站刷题 教程：链表技巧

  17. Q17 要列出所有满足条件的方案（子集、排列、组合），而不只是数一数有几个？

    如子集、全排列、组合总和；三数之和这类只挑两三个数凑目标和的题答否

  18. Q18 是把一个字符串切成几段，或者拼出合法的字符串？

    如括号生成、分割回文串、复原 IP 地址

    是

    第 20 站：拆分构造

    每一步决定从当前位置切多长，切出来的这段合法才继续往下递归。

    去第 20 站刷题 教程：回溯与 DFS 搜索（含剪枝）

  19. Q19 约束很多，必须边搜边剪枝，比如在棋盘上摆棋子、用四张牌凑出 24？

    如 N 皇后、N 皇后 II、24 点游戏

    是

    第 21 站：剪枝搜索

    用集合或位掩码记录已经占用的行、列和格子，一冲突就立刻回退，剪枝决定能不能在时限内跑完。

    去第 21 站刷题 教程：回溯与 DFS 搜索（含剪枝）

    否

    第 19 站：回溯枚举

    画出递归树：子集看每个元素选不选，排列看每个位置放谁；先排序再跳过相同的相邻元素来去重。

    去第 19 站刷题 教程：回溯与 DFS 搜索（含剪枝）

  20. Q20 输入是一组区间 [开始, 结束]？

    如合并区间、插入区间、无重叠区间、用最少数量的箭引爆气球

    是

    第 05 站：前缀和区间

    先按开始（或结束）排序再扫一遍：重叠就合并，要留下最多不重叠区间就按结束时间贪心；要数同一时刻有几个重叠，就在端点上 +1 / −1 做差分。

    去第 05 站刷题 教程：贪心算法

  21. Q21 数组已经有序，或者答案具有单调性（x 可行，那么比 x 大的也都可行）？

    如两数之和 II、三数之和（先排序）、搜索旋转排序数组、爱吃香蕉的珂珂

  22. Q22 要在有序数组里找两三个数凑出目标和，或者从两端往中间收？

    如两数之和 II、三数之和、有序数组的平方

    是

    第 04 站：双指针滑窗

    左右指针各站一端：和太小就右移左指针，太大就左移右指针，O(n) 扫完；三数之和先固定一个数，剩下的照此处理。

    去第 04 站刷题 教程：双指针与滑动窗口

    否

    第 06 站：二分查找

    有序就别线性扫：找位置直接二分；“最大值最小”这类题就二分答案，再写一个 O(n) 的判定。

    去第 06 站刷题 教程：二分查找、二分答案与三分法

  23. Q23 问的是连续的子数组或子串？

    如无重复字符的最长子串、和为 K 的子数组、乘积最大子数组

  24. Q24 要找回文子串：最长的那个，或者一共有几个？

    如最长回文子串、回文子串

    是

    第 27 站：回文区间

    以每个字符和每对相邻字符为中心向两边扩，O(n²) 就够；也可以让 dp[i][j] 记录 s[i..j] 是否回文，按长度从短到长填。

    去第 27 站刷题 教程：区间 DP

  25. Q25 要的是一段连续元素的最大和或最大乘积，元素有正有负？

    如乘积最大子数组、环形子数组的最大和、删除一次得到子数组最大和

    是

    第 28 站：状态机

    只看“以 i 结尾的最好结果”，它只依赖 i−1；求乘积时要同时记最大和最小，因为负负得正。最基础的最大子数组和在第 01 站。

    去第 28 站刷题 教程：DP 状态设计：状态机与维度对调

  26. Q26 元素可能是负数，或者要统计和恰好等于 k 的子数组有几个？

    如和为 K 的子数组、连续数组

    是

    第 05 站：前缀和区间

    前缀和把区间和变成两个数之差，用哈希表记住前面出现过的前缀和；要批量给区间加值就用差分数组。

    去第 05 站刷题 教程：前缀和与差分数组

    否

    第 04 站：双指针滑窗

    元素非负或只关心字符种类时，右指针扩张、左指针收缩，每个元素进出窗口各一次，整体 O(n)。

    去第 04 站刷题 教程：双指针与滑动窗口

  27. Q27 要第 k 大、前 k 个，或者每个元素右边第一个更大（更小）的数？

    如数组中的第 K 个最大元素、每日温度、柱状图中最大的矩形

    是

    第 07 站：单调栈与堆

    第 k 大和前 k 个用大小为 k 的堆；“下一个更大的元素”和柱状图中的最大矩形用单调栈，每个元素只进出栈一次。

    去第 07 站刷题 教程：堆与优先队列

  28. Q28 要处理嵌套或成对的结构（括号、表达式、编码字符串），或者总是先处理最近放进去的那个？

    如有效的括号、字符串解码、基本计算器、小行星碰撞

    是

    第 07 站：单调栈与堆

    遇到左括号或新的一层就压栈，遇到右括号就弹出最近的那个来配对或结算；表达式求值再加一个运算符栈。

    去第 07 站刷题 教程：栈

  29. Q29 求最大值、最小值或方案数，并且前面的选择会影响后面还能怎么选？

    如爬楼梯、打家劫舍、零钱兑换、跳跃游戏

  30. Q30 要比较两个字符串（或两个序列）：匹配、编辑，或者找公共部分？

    如最长公共子序列、编辑距离、交错字符串

    是

    第 26 站：字符串动规

    dp[i][j] 表示 s 的前 i 个字符和 t 的前 j 个字符的答案，按末尾字符相等或不等分别转移。

    去第 26 站刷题 教程：动态规划基础：状态、转移、LCS 与 LIS

  31. Q31 和回文有关，或者答案要通过合并、拆分区间 [i, j] 得到？

    如最长回文子序列、戳气球

    是

    第 27 站：回文区间

    dp[i][j] 只依赖更短的区间，所以按区间长度从小到大计算。

    去第 27 站刷题 教程：区间 DP

  32. Q32 从一堆物品或数字里挑一些，凑出某个和或容量，问能不能凑、最少几个、有多少种？

    如零钱兑换、分割等和子集、目标和

    是

    第 24 站：背包计数

    外层枚举物品、内层枚举容量；每件只能用一次就倒序遍历容量，可以重复用就正序。

    去第 24 站刷题 教程：背包 DP：0/1、完全、多重背包与方案计数

  33. Q33 每一天只可能处于少数几种状态之一，比如持有或不持有股票、冷冻期？

    如买卖股票的最佳时机系列

    是

    第 29 站：股票买卖

    每天为每种状态（持有、不持有、冷冻）记一个最大收益，按天在状态之间转移。

    去第 29 站刷题 教程：DP 状态设计：状态机与维度对调

  34. Q34 可以跳着选元素，只要选出来的保持某种先后或大小关系（最长递增子序列一类）？

    如最长递增子序列、俄罗斯套娃信封问题

    是

    第 25 站：子序列

    dp[i] 表示以第 i 个元素结尾的最好结果，从前面所有能接上的 j 转移；O(n log n) 的写法用贪心加二分。

    去第 25 站刷题 教程：动态规划基础：状态、转移、LCS 与 LIS

  35. Q35 要把数组切成若干段，或者在时间轴上安排互不冲突的任务？

    如最低票价、规划兼职工作、分隔数组以得到最大和

    是

    第 30 站：分段调度

    dp[i] 表示处理完前 i 个元素（或到第 i 个时间点）的最优值，枚举最后一段从哪里开始。

    去第 30 站刷题 教程：动态规划基础：状态、转移、LCS 与 LIS

  36. Q36 能说清楚为什么每一步都选当前最好的，最后不会吃亏？

    如跳跃游戏、加油站、分发糖果

    是

    第 08 站：贪心调度

    先排序，或者一路维护“目前最远能到哪里”，再用交换论证说明换成别的选择不会更好。

    去第 08 站刷题 教程：贪心算法

    否

    第 22 站：动规入门

    先写清楚“第 i 步的答案由前面哪几步推出”，从记忆化搜索写起，再改成递推。

    去第 22 站刷题 教程：记忆化搜索与 DAG 上的 DP

  37. Q37 要找满足某种关系的一对元素，或者按某个特征分组、计数？

    如两数之和、字母异位词分组、最长连续序列

    是

    第 02 站：哈希计数

    边扫边把见过的值存进哈希表，或者给每一组算一个共同的 key（比如排序后的字符串）。

    去第 02 站刷题 教程：哈希表

  38. Q38 和二进制位、异或、只出现一次的数字，或者整数溢出边界有关？

    如只出现一次的数字、位 1 的个数、x 的平方根

    是

    第 35 站：位运算

    记住几条常用技巧：x & (x − 1) 去掉最低位的 1，a ^ a = 0，再注意 32 位整数溢出。

    去第 35 站刷题 教程：位运算：常用技巧、异或与位掩码

  39. Q39 主要工作是按规则解析或匹配一个字符串？

    如字符串转换整数、反转字符串中的单词、找出字符串中第一个匹配项的下标

    是

    第 03 站：字符串

    按规则一个字符一个字符地往前走，处理好空格、正负号和越界；找子串可以用 KMP。

    去第 03 站刷题 教程：面试中的字符串基础

    否

    第 01 站：原地数组

    多半是原地改数组：读写双指针、交换元素，或者先排序再扫一遍。

    去第 01 站刷题 教程：排序实战：内置排序与自定义比较