经典算法思想总结（含 LeetCode 题目推荐）

发表于2019-07-03|计算机基础

|浏览量:

这份题单按算法思想而不是题号组织，覆盖面试中最常考的九类方法。每道题只回答三个问题：它训练什么能力、难度如何、值不值得先做。必做题用来建立模板手感，选做题用来检验迁移能力。

使用方式

先确认自己能默写对应方法的核心代码，再动手表里的必做题；选做题放到第二轮复习。每做完一题，记录四件事：题目的识别信号、循环或递归的不变量、时间空间复杂度、卡住自己的边界样例。说不清这四点，等于没做。

二分查找

题目	难度	优先级	训练目标
704. 二分查找	简单	必做	固定区间定义，练循环条件与边界更新的一致性
34. 在排序数组中查找元素的第一个和最后一个位置	中等	必做	在基础模板上改造出左边界、右边界两种查找
35. 搜索插入位置	简单	选做	理解循环结束时指针位置的含义
875. 爱吃香蕉的珂珂	中等	选做	把”最小可行速度”抽象成单调判定，入门答案二分

双指针与滑动窗口

题目	难度	优先级	训练目标
26. 删除有序数组中的重复项	简单	必做	读写指针分工，理解原地覆盖
977. 有序数组的平方	简单	必做	利用”两端绝对值最大”从后向前填充
15. 三数之和	中等	必做	排序加左右收缩，重点在去重逻辑
142. 环形链表 II	中等	选做	快慢指针相遇点到入环口的推导
3. 无重复字符的最长子串	中等	必做	可变窗口何时扩右端、何时缩左端
76. 最小覆盖子串	困难	选做	窗口内计数状态的维护与匹配判断

DFS 与 BFS

题目	难度	优先级	训练目标
102. 二叉树的层序遍历	中等	必做	队列按层扩展，学会统计层数
200. 岛屿数量	中等	必做	把网格当隐式图，练遍历加访问标记
994. 腐烂的橘子	中等	选做	多源 BFS 与扩散轮次统计
127. 单词接龙	困难	选做	把字符串变换建模为无权图最短路

回溯

题目	难度	优先级	训练目标
78. 子集	中等	必做	每个元素”选与不选”的决策树
77. 组合	中等	必做	路径、选择列表、撤销选择的标准骨架
39. 组合总和	中等	选做	允许重复选取时的起始下标控制
51. N 皇后	困难	选做	约束检查与剪枝的完整演练

动态规划

题目	难度	优先级	训练目标
70. 爬楼梯	简单	必做	状态定义与转移方程的最小实例
322. 零钱兑换	中等	必做	完全背包式最优化，理解初始化含义
300. 最长递增子序列	中等	必做	子序列 DP，弄清 `dp[i]` 到底代表什么
416. 分割等和子集	中等	选做	0-1 背包可行性版本与空间压缩

贪心

题目	难度	优先级	训练目标
455. 分发饼干	简单	必做	排序后配对，体验贪心策略的成立条件
55. 跳跃游戏	中等	必做	维护最远可达边界这一不变量
435. 无重叠区间	中等	选做	按结束时间排序的经典区间贪心
45. 跳跃游戏 II	中等	选做	分层扩展求最少步数，与 BFS 对照

图论与位运算

题目	难度	优先级	训练目标
207. 课程表	中等	必做	入度数组加队列的拓扑排序，同时学会判环
547. 省份数量	中等	必做	并查集 `find`/`union` 与路径压缩模板
684. 冗余连接	中等	选做	用并查集定位第一条成环边
136. 只出现一次的数字	简单	选做	异或的消去性质，位运算入门

刷题顺序建议

推荐顺序是：二分、双指针与滑动窗口、DFS/BFS、回溯、动态规划、贪心、图论与位运算。理由在于依赖关系：二分练边界控制的基本功，窗口与双指针复用这份基本功；回溯依赖 DFS 的熟练度；DP 往往需要先在回溯或记忆化搜索上体会”重复子问题”；贪心的证明意识又建立在已经见过最优子结构之后。

执行时每个主题先刷完必做列，再回头补选做列；同一主题内不要连刷超过三道相似题，隔几天脱离题解重写一遍，比追加新题更能检验是否真正掌握。

