高频面试题

LeetCode 224 https://leetcode.cn/problems/basic-calculator/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 由于字符串除了数字与括号外，只有加号和减号两种运算符。因此，如果展开表达式中所有的括号，则得到的新表达式中，数字本身不会发生变化，只是每个数字前面的符号会发生变化。 因此，我们考虑使用一个取值为 {−1,+1} 的整数 sign 代表「当前」的符号。根据括号表达式的性质，它的取值： 与字符串中当前位置的运算符有关； 如果当前位置处于一系列括号之内，则也与这些括号前面的运算符有关：每当遇到一个以 − 号开头的括号，则意味着此后的符号都要被「翻转」。 考虑到第二点，我们需要维护一个栈 ops，其中栈顶元素记录了当前位置所处的每个括号所「共同形成」的符号。例如，对于字符串 1+2+(3-(4+5))： 扫描到 1+2 时，由于当前位置没有被任何括号所包含，则栈顶元素为初始值 +1； 扫描到 1+2+(3 时，当前位置被一个括号所包含，该括号前面的符号为 + 号，因此栈顶元素依然 +1； 扫描到 1+2+(3-(4 时，当前位置被两个括号所包含，分别对应着 + 号和 − 号，由于 + 号和 − 号合并的结果为 − 号，因此栈顶元素变为 −1。 在得到栈 ops 之后， sign 的取值就能够确定了：如果当前遇到了 + 号，则更新 sign = ops.top()；如果遇到了遇到了 − 号，则更新 sign = −ops.top()。 然后，每当遇到 ( 时，都要将当前的 sign 取值压入栈中；每当遇到 ) 时，都从栈中弹出一个元素。这样，我们能够在扫描字符串的时候，即时地更新 ops 中的元素。 时间复杂度：O(n)，其中 n 为字符串 s 的长度。需要遍历字符串 s 一次，计算表达式的值。 空间复杂度：O(n)，其中 n 为字符串 s 的长度。空间复杂度主要取决于栈的空间，栈中的元素数量不超过 n。 ...

LeetCode 153 https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 二分查找，与最后一个数比大小。如果 mid 比 nums[n - 1] 小，一定是蓝色（是最小值或最小值右边），反之是红色（最小值左边）， 最后 right 就是答案。 时间复杂度：O(logn)，其中 n 为 nums 的长度。 空间复杂度：O(1)，仅用到若干额外变量。 ...

LeetCode 207 https://leetcode.cn/problems/course-schedule/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 三色标记法找环。 对于每个节点 x，都定义三种颜色值： 0：x 尚未被访问到。 1：x 正在被访问，dfs(x) 尚未结束。 2：x 已访问完毕，dfs(x) 已返回。 如果在递归过程中，发现下一个节点在递归栈中（正在访问中），则找到了环。 时间复杂度：O(n+m)，其中 n 是 numCourses，m 是 prerequisites 的长度。每个节点至多递归访问一次，每条边至多遍历一次。 空间复杂度：O(n+m)。存储 g 需要 O(n+m) 的空间。 ...

LeetCode 460 https://leetcode.cn/problems/lfu-cache/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是 LRU 缓存的升级版。本题对于每个使用频率，都需要维护一个双向链表，并通过哈希表把频率和链表关联起来。为了找到最少的使用频率，需要维护一个 min_freq 变量。 在插入时需要插入到链表的头部，而当容量满，需要删除时需要删除的是最少使用频率的书中的尾部结点 dummy->prev。 时间复杂度：所有操作均为 O(1)。 空间复杂度：O(min(p,capacity))，其中 p 为 put 的调用次数。 ...

LeetCode 79 https://leetcode.cn/problems/word-search/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 网格图回溯。为了知道当前匹配到了第几个字母，需要三个参数 dfs(i, j, k)。 定义 dfs(i,j,k) 表示当前在 board[i][j] 这个格子，要匹配 word[k]，返回在这个状态下最终能否匹配成功（搜索成功）。 如果 board[i][j] != word[k]，匹配失败，返回 false。 否则，如果 k == len(word) − 1，匹配成功，返回 true。 否则，枚举 (i, j) 周围的四个相邻格子 (x, y)，如果 (x, y) 没有出界，则递归 dfs(x, y, k + 1)，如果其返回 true，则 dfs(i, j, k) 也返回 true。 如果递归周围的四个相邻格子都没有返回 true，则最后返回 false，表示没有搜到。 递归过程中，为了避免重复访问同一个格子，可以直接修改 board[i][j]，将其置为空（或者 0），返回 false 前再恢复成原来的值（恢复现场）。注意返回 true 的时候就不用恢复现场了，因为已经成功搜到 word 了。 时间复杂度：\(O(mn3^k)\)，其中 m 和 n 分别为 grid 的行数和列数，k 是 word 的长度。除了递归入口，其余递归至多有 3 个分支（因为至少有一个方向是之前走过的），所以每次递归（回溯）的时间复杂度为 \(O(3^k)\)，一共回溯 O(mn) 次，所以时间复杂度为 \(O(mn3^k)\)。 空间复杂度：O(∣Σ∣+k)。其中 ∣Σ∣=52 是字符集合的大小。递归需要 O(k) 的栈空间。部分语言用的数组代替哈希表，可以视作 ∣Σ∣=128。 ...

