大公司笔试面试有哪些经典算法题目？
好的，聊到大厂笔试面试的算法题，那可真是个“老生常谈”的话题，不过里面门道可多着呢。其实并不是所有大厂都考一模一样的题，但有些经典的类型，几乎是“必杀技”，无论是阿里、腾讯、字节、还是美团，都会在某种程度上涉及。下面我就结合我的经验，尽可能详细地给大家掰扯掰扯这些“常客”，力求讲得接地气，就像跟老朋友聊天一样。
咱们把这些题目分类来看，这样更容易理解它们考察的核心能力。
一、 基础数据结构与算法的“基石”
这是所有算法面试的起点，也是最重要的部分。如果你这块儿基础不牢，后面再复杂的题目都很难驾驭。
1. 数组与字符串（Arrays & Strings）
问题类型：
查找类： 两数之和、三数之和、查找重复的数字/缺失的数字。
排序类： 有序数组的查找、合并两个有序数组、原地排序（如快速排序、归并排序的变种）。
滑动窗口类： 最长无重复字符的子串、包含所有字符的最短子串、连续子数组的最大和。
字符串处理： 反转字符串、判断回文字符串、字符串匹配（如KMP）、最长公共前缀/后缀。
子序列/子数组： 寻找特定子序列、子数组的某种属性。
为什么考？ 数组和字符串是最基础的数据结构，几乎所有编程都会用到。考察的是你对内存访问、指针操作（虽然很多语言封装了）、遍历技巧以及优化思路的理解。
怎么准备？
两数之和 (Two Sum): 这题简直是算法面试的“入门券”。思路就是用一个哈希表（HashMap/Dictionary）来存储已经遍历过的数字及其索引。当遍历到一个数字 `x` 时，检查哈希表中是否存在 `target x`。如果有，就找到了；如果没有，就把 `x` 和它的索引存进去。时间复杂度 O(n)，空间复杂度 O(n)。
滑动窗口： 这个思路的核心是维护一个窗口，窗口的起始和结束位置随着遍历不断移动。窗口的大小是动态调整的，目的是在满足某个条件的情况下，找到最优解（最大、最小、最短、最长等）。比如找最长无重复字符的子串，窗口内字符用一个集合（Set）或哈希表记录频率，如果遇到重复字符，就移动窗口的左边界，直到窗口内字符再次不重复。
原地排序： 很多题目会要求空间复杂度是 O(1)。这就需要你对一些原地排序算法（如插入排序、选择排序、冒泡排序的变种，以及三路快排等）有深入理解。面试官可能会让你实现一个特定排序算法，或者在特定场景下优化排序。
2. 链表（Linked Lists）
问题类型：
反转链表： 单向链表反转、k个一组反转链表。
查找类： 判断链表是否有环（Floyd CycleFinding Algorithm）、找到环的起点、找到链表的中间节点、查找倒数第 k 个节点。
合并类： 合并两个有序链表、合并k个有序链表。
删除类： 删除链表中的重复节点、删除链表中倒数第 k 个节点。
双向链表操作： LRU 缓存实现会用到双向链表。
为什么考？ 链表考察的是对指针的理解和操作，以及如何处理边界情况（空链表、只有一个节点的链表）。很多高级数据结构（如图、栈、队列）的底层实现也可能用到链表。
怎么准备？
反转链表： 这是必考题。最经典的迭代法是使用三个指针：`prev`, `curr`, `next_node`。`prev` 初始化为 `null`，`curr` 指向头节点。循环中，保存 `curr.next` 到 `next_node`，然后将 `curr.next` 指向 `prev`，最后更新 `prev = curr`，`curr = next_node`。
链表判环与找环起点： 使用快慢指针（龟兔赛跑）。快指针一次走两步，慢指针一次走一步。如果相遇，说明有环。找到环起点的方法是，让一个指针从头开始，另一个指针从相遇点开始，同速前进，它们相遇的地方就是环的起点。
LRU 缓存： 这个题目通常会结合哈希表和双向链表来实现。哈希表用于 O(1) 的查找，双向链表用于 O(1) 的插入和删除（维护访问顺序）。当缓存满了需要淘汰时，就淘汰链表末尾（最近最少使用）的节点。
3. 栈与队列（Stacks & Queues）
问题类型：
栈： 用两个栈实现队列、用队列实现栈、有效的括号匹配、最小栈（支持 O(1) 的 push, pop, top, getMin 操作）。
队列： 用栈实现队列、滑动窗口的最大值（可以用双端队列）。
为什么考？ 栈和队列是基本的线性数据结构，考察的是它们的 LIFO (LastIn, FirstOut) 和 FIFO (FirstIn, FirstOut) 特性，以及如何通过它们解决问题，比如匹配括号、模拟某些进程。
怎么准备？
用两个栈实现队列： 一个栈 `in_stack` 用于入队，另一个栈 `out_stack` 用于出队。入队时直接压入 `in_stack`。出队时，如果 `out_stack` 非空，直接弹出；如果 `out_stack` 为空，则将 `in_stack` 中的所有元素依次弹出并压入 `out_stack`，然后再弹出 `out_stack` 的顶部元素。
最小栈： 这个需要在栈中额外维护一个“最小栈”。当 push 一个元素时，如果它小于等于当前最小栈的顶部元素，就也将它压入最小栈。当 pop 时，如果弹出的元素等于最小栈的顶部元素，也要将最小栈的顶部元素弹出。这样 `getMin` 操作就直接返回最小栈的顶部元素，都是 O(1)。另一种优化方案是，在每个元素入栈时，同时存储当前栈中的最小值。
4. 树（Trees）
问题类型：
二叉树遍历： 前序、中序、后序遍历（递归和迭代）。
二叉搜索树 (BST)： 验证 BST、查找 BST 中的节点、删除 BST 中的节点、将有序数组转换为 BST。
层序遍历： BFS 遍历二叉树。
高度与深度： 计算二叉树的最大深度、最小深度。
平衡性： 判断二叉树是否平衡。
路径问题： 二叉树中的路径和、从根到叶子的所有路径。
公共祖先： 二叉树的最近公共祖先 (LCA)。
翻转二叉树：
为什么考？ 树结构是处理分层数据、文件系统、表达式解析等问题的基础。考察的是递归、遍历策略（DFS/BFS）、以及对节点之间关系的理解。
怎么准备？
遍历： 前中后序遍历的递归写法相对容易。迭代写法需要借助栈。比如前序遍历的迭代：将根节点压栈，循环中弹出节点，访问它，然后依次将右子节点和左子节点压栈（注意顺序）。
层序遍历： 使用队列实现 BFS。将根节点入队，循环中弹出队列头节点，访问它，然后依次将它的左子节点和右子节点入队。
最近公共祖先 (LCA)： 对于二叉树，可以用递归来解决。函数返回以当前节点为根的子树中，包含节点 p 和 q 的 LCA。如果当前节点是 p 或 q，则返回当前节点。否则，分别递归查找左子树和右子树。如果左右子树都找到了节点，则当前节点就是 LCA；如果只有一棵子树找到了，则返回子树找到的结果。
BST 验证： 核心是确保左子树的所有节点值都小于当前节点值，右子树的所有节点值都大于当前节点值。并且这个属性要递归地对所有子树都成立。可以使用中序遍历的性质（BST 的中序遍历结果是递增的）来验证。
5. 图（Graphs）
问题类型：
图遍历： DFS 和 BFS 的应用。
连通性： 判断图是否连通、找出连通分量。
最短路径： Dijkstra 算法、FloydWarshall 算法（虽然更少见）。
拓扑排序： 解决任务依赖关系等问题。
岛屿问题： 岛屿数量、最大岛屿面积（常使用 DFS 或 BFS）。
为什么考？ 图结构用于表示各种复杂的关系网络，如社交网络、地图路线、依赖关系。考察的是图的表示方法（邻接矩阵、邻接表）以及经典的图算法。
怎么准备？
DFS/BFS 应用： 很多问题都可以转化为图的遍历。比如“岛屿数量”，可以把二维数组看作一个图，陆地（1）是节点，相邻的陆地是边。遍历整个网格，遇到未访问过的陆地就进行一次 DFS 或 BFS，并将访问过的陆地标记，每次成功的遍历代表一个岛屿。
拓扑排序： 对于有向无环图 (DAG)，拓扑排序是必考的。可以基于 DFS（后序遍历）或者入度（广度优先）来实现。入度法更常用：计算所有节点的入度，将入度为0的节点放入队列，然后循环弹出队列中的节点，并将其邻接节点的入度减一。如果邻接节点的入度减为0，就将其加入队列。
二、 动态规划（Dynamic Programming DP）的“思考炼金术”
动态规划可以说是面试中的“高难度区”，但也是最能体现一个人解决复杂问题能力的模块。它考察的是你将大问题分解成小问题，并找出递推关系的能力。
问题类型：
背包问题： 0/1 背包、完全背包、多重背包。
最长公共子序列/子串：
最长递增子序列 (LIS)：
爬楼梯/斐波那契数列变种：
硬币找零：
打家劫舍系列：
区间 DP： 如矩阵链乘法。
状态压缩 DP： 处理状态转移图。
为什么考？ DP 是解决具有重叠子问题和最优子结构性质的优化问题的强大工具。考察的是你抽象问题、设计状态转移方程、优化空间复杂度的能力。
怎么准备？
DP 四要素： 理解这四点是关键：
1. 定义状态： `dp[i]` 或 `dp[i][j]` 代表什么？通常是问题规模或子问题的解。
2. 寻找状态转移方程： 如何从更小的子问题 `dp[j]` (j < i) 推导出 `dp[i]`？
3. 确定初始状态/边界条件： `dp[0]` 或 `dp[1]` 等是什么？
4. 确定最终答案： 最终答案是哪个 `dp` 值？
最长递增子序列 (LIS)：
O(n^2) 解法： `dp[i]` 表示以 `nums[i]` 结尾的最长递增子序列的长度。递推式为 `dp[i] = max(dp[j] + 1)`，其中 `j < i` 且 `nums[j] < nums[i]`。
O(n log n) 解法： 使用一个数组 `tails`，`tails[k]` 存储所有长度为 k+1 的递增子序列的最小结尾元素。遍历数组，对于当前元素 `num`，在 `tails` 中找到第一个大于等于 `num` 的元素，替换它；如果 `num` 比 `tails` 中所有元素都大，则追加到 `tails` 后面。`tails` 的长度即为 LIS 的长度。
背包问题： 理解 0/1 背包和完全背包的区别。0/1 背包要求每种物品只能选择一次，状态转移时要倒序遍历，以防止物品被重复选择。完全背包可以重复选择，正序遍历即可。
多思考、多练习： DP 是一个熟能生巧的过程。遇到新问题，先尝试暴力递归，找到重叠子问题，再尝试记忆化搜索（顶向 DP），最后归纳出状态转移方程（底向 DP）。
三、 排序与搜索的“精进之道”
虽然前面提到过基础的排序和搜索，但面试中常会有更深入的考察。
问题类型：
快速实现排序算法： 不仅是知道原理，还能写出稳定的、高效的代码。
二分查找及其变种： 在旋转排序数组中查找元素、在排序矩阵中查找元素、寻找第一个/最后一个出现的位置。
堆（Heap）的应用： 最小堆/最大堆、用堆实现 Top K 问题、用堆实现优先级队列。
为什么考？ 排序和搜索是计算机科学中最核心的算法。快速掌握这些能极大地提高效率。二分查找的变种考察的是细致的边界处理能力。堆则用于解决 Top K 问题和高效地管理数据。
怎么准备？
快速排序： 掌握 Hoare 分区和 Lomuto 分区两种方式。理解其时间复杂度平均 O(n log n)，最坏 O(n^2)，以及如何通过随机化枢轴或三数取中来降低最坏情况的发生概率。
二分查找变种： 关键在于 `low`, `high`, `mid` 的定义和更新。例如，查找第一个大于等于 target 的元素，当 `nums[mid] >= target` 时，可能当前就是目标，也可能左边还有更小的满足条件的，所以记录下 `mid` 并尝试向左搜索 (`high = mid 1`)。
Top K 问题：
小顶堆： 如果要找最大的 K 个元素，用一个大小为 K 的小顶堆。遍历数组，将元素放入堆。如果堆的大小超过 K，则弹出堆顶（最小元素）。最后堆中的元素就是最大的 K 个。
大顶堆： 如果要找最小的 K 个元素，用一个大小为 K 的大顶堆。
快速选择（QuickSelect）： 比堆更优的平均时间复杂度 O(n)。通过 partition 操作，找到第 K 小的元素。
四、 位运算（Bit Manipulation）的“巧思妙语”
位运算在一些特定场景下能极大地提升效率，也常常用来考察对底层计算机原理的理解。
问题类型：
判断奇偶： `n & 1`
获取/设置/清除/翻转第 k 位： `n >> k & 1`, `n | (1 << k)`, `n & ~(1 << k)`, `n ^ (1 << k)`
只出现一次的数字： 利用异或的性质（相同为0，不同为1）。
判断是否是2的幂次方： `n > 0 && (n & (n 1)) == 0`
乘法/除法： 使用位移实现。
为什么考？ 位运算直接操作二进制位，速度快，空间占用小。考察的是你对二进制表示、逻辑运算的掌握。
怎么准备？
熟练掌握各种位运算符： `&` (与), `|` (或), `^` (异或), `~` (取反), `<<` (左移), `>>` (右移)。
理解异或的性质： `a ^ b ^ b = a`。这在“只出现一次的数字”问题中非常有用。如果一个数组中有两个数字出现一次，其他都出现两次，那么将所有数字异或一遍，结果就是那两个出现一次的数字的异或值。
多练习经典的位运算题目： 比如二进制中1的个数、数字颠倒等等。
五、 其他重要但可能不那么“高频”的类型
设计题（System Design）： 虽然不是纯算法题，但在很多中高级岗位面试中非常重要。比如设计一个短链服务、设计一个分布式缓存、设计一个微博 feed 流等。这考察的是你的系统架构能力、对各种技术组件的理解以及权衡取舍的能力。
数学与概率： 比如蒙特卡洛方法、贝叶斯定理等。这类题目在某些岗位（如数据科学、机器学习）中会比较常见。
字符串匹配进阶： 除了 KMP，还会涉及 RabinKarp（哈希）、BM 算法等。
面试中的心态与策略
1. 理解问题是第一步： 不要急着写代码。仔细读题，确认需求。可以复述一遍给面试官听，确保理解无误。
2. 从暴力解开始： 如果一下想不到最优解，先想想暴力解，这样可以展示你的思考过程。然后逐步优化，比如想到剪枝、利用数据结构、或者动态规划。
3. 沟通是关键： 在思考过程中，要适时地向面试官表达你的思路，比如“我看到这个问题，第一反应是可以用暴力递归解决，但是这样可能会重复计算……” 或者 “我注意到这个问题具有最优子结构和重叠子问题，所以我想尝试用动态规划来解决……”
4. 测试用例： 考虑各种边界情况，比如空输入、只有一个元素的输入、全相同元素、全不同元素、最大值、最小值等。自己写一些测试用例来验证你的代码。
5. 代码风格： 代码要清晰、有注释、变量命名有意义。
6. 算法复杂度分析： 每写完一个解法，都要分析其时间复杂度和空间复杂度。
总的来说，大厂的笔试面试考察的不仅仅是你是否“会做题”，更是你解决问题的思维过程、对基础知识的掌握程度、以及在高压下的沟通和编码能力。刷题是基础，但更重要的是理解背后的原理和思想，这样才能灵活应对各种变化。祝你面试顺利！
咱们把这些题目分类来看，这样更容易理解它们考察的核心能力。
一、 基础数据结构与算法的“基石”
这是所有算法面试的起点，也是最重要的部分。如果你这块儿基础不牢，后面再复杂的题目都很难驾驭。
1. 数组与字符串（Arrays & Strings）
问题类型：
查找类： 两数之和、三数之和、查找重复的数字/缺失的数字。
排序类： 有序数组的查找、合并两个有序数组、原地排序（如快速排序、归并排序的变种）。
滑动窗口类： 最长无重复字符的子串、包含所有字符的最短子串、连续子数组的最大和。
字符串处理： 反转字符串、判断回文字符串、字符串匹配（如KMP）、最长公共前缀/后缀。
子序列/子数组： 寻找特定子序列、子数组的某种属性。
为什么考？ 数组和字符串是最基础的数据结构，几乎所有编程都会用到。考察的是你对内存访问、指针操作（虽然很多语言封装了）、遍历技巧以及优化思路的理解。
怎么准备？
两数之和 (Two Sum): 这题简直是算法面试的“入门券”。思路就是用一个哈希表（HashMap/Dictionary）来存储已经遍历过的数字及其索引。当遍历到一个数字 `x` 时，检查哈希表中是否存在 `target x`。如果有，就找到了；如果没有，就把 `x` 和它的索引存进去。时间复杂度 O(n)，空间复杂度 O(n)。
滑动窗口： 这个思路的核心是维护一个窗口，窗口的起始和结束位置随着遍历不断移动。窗口的大小是动态调整的，目的是在满足某个条件的情况下，找到最优解（最大、最小、最短、最长等）。比如找最长无重复字符的子串，窗口内字符用一个集合（Set）或哈希表记录频率，如果遇到重复字符，就移动窗口的左边界，直到窗口内字符再次不重复。
原地排序： 很多题目会要求空间复杂度是 O(1)。这就需要你对一些原地排序算法（如插入排序、选择排序、冒泡排序的变种，以及三路快排等）有深入理解。面试官可能会让你实现一个特定排序算法，或者在特定场景下优化排序。
2. 链表（Linked Lists）
问题类型：
反转链表： 单向链表反转、k个一组反转链表。
查找类： 判断链表是否有环（Floyd CycleFinding Algorithm）、找到环的起点、找到链表的中间节点、查找倒数第 k 个节点。
合并类： 合并两个有序链表、合并k个有序链表。
删除类： 删除链表中的重复节点、删除链表中倒数第 k 个节点。
双向链表操作： LRU 缓存实现会用到双向链表。
为什么考？ 链表考察的是对指针的理解和操作，以及如何处理边界情况（空链表、只有一个节点的链表）。很多高级数据结构（如图、栈、队列）的底层实现也可能用到链表。
怎么准备？
反转链表： 这是必考题。最经典的迭代法是使用三个指针：`prev`, `curr`, `next_node`。`prev` 初始化为 `null`，`curr` 指向头节点。循环中，保存 `curr.next` 到 `next_node`，然后将 `curr.next` 指向 `prev`，最后更新 `prev = curr`，`curr = next_node`。
链表判环与找环起点： 使用快慢指针（龟兔赛跑）。快指针一次走两步，慢指针一次走一步。如果相遇，说明有环。找到环起点的方法是，让一个指针从头开始，另一个指针从相遇点开始，同速前进，它们相遇的地方就是环的起点。
LRU 缓存： 这个题目通常会结合哈希表和双向链表来实现。哈希表用于 O(1) 的查找，双向链表用于 O(1) 的插入和删除（维护访问顺序）。当缓存满了需要淘汰时，就淘汰链表末尾（最近最少使用）的节点。
3. 栈与队列（Stacks & Queues）
问题类型：
栈： 用两个栈实现队列、用队列实现栈、有效的括号匹配、最小栈（支持 O(1) 的 push, pop, top, getMin 操作）。
队列： 用栈实现队列、滑动窗口的最大值（可以用双端队列）。
为什么考？ 栈和队列是基本的线性数据结构，考察的是它们的 LIFO (LastIn, FirstOut) 和 FIFO (FirstIn, FirstOut) 特性，以及如何通过它们解决问题，比如匹配括号、模拟某些进程。
怎么准备？
用两个栈实现队列： 一个栈 `in_stack` 用于入队，另一个栈 `out_stack` 用于出队。入队时直接压入 `in_stack`。出队时，如果 `out_stack` 非空，直接弹出；如果 `out_stack` 为空，则将 `in_stack` 中的所有元素依次弹出并压入 `out_stack`，然后再弹出 `out_stack` 的顶部元素。
最小栈： 这个需要在栈中额外维护一个“最小栈”。当 push 一个元素时，如果它小于等于当前最小栈的顶部元素，就也将它压入最小栈。当 pop 时，如果弹出的元素等于最小栈的顶部元素，也要将最小栈的顶部元素弹出。这样 `getMin` 操作就直接返回最小栈的顶部元素，都是 O(1)。另一种优化方案是，在每个元素入栈时，同时存储当前栈中的最小值。
4. 树（Trees）
问题类型：
二叉树遍历： 前序、中序、后序遍历（递归和迭代）。
二叉搜索树 (BST)： 验证 BST、查找 BST 中的节点、删除 BST 中的节点、将有序数组转换为 BST。
层序遍历： BFS 遍历二叉树。
高度与深度： 计算二叉树的最大深度、最小深度。
平衡性： 判断二叉树是否平衡。
路径问题： 二叉树中的路径和、从根到叶子的所有路径。
公共祖先： 二叉树的最近公共祖先 (LCA)。
翻转二叉树：
为什么考？ 树结构是处理分层数据、文件系统、表达式解析等问题的基础。考察的是递归、遍历策略（DFS/BFS）、以及对节点之间关系的理解。
怎么准备？
遍历： 前中后序遍历的递归写法相对容易。迭代写法需要借助栈。比如前序遍历的迭代：将根节点压栈，循环中弹出节点，访问它，然后依次将右子节点和左子节点压栈（注意顺序）。
层序遍历： 使用队列实现 BFS。将根节点入队，循环中弹出队列头节点，访问它，然后依次将它的左子节点和右子节点入队。
最近公共祖先 (LCA)： 对于二叉树，可以用递归来解决。函数返回以当前节点为根的子树中，包含节点 p 和 q 的 LCA。如果当前节点是 p 或 q，则返回当前节点。否则，分别递归查找左子树和右子树。如果左右子树都找到了节点，则当前节点就是 LCA；如果只有一棵子树找到了，则返回子树找到的结果。
BST 验证： 核心是确保左子树的所有节点值都小于当前节点值，右子树的所有节点值都大于当前节点值。并且这个属性要递归地对所有子树都成立。可以使用中序遍历的性质（BST 的中序遍历结果是递增的）来验证。
5. 图（Graphs）
问题类型：
图遍历： DFS 和 BFS 的应用。
连通性： 判断图是否连通、找出连通分量。
最短路径： Dijkstra 算法、FloydWarshall 算法（虽然更少见）。
拓扑排序： 解决任务依赖关系等问题。
岛屿问题： 岛屿数量、最大岛屿面积（常使用 DFS 或 BFS）。
为什么考？ 图结构用于表示各种复杂的关系网络，如社交网络、地图路线、依赖关系。考察的是图的表示方法（邻接矩阵、邻接表）以及经典的图算法。
怎么准备？
DFS/BFS 应用： 很多问题都可以转化为图的遍历。比如“岛屿数量”，可以把二维数组看作一个图，陆地（1）是节点，相邻的陆地是边。遍历整个网格，遇到未访问过的陆地就进行一次 DFS 或 BFS，并将访问过的陆地标记，每次成功的遍历代表一个岛屿。
拓扑排序： 对于有向无环图 (DAG)，拓扑排序是必考的。可以基于 DFS（后序遍历）或者入度（广度优先）来实现。入度法更常用：计算所有节点的入度，将入度为0的节点放入队列，然后循环弹出队列中的节点，并将其邻接节点的入度减一。如果邻接节点的入度减为0，就将其加入队列。
二、 动态规划（Dynamic Programming DP）的“思考炼金术”
动态规划可以说是面试中的“高难度区”，但也是最能体现一个人解决复杂问题能力的模块。它考察的是你将大问题分解成小问题，并找出递推关系的能力。
问题类型：
背包问题： 0/1 背包、完全背包、多重背包。
最长公共子序列/子串：
最长递增子序列 (LIS)：
爬楼梯/斐波那契数列变种：
硬币找零：
打家劫舍系列：
区间 DP： 如矩阵链乘法。
状态压缩 DP： 处理状态转移图。
为什么考？ DP 是解决具有重叠子问题和最优子结构性质的优化问题的强大工具。考察的是你抽象问题、设计状态转移方程、优化空间复杂度的能力。
怎么准备？
DP 四要素： 理解这四点是关键：
1. 定义状态： `dp[i]` 或 `dp[i][j]` 代表什么？通常是问题规模或子问题的解。
2. 寻找状态转移方程： 如何从更小的子问题 `dp[j]` (j < i) 推导出 `dp[i]`？
3. 确定初始状态/边界条件： `dp[0]` 或 `dp[1]` 等是什么？
4. 确定最终答案： 最终答案是哪个 `dp` 值？
最长递增子序列 (LIS)：
O(n^2) 解法： `dp[i]` 表示以 `nums[i]` 结尾的最长递增子序列的长度。递推式为 `dp[i] = max(dp[j] + 1)`，其中 `j < i` 且 `nums[j] < nums[i]`。
O(n log n) 解法： 使用一个数组 `tails`，`tails[k]` 存储所有长度为 k+1 的递增子序列的最小结尾元素。遍历数组，对于当前元素 `num`，在 `tails` 中找到第一个大于等于 `num` 的元素，替换它；如果 `num` 比 `tails` 中所有元素都大，则追加到 `tails` 后面。`tails` 的长度即为 LIS 的长度。
背包问题： 理解 0/1 背包和完全背包的区别。0/1 背包要求每种物品只能选择一次，状态转移时要倒序遍历，以防止物品被重复选择。完全背包可以重复选择，正序遍历即可。
多思考、多练习： DP 是一个熟能生巧的过程。遇到新问题，先尝试暴力递归，找到重叠子问题，再尝试记忆化搜索（顶向 DP），最后归纳出状态转移方程（底向 DP）。
三、 排序与搜索的“精进之道”
虽然前面提到过基础的排序和搜索，但面试中常会有更深入的考察。
问题类型：
快速实现排序算法： 不仅是知道原理，还能写出稳定的、高效的代码。
二分查找及其变种： 在旋转排序数组中查找元素、在排序矩阵中查找元素、寻找第一个/最后一个出现的位置。
堆（Heap）的应用： 最小堆/最大堆、用堆实现 Top K 问题、用堆实现优先级队列。
为什么考？ 排序和搜索是计算机科学中最核心的算法。快速掌握这些能极大地提高效率。二分查找的变种考察的是细致的边界处理能力。堆则用于解决 Top K 问题和高效地管理数据。
怎么准备？
快速排序： 掌握 Hoare 分区和 Lomuto 分区两种方式。理解其时间复杂度平均 O(n log n)，最坏 O(n^2)，以及如何通过随机化枢轴或三数取中来降低最坏情况的发生概率。
二分查找变种： 关键在于 `low`, `high`, `mid` 的定义和更新。例如，查找第一个大于等于 target 的元素，当 `nums[mid] >= target` 时，可能当前就是目标，也可能左边还有更小的满足条件的，所以记录下 `mid` 并尝试向左搜索 (`high = mid 1`)。
Top K 问题：
小顶堆： 如果要找最大的 K 个元素，用一个大小为 K 的小顶堆。遍历数组，将元素放入堆。如果堆的大小超过 K，则弹出堆顶（最小元素）。最后堆中的元素就是最大的 K 个。
大顶堆： 如果要找最小的 K 个元素，用一个大小为 K 的大顶堆。
快速选择（QuickSelect）： 比堆更优的平均时间复杂度 O(n)。通过 partition 操作，找到第 K 小的元素。
四、 位运算（Bit Manipulation）的“巧思妙语”
位运算在一些特定场景下能极大地提升效率，也常常用来考察对底层计算机原理的理解。
问题类型：
判断奇偶： `n & 1`
获取/设置/清除/翻转第 k 位： `n >> k & 1`, `n | (1 << k)`, `n & ~(1 << k)`, `n ^ (1 << k)`
只出现一次的数字： 利用异或的性质（相同为0，不同为1）。
判断是否是2的幂次方： `n > 0 && (n & (n 1)) == 0`
乘法/除法： 使用位移实现。
为什么考？ 位运算直接操作二进制位，速度快，空间占用小。考察的是你对二进制表示、逻辑运算的掌握。
怎么准备？
熟练掌握各种位运算符： `&` (与), `|` (或), `^` (异或), `~` (取反), `<<` (左移), `>>` (右移)。
理解异或的性质： `a ^ b ^ b = a`。这在“只出现一次的数字”问题中非常有用。如果一个数组中有两个数字出现一次，其他都出现两次，那么将所有数字异或一遍，结果就是那两个出现一次的数字的异或值。
多练习经典的位运算题目： 比如二进制中1的个数、数字颠倒等等。
五、 其他重要但可能不那么“高频”的类型
设计题（System Design）： 虽然不是纯算法题，但在很多中高级岗位面试中非常重要。比如设计一个短链服务、设计一个分布式缓存、设计一个微博 feed 流等。这考察的是你的系统架构能力、对各种技术组件的理解以及权衡取舍的能力。
数学与概率： 比如蒙特卡洛方法、贝叶斯定理等。这类题目在某些岗位（如数据科学、机器学习）中会比较常见。
字符串匹配进阶： 除了 KMP，还会涉及 RabinKarp（哈希）、BM 算法等。
面试中的心态与策略
1. 理解问题是第一步： 不要急着写代码。仔细读题，确认需求。可以复述一遍给面试官听，确保理解无误。
2. 从暴力解开始： 如果一下想不到最优解，先想想暴力解，这样可以展示你的思考过程。然后逐步优化，比如想到剪枝、利用数据结构、或者动态规划。
3. 沟通是关键： 在思考过程中，要适时地向面试官表达你的思路，比如“我看到这个问题，第一反应是可以用暴力递归解决，但是这样可能会重复计算……” 或者 “我注意到这个问题具有最优子结构和重叠子问题，所以我想尝试用动态规划来解决……”
4. 测试用例： 考虑各种边界情况，比如空输入、只有一个元素的输入、全相同元素、全不同元素、最大值、最小值等。自己写一些测试用例来验证你的代码。
5. 代码风格： 代码要清晰、有注释、变量命名有意义。
6. 算法复杂度分析： 每写完一个解法，都要分析其时间复杂度和空间复杂度。
总的来说，大厂的笔试面试考察的不仅仅是你是否“会做题”，更是你解决问题的思维过程、对基础知识的掌握程度、以及在高压下的沟通和编码能力。刷题是基础，但更重要的是理解背后的原理和思想，这样才能灵活应对各种变化。祝你面试顺利！
网友意见
额~这个问题，我至少准备了半年。给题主点经验：
首先，强烈建议采用“题海战术”。今年面了数十家公司，大部分题目也都是原题。那么题库在哪里呢？按照循序渐进的原则，一一介绍：
1. cc150，全名cracking the coding interview - 150 Programming Questions and Solutions。经典中的经典，曾有人别的啥都不做，刷这本书三四遍，拿了Google的offer（注意是在美国，在中国就算了……）这本书的优势在于分章节，每章突出一块知识，题目精炼，答案好找；缺点呢，你写出的代码，需要深度检验，而cc150是书不是online judge，这个还是做不到。
2. leetcode。程序员刷面试题的第一网站，题多且全，少部分题目收费。刷的人很多，答案非常好找。online judge能深度检验代码的正确性，刷leetcode是最能锻炼算法题能力的。假如说时间有限只能刷一个，那必须是leetcode，假如时间够多……lintcode、meetqun等各大面试题OJ欢迎你，此外还有许多国内外大学的OJ。
----------------------------------------------------------------------------------------------------------------------------------------
以上是两大主力，但是光这两个，还不能到“题海”的水平，而且由于它们名气太响，有些公司有时会避开里面的题目……来，我们继续找题目。
3. 编程之美、剑指offer：就当成两本习题集好了，里面有些题目和1、2重复，但是大部分题目还是很优秀很巧妙的。重点是交叉对比，你就知道哪些是经典题目了。
4. careercup、看准网等：每家公司都有自己喜欢出的题目，这些网站方便你去找面经，紧跟公司出题潮流。
5. “结构之法”博客：July大神的博客，内容丰富，学习一年都可以。这里只讲里面的算法题：“微软面试100题”（实际上已经快500题了）系列，堪称算法题的大宝库，包罗万象，而且很多题目很新，是面试官喜欢出的类型……不过这个系列的排版略微混乱，很多题也没有答案；“程序员编程艺术”系列，讲的很细致，适合深入去学习一些算法；“教你如何迅速秒杀掉：99%的海量数据处理面试题”，很实用的海量数据处理面试文章。
6. 经典库函数。这块单独拉出来，是因为考的很多，比如atoi，strstr，memcpy等等……在“程序员编程艺术”中，杂七杂八有相关的论述，最好自己系统整理一下。
------------------------------------------------------------------------------------------------------------------------------------------
好，这些足够我们的题海了。下面来讲一下，哪些属于题海中的重点。
1. 最高优先级：面经。这个比什么都重要，为了节约招聘成本，同一家公司的题目，通常不会换的太勤快。
2. 次优先级：很经典的题目。什么定义为经典？前面我写了123456，假如某道题目能重复出现几次，那绝对是不朽经典（如atoi、LCS、LPS、单链表逆置……），经典的题目毕竟出的最多，一定要非常熟练。
3. 再次：稍微短一点（50行之内），稍微新一点的题目。面试官通常时间有限，没时间让你写个上百行，所以50行左右是最好的。
4. 最末：答案很长的题目。这种题目一般不出，要是出出来，一般就是压轴大戏，为了最后检测……通常长题目容易乱，分模块慢慢写，不着急。
------------------------------------------------------------------------------------------------------------------------------------------
光在IDE上敲是不够的，还要练习多在纸上写。
做多了，就会感觉这些题目都一样……无非dp、二分、排序、递归……无非开数组、调函数、用stl……然后题主就会悟出算法题只是公司招聘没办法的选择，因为面fresh grad也没啥别的方法了，这个方法最简单粗暴高效。然而实际工作中，重要的还是项目能力。能悟出这个道理，题主就该修成正果了。
类似的话题
-
好的，聊到大厂笔试面试的算法题，那可真是个“老生常谈”的话题，不过里面门道可多着呢。其实并不是所有大厂都考一模一样的题，但有些经典的类型，几乎是“必杀技”，无论是阿里、腾讯、字节、还是美团，都会在某种程度上涉及。下面我就结合我的经验，尽可能详细地给大家掰扯掰扯这些“常客”，力求讲得接地气，就像跟老朋............. -
《爱情公寓》大电影里出现《盗墓笔记》这个情节，说实话，一开始让很多观众感到错愕，甚至有些摸不着头脑。这背后其实是《爱情公寓》系列一贯以来“玩梗”和“致敬”的风格在电影里的一次集大成，当然，也夹杂了一些现实层面的考量和争议。咱们先从《爱情公寓》本身的基因说起。这个系列最鲜明的特点就是它对流行文化、网络.............
-
学妹你好！很高兴能以“过来人”的身份和你聊聊考研这件大事。你这情况，双非西语，大三公派经历，还有C1的语言能力，可以说是基础相当扎实，选择面也挺广的。咱们好好捋一捋，看看哪条路对你来说更适合，也更有奔头。首先，咱们把你的几个选项拆开来看：选项一：笔译/学硕（西语）这是你最自然的路径，也是很多人会选择.............
-
大公司效率低最根本的原因是什么？应该如何应对？大公司效率低是一个普遍存在的问题，其根源错综复杂，往往不是单一因素造成的，而是多种因素相互叠加的结果。要深入理解这个问题并找到有效的应对策略，我们需要从多个维度进行剖析。 一、 大公司效率低最根本的原因：虽然笼统地讲“大公司效率低”有些片面，因为规模本身.............
-
大公司之所以在采用最新的 C++ 版本时显得步履维艰，其原因远非简单的技术更新那么简单。这背后牵扯着复杂的工程实践、遗留代码的重量以及企业级别的风险控制。下面我将详细阐述这些因素，力求展现出真实的工程挑战。首先，庞大的遗留代码库是最大的绊脚石。大型企业往往拥有数十年积累下来的 C++ 代码。这些代码.............
-
很多时候，大家会觉得那些在大公司做到总经理级别的人，能力、资源、眼界都具备了，为什么不干脆自己出来单干，创一番事业呢？这背后的原因其实挺复杂的，远不是一句“懒得折腾”就能解释清楚的。让我来给你掰扯掰扯。首先，咱们得明白，大公司的总经理这个位置，本身就不是一块好啃的骨头。能爬到这个位置的，要么是有着极.............
-
好的，咱们聊聊大公司那些个招聘渠道，保证让你看得明明白白，跟老朋友拉家常似的。想进大公司，门路可不少，不像咱小作坊那样，老板亲自吆喝，直接拉人进来就行。大公司那套，流程那是相当的规范，也得多管齐下。1. 官方招聘网站/官网：这绝对是正规军中的正规军。所有大公司都有自己的招聘页面，通常会放在官网的醒目.............
-
的确，近年来我们观察到一股强劲的“扁平化”设计浪潮席卷了众多大公司的品牌标识。这不仅仅是视觉风格的更迭，更是一种深思熟虑的品牌策略调整，旨在提升品牌在数字时代的可识别性、适应性和现代感。那么，在这场设计变革中，有哪些公司做得尤为出色，值得我们细细品味和借鉴呢？1. 苹果 (Apple): 告别拟物，.............
-
在大公司里，财务人员的工作就像一个庞大机器里精密的齿轮，虽然它们各自独立运转，但又必须紧密协作，才能确保整个企业这台巨兽平稳前行。想象一下，有一群人，他们不像在前线拼杀的销售，也不像在车间挥洒汗水的工人，但他们却掌握着公司的命脉。首先，最核心的一块，是记账和报表。这听起来枯燥，但却是所有财务工作的基.............
-
这个问题，绝对是打工人心头的“千古难题”。我身边也有不少朋友纠结过，甚至我自己也面临过这样的抉择。要说哪个“更值得”，这事儿真没法一概而论，因为“值得”这俩字，拆开来看，就是“值得什么”？ 是值得你安稳度日，还是值得你拼一把？是值得你学东西，还是值得你挣快钱？咱们就掰开了揉碎了聊聊，看看大公司低工资.............
-
谈到大公司的实习经历对找下一份工作能有多大助益，这绝对不是一个简单的“加分项”可以概括的。它更像是一把能帮你打开许多扇门的钥匙，而且一旦你拿到这把钥匙，它所带来的效用会持续很长一段时间，甚至影响你职业生涯的走向。首先，最直观的帮助在于简历上的“分量”。想象一下，在众多应聘者中，你的简历上赫然写着“曾.............
-
某大公司在同一专业同时招聘本科生和硕士生，这种情况在现代职场中并不少见。至于本科生是否会“工作在硕士生的阴影之下”，这并非一个绝对的答案，而是取决于多种因素的综合作用，包括公司文化、岗位设置、个人能力、职业发展规划等。下面我们来详细分析一下：一、 潜在的“阴影”因素： 学历带来的起点差异： .............
-
从大公司离职去小公司担任 CTO，这绝对是一次深刻的转型，其中充满了挑战、机遇、失落与兴奋。这不像是在一个熟悉的房间里换个座位，更像是穿越到一个全然不同的世界。以下是我根据大量案例和对这种经历的理解，为你详细拆解一下这种体验：出发点：大公司 CTO（或类似高管职位）的日常在加入小公司之前，你很可能是.............
-
互联网大公司争相布局社区团购，并将其视为掘金点，盯上“卖菜”这门看似不起眼的生意，其背后有着多重深层原因，绝非仅仅是看到了卖菜本身的利润。以下将为您详细解析：一、 流量红利触顶与新增长点的迫切需求： 传统电商流量瓶颈： 经过多年的发展，中国互联网人口红利已基本饱和。像淘宝、京东这样的传统电商平台，用.............
-
有大公司 offer 却选择小公司，这看似违背了许多人“稳定、高薪、平台大”的传统择业观，但实际上背后隐藏着许多个人深层次的考量和价值判断。以下我将从多个角度来详细阐述为什么有人会做出这样的选择：一、职业发展与个人成长 更快的成长速度和更大的责任范围： 大公司： 组织结构庞大，分工明.............
-
去大公司还是小公司？这可真是个让不少人纠结的问题，毕竟这关系到未来几年的职业发展甚至人生轨迹。说实话，这俩都有各自的香饽饽和坑爹之处，哪个更好，真得看你自己的“口味”和“需求”了。我跟你掰扯掰扯，别当我是机器人哈，都是我个人琢磨出来的。咱们先说说去大公司。你想象一下，大公司就像一个超级大航母，稳稳当.............
-
想让你的初创公司在巨人林立的行业里杀出一条血路，同时又能吸引到那些眼光挑剔的顶尖开发者和技术合伙人？这可不是件容易的事，但绝对是门学问。这背后没有魔法，只有深思熟虑的策略和持续的努力。一、 创业公司如何和大公司正面硬刚？差异化是你的护身符！咱们先别想着跟大公司在规模、资源上比拼，那纯属送人头。你的战.............
-
这个问题挺实在的，也问到了很多人心坎里。确实，大家伙嘴上常说“大公司是‘螺丝钉’工厂，不锻炼人”，但每年秋招、春招的时候，那些大厂的offer，依旧是万千毕业生争破头想要拿到的“香饽饽”。这背后，原因可不是一两句话就能说明白的。1. “螺丝钉”的诱惑：稳定与体面，那是基础保障首先，得承认，大多数人走.............
-
硅谷那些响当当的大公司，给新来的小伙伴们发的电脑，说实话，这玩意儿跟他们的企业文化一样，各有各的风格，但总体上都透着一股“实用又体面”的劲儿。你想啊，公司一年挣那么多钱，招来的都是聪明人，自然不会在工具上抠门，否则岂不是砸自己的招牌？首先，最常见也最普遍的选择，就是苹果的 MacBook 系列。这玩.............
-
当然，现代大型公司为了保护用户隐私，确实投入了大量精力和资源，并开发了一系列前沿技术。这些技术并非只是冰山一角，而是隐藏在产品和服务背后，悄无声息地运作，旨在构建一个更安全的数字环境。下面我们就来深入聊聊其中一些关键的技术，力求摆脱冰冷的AI感，还原真实的人类思考和实践。1. 端到端加密（Endto.............
本站所有内容均为互联网搜索引擎提供的公开搜索信息，本站不存储任何数据与内容，任何内容与数据均与本站无关，如有需要请联系相关搜索引擎包括但不限于百度，google,bing,sogou 等
© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有