文章作者: Dai Wei

文章链接: https://www.daiwei.biz/knowledge/cs-basics/algorithms/classical-algorithm-problems-recommendations/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Dai Wei！

扫码打赏

微信
支付宝

相关推荐

DFS 与 BFS 面试题总结：树、图、矩阵搜索与最短路径模板

DFS 与 BFS 是遍历状态空间的两种范式：一个借助栈一条路走到底再回退，一个借助队列按距离逐层扩散。二者的差别不在代码长短，而在”待处理节点按什么顺序取出”——正是这个顺序，决定了 DFS 擅长枚举与连通性，BFS 垄断无权图最短路。它解决什么问题树、图、矩阵、棋盘都可以抽象成状态图：节点是状态，边是状态间的转移。DFS 与 BFS 解决的是”如何不重不漏地访问所有可达状态”，并在此之上衍生出连通块统计、路径枚举、层级展开、最短步数等具体问题。面试很少让你背定义，而是给一座岛屿、一张课程表或一个迷宫，考察你能否把题目翻译成状态图，并选对遍历顺序。核心原理两种遍历共享同一个骨架：从起点出发，把邻居放入”待处理容器”，逐个取出并扩展新邻居。唯一区别是容器——DFS 用栈，后发现的邻居先处理，于是不断深入；BFS 用队列，先发现的先处理，于是同一层的节点一起扩展。DFS 的栈可以直接复用递归调用栈，代码极短；BFS 必须显式维护队列，而”层”的信息天然保存在队列长度的快照里。访问标记是两条范式的共同生命线：图有环、矩阵相邻互通，不标记就会死循环。经验法则是入容器时就标记，...

动态规划面试题总结：状态转移、背包、子序列与 Java 模板

动态规划解决的是「子问题被反复求解」的浪费：把每个状态的答案存下来，后面直接查表，让指数级递归降回多项式时间。它的难点从不在代码长短，而在于状态定义必须精确到足以支撑后续所有决策。它解决什么问题很多最优化与计数问题都能拆成结构相同的子问题：爬 n 级台阶的方法数，取决于 n-1 级和 n-2 级；凑出金额 j 的最少硬币数，取决于 j 减去每种硬币面额之后的结果。直接对这类问题做朴素递归，同一个状态会被展开成天文数字次的重复调用——斐波那契递归树里 f(n-2) 出现两次、f(n-3) 出现三次，节点数随 n 指数膨胀。动态规划的核心动作只有一个：给每个状态分配一个格子，算过一次就存起来，从此以空间换时间，每个状态只求解一次。核心原理三个适用条件一个问题能用动态规划，需要同时满足三点：最优子结构：原问题的最优解由子问题的最优解组合而成。比如最短路径中，A 到 C 的最短路若经过 B，那么其中 A 到 B 那一段必然也是最短的。重叠子问题：不同分支会反复碰到同一个子问题，缓存才有价值。如果子问题彼此独立（如归并排序），那是分治，不是 DP。无后效性：一个状态的值确定...

双指针与滑动窗口面试题总结：数组、链表、字符串高频模板