LeetCode 402 https://leetcode.cn/problems/remove-k-digits/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题需要尽量保证前面的数字最小，这可以使用单调栈来实现。 我们定义一个单调栈，遍历整个数字，当 k > 0 时，对于当前数字，判断是否小于栈顶，否则弹出栈顶元素。这样最后从栈底到栈顶单调不减。 如果最后 k 还是 > 0，那么直接删除最后的 k - m 个元素，因为他们是最大的。 为了生成答案，需要从栈底到栈顶遍历，因此栈使用 vector 来实现。 时间复杂度：O(n)，其中 n 为字符串的长度。 空间复杂度：O(n)。栈存储数字需要线性的空间。 ...

LeetCode 47 https://leetcode.cn/problems/permutations-ii/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是有重复元素的全排列。如何避免得到重复的结果呢？可以把相同的元素排一个顺序，只能从左往右按顺序排。 为方便判断，先把 nums 排序（从小到大或者从大到小都可以）。 如果 nums[i] != nums[i−1]，那么 nums[i] 就是所有等于 nums[i] 的数中的第一个数。我们规定：这种情况可以随意填。 如果 nums[i] == nums[i−1]，继续讨论： 如果 nums[i−1] 没有填入排列，为了避免生成重复的排列，绝对不能填 nums[i]，直接 continue。这会导致后续所有等于 nums[i] 的数全部 continue，因为对于后面的 nums[i] 来说，nums[i] 和前面的数 nums[i−1] 相等，并且 nums[i−1] 没有填入排列。 如果 nums[i−1] 已经填入排列，那么 nums[i] 是剩余元素（子问题）中的第一个等于 nums[i] 的数，可以随意填。 时间复杂度：O(n⋅n!)，其中 n 为 nums 的长度。分析方法同 46 题的题解。 空间复杂度：O(n)。返回值的空间不计入。 ...

LeetCode 468 https://leetcode.cn/problems/validate-ip-address/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 模拟题。 我们首先查找给定的字符串 queryIP 中是否包含符号 ‘.’。如果包含，那么我们需要判断其是否为 IPv4 地址；如果不包含，我们则判断其是否为 IPv6 地址。 对于 IPv4 地址而言，它包含 4 个部分，用 ‘.’ 隔开。因此我们可以存储相邻两个 ‘.’ 出现的位置 last 和 cur（当考虑首个部分时，last=−1；当考虑最后一个部分时，cur=n，其中 n 是字符串的长度），那么子串 queryIP[last+1..cur−1] 就对应着一个部分。我们需要判断： 它的长度是否在 [1,3] 之间（虽然这一步没有显式要求，但提前判断可以防止后续计算值时 32 位整数无法表示的情况）； 它是否只包含数字； 它的值是否在 [0,255] 之间； 它是否不包含前导零。具体地，如果它的值为 0，那么该部分只能包含一个 0，即 (cur−1)−(last+1)+1=1；如果它的值不为 0，那么该部分的第一个数字不能为 0，即 queryIP[last+1] 不为 0。 对于 IPv6 地址而言，它包含 8 个部分，用 ‘:’ 隔开。同样地，我们可以存储相邻两个 ‘:’ 出现的位置 last 和 cur，那么子串 queryIP[last+1..cur−1] 就对应着一个部分。我们需要判断： 它的长度是否在 [1,4] 之间； 它是否只包含数字，或者 a-f，或者 A-F； 除了上述情况以外，如果我们无法找到对应数量的部分，那么给定的字符串也不是一个有效的 IP 地址。 时间复杂度：O(n)，其中 n 是字符串 queryIP 的长度。我们只需要遍历字符串常数次。 空间复杂度：O(1)。 ...

LeetCode 739 https://leetcode.cn/problems/daily-temperatures/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 单调栈经典题目。从左往右遍历，栈中记录还没算出下一个更大元素的那些数的下标。相当于栈是一个 todolist，在循环的过程中，现在还不知道答案是多少，在后面的循环中会算出答案。 时间复杂度：O(n)，其中 n 为 temperatures 的长度。虽然我们写了个二重循环，但站在每个元素的视角看，这个元素在二重循环中最多入栈出栈各一次，因此循环次数之和是 O(n)，所以时间复杂度是 O(n)。 空间复杂度：O(n)。注意这种写法栈中可以有重复元素。 ...

LeetCode 297 https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题可以使用前序遍历或者层序遍历，这里使用层序遍历。 在序列化时需要注意空节点也需要保存。在反序列化时，为了分割字符串，使用了 stringstream。 getline(ss, token, ',') 序列化和反序列化的时空复杂度相同。 时间复杂度：O(n)。 空间复杂度：O(n)。 ...