LeetCode 面试题三大板块全攻略：算法数据结构数学，实用模板提升解题能力

还有背包问题，01 背包和完全背包的区别在于物品能不能重复选，状态定义都是 dp [i][j] 表示前 i 个物品装进容量为 j 的背包的最大价值。01 背包的转移方程是 dp [i][j] = max (dp [i-1][j], dp [i-1][j-weight [i]] + value [i])，因为第 i 个物品要么不选，要么选，选的话就得看容量够不够。完全背包因为可以重复选，所以内层循环容量的时候要从前往后遍历，而 01 背包是从后往前，避免重复选同一个物品。做动态规划题一定要多刷题，积累不同类型的状态定义和转移方程，慢慢就能找到感觉。

贪心算法的关键是找到正确的贪心策略，也就是每一步都做当前最优的选择，最终能得到全局最优解。比如活动选择问题，选择结束时间最早的活动，这样能给后面留更多时间。还有跳跃游戏，维护一个当前能到达的最远距离，每次遍历到一个位置，就更新这个最远距离为 max (最远距离，当前位置 + 跳跃距离)，如果当前位置超过了最远距离，就说明跳不到，返回 false，否则遍历完返回 true。

贪心策略的正确性有时候需要数学证明，比如哈夫曼编码，通过构建最优二叉树来证明贪心选择的正确性。不过平时做题的时候，只要能通过测试用例，并且逻辑上符合局部最优推全局最优的思路，就可以尝试用贪心算法。贪心算法的优势在于时间复杂度低，代码简洁，但是适用场景有限，需要仔细分析题目是否满足贪心的条件，比如是否具有最优子结构和贪心选择性质。

数组和链表是最基础的数据结构，它们的特点决定了适用场景不同。数组随机访问速度快，但是插入和删除需要移动元素，适合频繁查询的场景。链表插入删除方便，但是随机访问需要遍历，适合频繁修改的场景。比如反转链表，用迭代的方法，定义三个指针，前驱、当前、后继，每次让当前的 next 指向前驱，然后三个指针依次后移，直到当前为空，前驱就是新的头节点。

操作数组的时候要注意下标越界，尤其是在处理滑动窗口、双指针问题时，比如求数组中元素和为目标值的连续子数组，用双指针 left 和 right 表示窗口的左右边界，sum 表示窗口内元素和，当 sum 大于目标值时，left 右移，减少窗口内元素和，当 sum 小于目标值时，right 右移，增加元素和，直到找到符合条件的窗口。链表操作则要注意头节点的处理，很多时候需要创建一个虚拟头节点，方便操作，比如合并两个有序链表，虚拟头节点的 next 指向合并后的链表，然后用一个指针遍历，比较两个链表当前节点的值，把小的接到后面，直到其中一个链表为空，再把另一个链表剩下的部分接上。

树的遍历方式有前序、中序、后序的深度优先遍历，还有层次遍历的广度优先遍历。二叉树的中序遍历对于二叉搜索树来说是有序的，这一点经常被用来解决相关问题，比如判断一个二叉树是否是二叉搜索树，就可以通过中序遍历，看结果是否单调递增。层次遍历通常用队列来实现，每次把当前层的节点加入队列，然后遍历队列中的节点，把它们的左右孩子加入下一层的队列，直到队列为空。

图的遍历有深度优先搜索（DFS）和广度优先搜索（BFS），DFS 用递归或者栈实现，BFS 用队列实现。比如判断图中是否存在环，对于有向图和无向图方法不同，无向图在遍历的时候如果发现一个节点的邻接节点已经访问过，并且不是父节点，就说明有环；有向图需要记录节点的访问状态，分为未访问、正在访问、已访问，在 DFS 过程中，如果遇到正在访问的节点，就说明有环。树和图的问题很多时候需要递归的思路，把问题分解成子问题，比如求树的深度，就是左子树深度和右子树深度的最大值加 1。

