1. 算法面试的“地基”与“弹药库”最近和几个刚经历完秋招的朋友聊天发现一个挺有意思的现象大家刷的题量都不少动辄三五百道但面试时遇到一些基础算法的变形题或者面试官追问底层实现细节时还是会卡壳。问题出在哪不是题刷得不够多而是基础没打牢对经典算法的理解停留在“会用模板”的层面知其然不知其所以然。这就好比盖房子你收集了一堆高级建材各种花哨的框架、中间件但水泥标号不够、钢筋绑扎不牢房子盖得再高也经不起推敲。“2020最新-精选基础算法100题”这个标题乍一看可能觉得有点“过时”毕竟现在都2024年了。但恰恰是这种“基础”和“精选”才是应对技术面试最核心、最持久的竞争力。面试官考察的从来不是你刷了多少道最新的Hard题而是你对计算机科学最核心、最经典的那一套方法论掌握得有多扎实。动态规划的状态定义、回溯的剪枝策略、双指针的移动条件、各种排序算法的适用场景与时空复杂度……这些才是构成你算法能力的“原子”无论题目如何包装最终都会落到这些基础组件上。这100道题更像是一个精心设计的“弹药库”和“训练场”。它不是为了追求数量而是为了覆盖广度与深度。广度上它需要囊括数据结构数组、链表、树、图上的基本操作以及分治、贪心、回溯、动态规划等核心算法思想。深度上每一道题都应该能引申出对算法原理的探讨比如为什么快速排序在平均情况下最快Dijkstra算法不能处理负权边的根本原因是什么01背包问题的空间优化是如何推导出来的把这些基础打牢了再去看力扣热题100、剑指Offer甚至是竞赛题你会有一种“降维打击”的感觉因为复杂的题目在你眼中会被自动拆解成熟悉的基础模块。所以别被“2020”这个年份迷惑也别觉得“基础”二字意味着简单。真正吃透这100道基础题比你走马观花地刷500道题更有价值。接下来我们就抛开年份的标签回归算法本质一起拆解这份“面试必备”的精选清单应该如何构建与使用并深入几个核心算法点看看如何从“背答案”进化到“掌握思想”。2. 精选百题框架如何构建你的核心算法图谱盲目刷题是效率最低的学习方式。一份有价值的“精选100题”清单不应该是一堆题号的简单罗列而应该是一个有清晰脉络的知识体系。我们可以按照“数据结构”和“算法思想”两个维度来搭建这个框架确保覆盖全面且重点突出。2.1 按数据结构分类夯实操作基本功数据结构是算法的载体几乎所有问题都围绕着它们展开。这部分的目标是对每一种基本数据结构你都能熟练完成增删改查并理解其特性背后的代价。数组与字符串约20题这是出现频率最高的部分。重点不在于复杂的算法而在于对索引、边界、原地操作的精确控制。核心操作二分查找标准、寻找左右边界、双指针快慢指针、左右指针、滑动窗口、前缀和、差分数组。典型问题移除有序数组中的重复项快慢指针、两数之和哈希表或双指针、滑动窗口最大值、字符串的排列/子串问题、接雨水双指针或动态规划。深度思考为什么二分查找的循环条件是left right而不是滑动窗口适用于解决哪一类问题的共性如何证明一个字符串匹配算法如KMP的正确性KMP算法中的next数组到底表示什么它如何避免主串指针的回退这部分是理解更复杂算法的基础务必做到代码一次写对。链表约15题链表题考察的是指针操作和细心程度以及是否理解虚拟头节点、快慢指针等技巧的本质。核心操作链表反转递归与迭代、节点删除、环的检测与入口定位、合并有序链表、寻找中点。典型问题反转链表、删除链表的倒数第N个节点、环形链表II、合并K个升序链表优先队列、LRU缓存机制链表哈希表。深度思考递归反转链表时递归栈的空间复杂度是多少快慢指针找环入口的数学推导过程是怎样的虚拟头节点在处理哪些边界情况时能极大简化代码树与图约25题树是面试中的重中之重尤其是二叉树。图论问题通常不会太复杂但需要掌握基本的遍历方法。核心操作树的深度优先遍历DFS递归/迭代、广度优先遍历BFS、二叉搜索树BST的性质、树的序列化与反序列化、图的DFS/BFS、拓扑排序。典型问题二叉树的前中后序遍历、二叉树的最大深度/直径、二叉树的最近公共祖先、二叉搜索树中的搜索/验证、从前序与中序遍历序列构造二叉树、岛屿数量网格DFS、课程表拓扑排序。深度思考递归遍历树的时空复杂度如何分析Morris遍历如何做到O(1)空间复杂度为什么拓扑排序通常用BFSKahn算法而DFS需要记录状态Dijkstra算法和A算法的核心区别与联系是什么A算法中的启发函数如何设计才能保证找到最优解栈与队列约10题它们既是基础数据结构也是实现其他算法的辅助工具。核心操作单调栈、单调队列、用栈实现队列/用队列实现栈。典型问题有效的括号、最小栈、每日温度单调栈、滑动窗口最大值单调队列。深度思考单调栈通常用于解决“下一个更大元素”这类问题其核心思想是什么为什么单调队列能在O(1)时间内获取窗口最大值哈希表约5题哈希表是“以空间换时间”的典范关键在于理解其应用场景。核心操作利用哈希表实现快速查找、去重、计数。典型问题两数之和、字母异位词分组、最长连续序列。深度思考当数据范围已知且较小如只有小写字母时如何用数组替代哈希表进一步提升效率2.2 按算法思想分类提升解题方法论掌握了数据结构的基本功后需要学习如何用系统性的思想去解决问题。递归与回溯约10题这是理解深度优先搜索DFS和复杂问题拆解的关键。核心思想尝试与回退。把问题看作一棵决策树递归地探索所有可能路径不满足条件时回退。典型问题全排列、组合总和、N皇后、子集、括号生成。深度思考如何理解递归的“归”的过程回溯算法中“状态”的维护与恢复即“做选择”和“撤销选择”为什么至关重要如何对递归树进行剪枝以优化效率分治算法约5题“分而治之”将大问题分解为小问题递归解决后再合并。核心思想分解、解决、合并。关键在于如何定义子问题以及合并子问题的解。典型问题归并排序、快速排序、最大子数组和也可用DP、为运算表达式设计优先级。深度思考归并排序和快速排序的稳定性、时间复杂度、空间复杂度对比分治算法和动态规划在解决类似问题如最大子数组和时思路有何本质不同贪心算法约10题每一步都做出当前看来最优的选择希望导致全局最优。核心思想局部最优 - 全局最优。难点在于证明贪心策略的正确性。典型问题分发饼干、跳跃游戏、买卖股票的最佳时机II、区间调度问题如无重叠区间。深度思考为什么跳跃游戏可以用贪心如何证明贪心算法在什么情况下会失效例如部分背包问题可以用贪心但01背包问题不行。动态规划约20题面试中的“大魔王”也是区分度最高的部分。核心是定义状态和找到状态转移方程。核心思想最优子结构 重叠子问题。通过记忆化搜索或递推表格来避免重复计算。典型问题线性DP斐波那契数列、爬楼梯、打家劫舍、最大子数组和。背包问题01背包、完全背包、分割等和子集01背包变种、零钱兑换完全背包变种。必须亲手推导一遍状态转移方程并实现空间优化一维数组。序列DP最长递增子序列LIS、最长公共子序列LCS、编辑距离。区间DP最长回文子串、戳气球。状态机DP买卖股票系列问题含冷冻期、手续费等。深度思考如何从暴力递归回溯优化到记忆化搜索再优化到递推形式的动态规划01背包问题的一维优化为什么需要逆序枚举完全背包的一维优化为什么是正序dp数组的初始化有什么讲究如何打印出具体的解而不仅仅是最大价值3. 动态规划深度剖析从记忆化搜索到状态压缩动态规划是算法面试的皇冠而01背包问题又是这顶皇冠上最耀眼的明珠之一。很多人能背出模板但问到“为什么可以这样优化”时就哑火了。我们以经典的01背包问题为例彻底搞懂它的前世今生。问题描述有N件物品和一个容量为V的背包。第i件物品的体积是v[i]价值是w[i]。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。3.1 暴力递归一切思考的起点最直观的想法是对于每一件物品我们有两种选择放或者不放。这就形成了一个二叉决策树。def knapsack_recursive(i, c): i: 当前考虑第i件物品从0开始 c: 当前剩余背包容量 返回: 从第i件物品开始做选择能获得的最大价值 if i N: # 没有物品可选了 return 0 if c v[i]: # 当前物品体积大于剩余容量只能不放 return knapsack_recursive(i1, c) else: # 选择1: 不放当前物品 not_take knapsack_recursive(i1, c) # 选择2: 放当前物品 take knapsack_recursive(i1, c - v[i]) w[i] return max(not_take, take) # 初始调用 max_value knapsack_recursive(0, V)这个解法的时间复杂度是指数级的O(2^N)因为递归树有2^N个节点。但它清晰地定义了问题的状态(i, c)即“考虑前i件物品在剩余容量c下的最大价值”。3.2 记忆化搜索消除重叠子问题观察递归树你会发现很多状态被重复计算了。例如考虑物品[2...]在容量5下的最大价值可能会从不同的路径放/不放物品0放/不放物品1多次计算。这就是“重叠子问题”。 我们可以用一个二维数组memo[i][c]来记录已经计算过的状态。memo [[-1] * (V1) for _ in range(N)] def knapsack_memo(i, c): if i N: return 0 if memo[i][c] ! -1: return memo[i][c] # 已经计算过直接返回 if c v[i]: res knapsack_memo(i1, c) else: res max(knapsack_memo(i1, c), knapsack_memo(i1, c - v[i]) w[i]) memo[i][c] res # 记录计算结果 return res这样每个状态(i, c)最多只计算一次时间复杂度优化到了O(NV)空间复杂度也是O(NV)。记忆化搜索是自顶向下的它更符合我们自然的思考过程。3.3 递推DP Table自底向上的标准形式我们可以把递归过程反过来从基础情况开始逐步递推到最终答案。定义dp[i][j]为考虑前i件物品物品编号0到i-1在背包容量为j时能获得的最大价值。状态转移方程如果不放第i-1件物品dp[i][j] dp[i-1][j]如果放第i-1件物品前提是j v[i-1]dp[i][j] dp[i-1][j - v[i-1]] w[i-1]两者取最大值dp[i][j] max(dp[i-1][j], dp[i-1][j - v[i-1]] w[i-1])初始化dp[0][j] 0表示考虑0件物品时任何容量下价值都是0。dp [[0] * (V1) for _ in range(N1)] for i in range(1, N1): # 考虑前i件物品 for j in range(V1): # 当前背包容量 if j v[i-1]: dp[i][j] dp[i-1][j] # 放不下 else: dp[i][j] max(dp[i-1][j], dp[i-1][j - v[i-1]] w[i-1]) max_value dp[N][V]这个过程是自底向上的dp[i][j]依赖于dp[i-1][...]的值。3.4 空间优化滚动数组理解状态压缩的本质仔细观察状态转移方程你会发现dp[i][j]只依赖于上一行dp[i-1][...]的数据。也就是说我们不需要保存整个NV的表格只需要保存“上一行”和“当前行”即可。这就是“滚动数组”的思想可以将空间复杂度从O(NV)降到O(V)。更进一步的如果我们只用一个一维数组dp[j]来表示“容量为j的背包所能装下的最大价值”并且在更新时逆序枚举容量j就可以在覆盖旧数据之前完成所有依赖旧数据的计算。dp [0] * (V1) for i in range(N): # 遍历物品 for j in range(V, v[i]-1, -1): # 逆序遍历容量 dp[j] max(dp[j], dp[j - v[i]] w[i]) max_value dp[V]为什么必须逆序这是理解01背包优化的关键。dp[j]在更新时需要用到dp[j - v[i]]这个值是“考虑完当前物品i之前”的状态。如果正序遍历当更新到dp[j]时dp[j - v[i]]可能已经在同一轮循环同一个i中被更新过了它代表的是“已经考虑了当前物品i”的状态这就相当于同一件物品被放了多次变成了“完全背包”的逻辑。逆序遍历保证了在更新dp[j]时dp[j - v[i]]还是上一轮i-1的值符合01背包“每个物品最多选一次”的规则。3.5 举一反三完全背包的空间优化理解了01背包的逆序原理完全背包每件物品无限个的空间优化就很好理解了。完全背包的状态转移方程是dp[i][j] max(dp[i-1][j], dp[i][j - v[i-1]] w[i-1])。注意这里第二个项是dp[i][j - v[i-1]]因为放了物品i-1后还可以继续放i-1。那么在一维数组优化时我们只需要把容量j的遍历顺序改为正序即可。dp [0] * (V1) for i in range(N): for j in range(v[i], V1): # 正序遍历容量 dp[j] max(dp[j], dp[j - v[i]] w[i])正序保证了在计算dp[j]时dp[j - v[i]]已经是考虑过当前物品i的状态从而实现了物品的无限次选取。核心心得动态规划的空间优化本质上是观察状态转移的依赖关系。如果当前状态只依赖于上一行的某些列如01背包就可以用滚动数组或一维数组逆序优化。如果依赖于本行前面的列如完全背包就用一维数组正序。死记硬背容易混淆理解依赖关系才是根本。4. 排序算法动图解析与实战选型排序是算法的基础面试中不仅要求会写更要求理解其原理、稳定性、时间/空间复杂度以及适用场景。结合动图来理解排序过程非常直观但动图看完必须自己动手推导一遍过程并思考其优缺点。4.1 快速排序分治思想的典范快速排序是面试最高频的排序算法平均时间复杂度O(n log n)但不稳定。核心思想选择一个“基准”pivot将数组分成两部分左边都小于等于基准右边都大于等于基准然后递归地对左右两部分排序。关键步骤Lomuto分区方案选择最右元素作为基准pivot。初始化一个指针i指向“小于等于pivot区域”的末尾初始为low-1。遍历j从low到high-1。如果arr[j] pivot则i并交换arr[i]和arr[j]。这保证了i及其左边的元素都pivot。遍历结束后i1的位置就是pivot应该在的位置。交换arr[i1]和arr[high]。返回i1作为分区点。def partition(arr, low, high): pivot arr[high] # 选择最右元素为基准 i low - 1 # 小于等于pivot区域的边界 for j in range(low, high): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i1], arr[high] arr[high], arr[i1] return i 1 def quick_sort(arr, low, high): if low high: pi partition(arr, low, high) quick_sort(arr, low, pi-1) quick_sort(arr, pi1, high)时间复杂度分析最好/平均情况每次分区都能将数组大致平分递归树深度为O(log n)每层处理O(n)个元素故为O(n log n)。最坏情况数组已排序或逆序每次分区只减少一个元素递归树退化为链表深度为O(n)故为O(n^2)。优化策略随机化基准随机选择low到high之间的一个元素与arr[high]交换再执行上述分区。这能极大避免最坏情况的发生。三数取中选择arr[low]、arr[mid]、arr[high]的中位数作为基准。小数组切换插入排序当递归到子数组长度较小如15时使用插入排序因为插入排序在小数据量上常数项更小。4.2 归并排序稳定排序的标杆归并排序是稳定的O(n log n)排序但需要O(n)的额外空间。核心思想分治。将数组递归地分成两半分别排序然后将两个有序数组合并成一个。关键步骤合并申请一个临时数组temp大小与arr[low...high]相同。设定两个指针i和j分别指向左右两个有序子数组的起始位置。比较arr[i]和arr[j]将较小的放入temp并移动对应指针。重复步骤3直到一个子数组被取完。将另一个子数组剩余部分直接复制到temp末尾。将temp中的数据拷贝回原数组arr[low...high]。def merge_sort(arr, low, high): if low high: return mid (low high) // 2 merge_sort(arr, low, mid) merge_sort(arr, mid1, high) merge(arr, low, mid, high) def merge(arr, low, mid, high): temp [] i, j low, mid1 while i mid and j high: if arr[i] arr[j]: # 这里用 保证了稳定性 temp.append(arr[i]) i 1 else: temp.append(arr[j]) j 1 while i mid: temp.append(arr[i]) i 1 while j high: temp.append(arr[j]) j 1 arr[low:high1] temp时间复杂度分析递归树深度为O(log n)每层合并操作的总时间复杂度为O(n)故总为O(n log n)。无论数据如何分布性能都很稳定。空间复杂度O(n)主要用于合并时的临时数组。递归调用栈深度为O(log n)但通常不计入主要空间开销。4.3 堆排序原地的不稳定排序堆排序利用“堆”这种数据结构平均和最坏情况都是O(n log n)且是原地排序空间复杂度O(1)但不稳定。核心思想建堆将无序数组调整成一个大顶堆父节点值 子节点值。排序将堆顶元素最大值与堆末尾元素交换此时最大值已就位。然后将剩余元素重新调整成大顶堆重复此过程。关键操作下沉def heapify(arr, n, i): 将以i为根的子树调整为大顶堆 n: 堆的当前有效长度 i: 当前需要下沉的节点索引 largest i left 2 * i 1 right 2 * i 2 if left n and arr[left] arr[largest]: largest left if right n and arr[right] arr[largest]: largest right if largest ! i: arr[i], arr[largest] arr[largest], arr[i] heapify(arr, n, largest) # 递归下沉排序过程def heap_sort(arr): n len(arr) # 1. 建堆从最后一个非叶子节点开始自底向上调整 for i in range(n//2 - 1, -1, -1): heapify(arr, n, i) # 2. 排序 for i in range(n-1, 0, -1): arr[0], arr[i] arr[i], arr[0] # 将堆顶最大值交换到末尾 heapify(arr, i, 0) # 对剩余i个元素重新建堆时间复杂度分析建堆过程时间复杂度为O(n)排序过程进行n-1次调整每次调整堆顶下沉时间复杂度为O(log n)故总为O(n log n)。4.4 实战选型指南了解了原理在实际编码或面试中如何选择快速排序是绝大多数语言标准库如C的sort Java的Arrays.sort对基本类型的默认选择。因为它平均性能好且是原地排序。当需要原地、高效的通用排序时选它。但要警惕最坏情况可以通过随机化来避免。归并排序稳定且性能稳定在O(n log n)。当排序稳定性是硬性要求或者数据是链表形式链表归并排序不需要额外空间时选它。也常用于外部排序数据量太大无法全部加载到内存。堆排序原地、时间复杂度稳定。当对空间有严格限制不能使用O(n)额外空间又需要稳定的O(n log n)性能时选它。也常用于解决Top K问题维护一个大小为K的小顶堆。插入排序/冒泡排序时间复杂度O(n^2)仅适用于数据量极小n 50或基本有序的情况。在快速排序/归并排序的递归基中会用到。计数排序/桶排序/基数排序非比较排序时间复杂度可达O(n)但有特定适用条件如数据范围已知且较小。在满足条件时是性能杀手锏。面试高频考点手写快速排序的partition函数、归并排序的merge函数、堆排序的heapify函数。务必做到一次写对并能分析其时间/空间复杂度及稳定性。5. 面试实战如何高效刷题与应对考察刷题不是为了背题而是为了训练思维形成条件反射。面对一份“精选100题”如何最高效地利用它并在面试中发挥出来5.1 刷题方法论五步刷题法第一遍独立思考暴力起步。拿到题目不要立刻看答案或提示。先自己思考哪怕只想出最暴力的解法比如O(n^2)的双重循环。动手把暴力解法写出来确保能通过部分测试用例。这一步是理解问题本质的关键。第二遍分析优化寻找规律。分析暴力解法慢在哪里有没有重复计算数据结构是否合适尝试在纸上画图列举小规模例子寻找规律。思考能否用哈希表、双指针、排序、栈、队列等数据结构优化问题是否具有最优子结构动态规划或贪心选择性第三遍学习优质题解对比差距。在自己思考到“山穷水尽”或写出一个解法后去查看官方题解或高票讨论。重点关注思路别人的解题切入点是什么和我的有什么不同代码实现边界条件如何处理变量命名、代码结构是否清晰优雅复杂度分析对方分析的对吗有没有更优的解法举一反三这道题和之前做过的哪道题类似属于哪个分类第四遍闭卷重现内化吸收。关上题解完全靠自己把最优解法重新写一遍。包括所有的边界条件。如果卡住了就再回顾思路但不要抄代码。直到能独立、流畅地写出AC的代码。第五遍定期回顾总结归纳。根据艾宾浩斯遗忘曲线定期比如1天后、1周后、1月后回顾这道题。不是重写代码而是复述思路“这是一道XX类型的题核心思想是XX关键步骤是XX易错点是XX”。把题目归类到自己的知识图谱中。5.2 面试中的沟通技巧展现思考过程面试官考察的不仅是最终答案更是你解决问题的过程。明确问题拿到题目后先和面试官确认理解是否正确可以举一两个例子说明。例如“请问这个‘最长连续序列’是指数值上连续还是索引上连续我举个例子数组[100, 4, 200, 1, 3, 2]的最长连续序列是[1,2,3,4]对吗”阐述思路不要沉默地写代码。一边想一边说“我首先想到的是暴力解法两层循环枚举所有子序列复杂度是O(n^2)。但这显然不是最优的。我注意到连续序列这个条件也许我们可以用哈希表来快速判断一个数的相邻数是否存在。我们可以先把所有数存入哈希集合去重然后遍历集合只从‘序列的起点’即num-1不在集合中开始向上计数。这样每个数字最多被访问两次时间复杂度是O(n)。”讨论权衡如果有多解可以提出来并分析利弊。“除了哈希集合的方案我们也可以先排序再遍历时间复杂度O(n log n)空间O(1)。在数据量不大且对空间有严格要求时排序法可能更合适。但考虑到一般情况哈希法的时间复杂度更优我选择实现哈希法。”处理卡壳如果一时没有思路可以尝试简化问题先考虑特殊情况如数组已排序、没有重复元素。画图/举例在共享白板上画图列举一个小型测试用例手动模拟过程。回溯已知算法“这个问题让我想起了‘并查集’可以处理连通性但这里是数值连续可能用哈希表更直接。”写完代码后主动走查代码用之前举的例子测试一下分析时间复杂度和空间复杂度。5.3 针对“八股文”与深度追问的应对除了手写代码面试官还可能问一些理论问题。关于复杂度不仅要会背更要会推导。比如被问到“快速排序为什么平均是O(n log n)”你可以从递归树和期望的角度解释如果每次划分比较均衡递归树深度约为log n每层partition操作总计O(n)。关于稳定性能清晰说出常见排序算法的稳定性归并、插入、冒泡稳定快排、堆排、选择不稳定并解释原因。例如“快速排序在交换元素时可能把相等的元素交换到不同侧所以不稳定。”关于应用场景“如果给你一个100GB的日志文件要按时间排序内存只有2GB你会用什么排序”答案外部排序通常使用多路归并。关于语言细节比如Java中Arrays.sort()对基本类型和对象排序分别用了什么算法双轴快速排序和TimSort后者是归并和插入的混合排序。这份“精选基础算法100题”的价值就在于它为你搭建了一个坚实、全面的算法知识框架。当你通过这100道题真正理解了背后的数据结构与算法思想你就拥有了拆解任何新问题的“武器库”。面试时你看到的将不再是孤立的题目而是一个个由基础模块组合而成的拼图。这时你的从容与自信就是最好的答案。