双指针与滑动窗口常被并列提起，内核却是同一件事：两个指针各自只朝一个方向走，被跳过的候选永不再看。正是这份单调性，把暴力枚举的 O(n²) 压成了 O(n)。它解决什么问题子数组、子串、数对类问题，暴力枚举是 O(n²) 起步。但只要能论证「某位置被排除后绝不可能参与更优解」，指针就能放心单向移动、不再回头，枚举量坍缩为线性。三个典型形态：对撞指针两端收缩，快慢指针利用速度差，滑动窗口维护连续区间的状态。核心原理指针移动的合法性来自排除论证每次移动指针前必须回答：被跳过的配对为什么不可能更优？以有序数组两数之和为例，nums[l] + nums[r] < target 时只能移动左指针——左值搭配任何不超过 nums[r] 的数都更小，「当前左值 + 任意右值」整列候选被一次排除。移动的本质是裁剪搜索空间，而非碰运气。对撞指针：两数之和与盛水容器int[] twoSum(int[] nums, int target) { // nums 已排序 int left = 0, right = nums.length - 1; while (l...

回溯算法面试题总结：组合、排列、子集、剪枝与 Java 模板

回溯是带撤销机制的深度优先搜索：把所有候选方案组织成一棵决策树，逐层做选择、走不通就撤回重选，用一棵树的遍历完成全量枚举。它的威力不在聪明，而在「一个不漏、一步不冤」。它解决什么问题有一类问题的要求很「霸道」：列出所有组合、所有排列、所有可行解，或者答案藏在巨大的搜索空间里（如 N 皇后）。这类问题没法用一个公式直接算出，只能枚举。但裸枚举的代价是指数级的：n 个元素的全排列有 n! 种，子集有 2^n 种，靠蛮力双重循环根本写不完。回溯的价值在于把枚举系统化——按树形结构逐层展开，并在每个节点做合法性检查，把不可能长出答案的整棵子树提前砍掉，一步冤枉路都不走。核心原理决策树模型任何回溯问题都能画成一棵决策树：根节点是空方案，每向下一层就多做一个决定，叶子节点对应完整方案。以「从 1~3 中选 2 个数的组合」为例，第一层决定第一个数选谁，第二层在剩下的数里再挑一个，到达叶子时收集答案。所谓回溯代码，无非是对这棵树做深度优先遍历，外加一套「做完选择要记得撤销」的现场保护机制。三要素与通用模板动笔之前，先明确三件事：路径（path）：已经做出的选择，即从根到当前节点的...

算法专题：面试刷题路线、核心模板与 LeetCode 高频题

这是算法模块的学习地图。它把全部主题按依赖关系分成四层，给出推荐学习顺序，并用一句话说明每个主题解决什么问题，适合规划第一轮学习和面试前查漏补缺。第一层：基础工具这一层不直接产出算法，但决定后面所有题的实现质量。复杂度分析：用 Big O 在写代码之前判断方案是否可行，是一切优化的度量衡。数组与字符串：下标、区间与原地修改，承载双指针、前缀和等基础技巧。链表：纯指针操作，训练手写代码时对空节点与边界的控制。栈与队列：表达顺序约束——栈处理嵌套与未完成状态，队列处理层次与到达顺序。哈希表：用空间换平均常数查找，核心功夫在 key 的设计。第二层：搜索与枚举这一层开始解决”在解空间里找答案”的问题。排序：快排、归并、堆排的过程与稳定性，是许多算法的前置步骤。二分查找：利用单调性每次排除一半，并能从数组推广到答案空间。 DFS 与 BFS：显式与隐式图的两种遍历；BFS 额外承担无权最短路的职责。树：递归遍历与自底向上的信息汇总，二叉搜索树再叠加有序性。第三层：决策与优化这一层处理”从多种选择中找最优或全部方案”的问题。回溯：沿决策树枚举所有方案，...

十大经典排序算法总结

排序算法的评价从来不止”快”一个维度：时间、空间、稳定性是三把基本尺子。比较类排序无法突破 Ω(n log n) 的比较下界，非比较类则利用值域、分布、位数等额外信息换取线性时间。本文按”比较 vs 非比较”两大阵营梳理十种经典算法，重点拆透工程中最常用的快排与归并。它解决什么问题排序解决的是”为一组记录建立全序”的问题，它既是独立需求（排行榜、分页），也是其他算法的前置步骤（二分查找、去重、贪心）。选型的难点在于没有银弹：数据规模、初始有序度、值域范围、内存预算、稳定性要求，每一项都会改变最优解。理解排序的关键不是背十个名字，而是吃透四类机制：交换、插入、分治、计数。核心原理比较类：交换与插入一族冒泡排序：相邻元素两两比较、逆序即交换，每轮把最大值”浮”到末尾。加提前退出标志后最好 O(n)，平均与最坏 O(n²)，空间 O(1)，稳定。教学价值大于实用价值。选择排序：每轮从未排序区挑出最小值，放到已排序区末尾。任何输入都是 O(n²)，但交换次数最多 n-1 次，写入昂贵的场景偶有优势；不稳定。插入排序：像整理扑克牌，把新元素插进已排序区。近乎有序时 O(n)，...

评论

数据加载中