栈是后进先出，常用于处理需要逆序的问题，比如括号匹配，遇到左括号入栈，遇到右括号就和栈顶的左括号匹配，匹配成功就出栈，否则不合法。还有中缀表达式转后缀表达式，利用栈来存储运算符，根据优先级决定何时入栈和出栈。队列是先进先出，常用于层次遍历、广度优先搜索，还有滑动窗口问题，比如求滑动窗口内的最大值，用双端队列来维护窗口内的元素下标，保证队列中的下标对应的元素是递减的，这样队头就是最大值的下标，窗口滑动时，移除不在窗口内的下标，然后把新元素下标加入队列，同时移除队列中比它小的元素下标，保持队列的递减性。

栈和队列还有一些变形，比如单调栈，用来解决下一个更大元素的问题，遍历数组时，维护一个单调递减的栈，当遇到一个元素比栈顶元素大时，栈顶元素的下一个更大元素就是当前元素，弹出栈顶，直到栈为空或者当前元素不大于栈顶元素，然后将当前元素下标入栈。这些特殊的数据结构用法需要多练习，才能在遇到问题时想到合适的工具。

遇到大数运算时，比如两个超大数相加、相乘，不能直接用基本数据类型存储，需要用字符串或者数组来处理。大数相加，先将两个字符串反转，方便从低位开始相加，然后逐位相加，记录进位，最后再反转得到结果。大数相乘，用一个数组存储每一位的乘积，长度为两个数长度之和，然后按位相乘，累加到对应的位置，最后处理进位，去掉前导零。

模运算在数学题中很常见，比如求 (a*b)% m，可以先分别对 a 和 b 取模，再相乘取模，避免溢出。还有快速幂算法，求 a 的 n 次方模 m，用二进制拆分 n，把指数分解成 2 的幂次之和，每次平方取模，根据二进制位是否为 1 来决定是否乘到结果中，这样时间复杂度是 O (logn)，比直接循环相乘高效很多。处理负数的模运算时，要注意不同语言的取模规则，通常可以通过加上模数再取模来保证结果为正。

质因数分解可以用试除法，从 2 到根号 n 依次试除，记录每个质因数的指数。比如分解 n，当 i 能整除 n 时，就不断除以 i，记录 i 的次数，直到不能整除，i++，直到 i*i>n，最后如果 n>1，说明还有一个质因数是 n 本身。最大公约数（GCD）常用欧几里得算法，也就是辗转相除法，gcd (a,b)=gcd (b,a% b)，直到 b 为 0，返回 a。求多个数的 GCD，可以依次求两个数的 GCD。

还有扩展欧几里得算法，用于求解 ax+by=gcd (a,b) 的一组整数解，这在求解同余方程时很有用。欧拉定理和费马小定理也是数论中的重要知识，费马小定理指出如果 p 是质数，a 和 p 互质，那么 a^(p-1)≡1 mod p，这可以用来简化幂运算的模运算。遇到与质因数、公约数、倍数相关的问题时，先考虑数论的基本方法，往往能找到高效的解法。

排列组合问题需要分清楚是排列还是组合，排列考虑顺序，组合不考虑。计算排列数和组合数时，当 n 和 k 较大时，直接计算阶乘可能会溢出，需要用动态规划或者递推的方式，比如组合数的递推公式 C (n,k)=C (n-1,k)+C (n-1,k-1)。还有隔板法，用于解决相同元素分组的问题，比如把 n 个相同的球放进 k 个不同的盒子，允许空盒，方法数是 C (n+k-1,k-1)。

排列组合常和动态规划结合，比如求不同路径数，从左上角到右下角，只能向右或向下走，网格有 m 行 n 列，那么 dp [i][j]=dp [i-1][j]+dp [i][j-1]，初始条件 dp [0][0]=1，第一行和第一列都只有一种走法。还有错排问题，n 个元素的错排数 D (n)=(n-1)*(D (n-1)+D (n-2))，这些问题需要理解背后的数学原理，再结合动态规划的状态转移来解题。

【该文章由dudu123.com嘟嘟 ai 导航整理，嘟嘟 AI 导航汇集全网优质网址资源和最新优质 AI 工具】