高频面试题

LeetCode 55 https://leetcode.cn/problems/jump-game/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 维护最右可达位置。用 i + nums[i] 更新 mx 最大值。如果当前位置不可达返回 False。 时间复杂度：O(n)，其中 n 是 nums 的长度。 空间复杂度：O(1)。仅用到若干额外变量。 ...

LeetCode 958 https://leetcode.cn/problems/check-completeness-of-a-binary-tree/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 层序遍历二叉树。如果遍历到了一个非空节点之前遍历过空节点，就不是完全二叉树。 时间复杂度：O(N)，其中 N 是树节点个数。 空间复杂度：O(N)。 ...

LeetCode 498 https://leetcode.cn/problems/diagonal-traverse/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 模拟对角线遍历，当到达边界的时候需要改变方向。需要注意的是在判断边界时有顺序要求，例如向上移动时，需要先处理右边界，再处理上边界。这是因为如果当同时到达右边界和上边界时，如果处理上边界，col 就越界了。 时间复杂度：O(m×n)，其中 m 为矩阵行的数量，n 为矩阵列的数量。需要遍历一遍矩阵中的所有元素，需要的时间复杂度为 O(m×n)。 空间复杂度：O(1)。除返回值外不需要额外的空间。 ...

LeetCode 123 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是至少可以完成 k 次交易的股票买卖问题。 数组需要增加一维 k， f[n + 1][k + 2][2]。在买入（或卖出）时将剩余交易次数减一。 初始化 f[0][j][0] = 0，其他元素为 -INF。 时间复杂度：O(n)，其中 n 为 prices 的长度。 空间复杂度：O(1)。 ...

LeetCode 61 https://leetcode.cn/problems/rotate-list/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是旋转链表，可以直接将链表闭合成环，再在指定位置断开。 时间复杂度：O(n)，最坏情况下，我们需要遍历该链表两次。 空间复杂度：O(1)，我们只需要常数的空间存储若干变量。 ...

LCR 125 https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 将一个栈当作输入栈，用于压入 appendTail 传入的数据；另一个栈当作输出栈，用于 deleteHead 操作。 每次 deleteHead 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。 时间复杂度：appendTail 为 O(1)，deleteHead 为均摊 O(1)。对于每个元素，至多入栈和出栈各两次，故均摊复杂度为 O(1)。 空间复杂度：O(n)。其中 n 是操作总数。对于有 n 次 appendTail 操作的情况，队列中会有 n 个元素，故空间复杂度为 O(n)。 ...

LeetCode 912 https://leetcode.cn/problems/sort-an-array/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 归并排序。将整个数组分成前后两个部分，递归调用归并排序，使得两部分分别有序，之后使用一个临时数组，将两个有序数组合并，最后将结果复制回原数组。 时间复杂度：O(nlogn)。由于归并排序每次都将当前待排序的序列折半成两个子序列递归调用，然后再合并两个有序的子序列，而每次合并两个有序的子序列需要 O(n) 的时间复杂度，根据主定理我们可以得出归并排序的时间复杂度为 O(nlogn)。 空间复杂度：O(n)。我们需要额外 O(n) 空间的 tmp 数组，且归并排序递归调用的层数最深为 logn，所以我们还需要额外的 O(logn) 的栈空间，所需的空间复杂度即为 O(n+logn) = O(n)。 ...

LeetCode 11 https://leetcode.cn/problems/container-with-most-water/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 相向双指针。容器的容积是由左右两端较低的一方决定的。如果保留较低的一端，另一端相向移动。假设新的另一端比他要高，那么最低的还是他，宽度变小了，容积也变小了。假设另一端比他还低，那么宽度变小了，高度也变小了，容积还是变小。因此如果要得到更大的容积，就不能保留较低的一端，需要移动他。 时间复杂度：O(n)，其中 n 为 height 的长度。 空间复杂度：O(1)，仅用到若干额外变量。 ...

LeetCode 136 https://leetcode.cn/problems/single-number/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 利用异或运算 a ⊕ a = 0 的性质，我们可以用异或来「消除」所有出现了两次的元素，最后剩下的一定是只出现一次的元素。 初始化 ans = 0 是因为 0 ⊕ a = a，相当于我们从第一个数开始，和其它数异或。 ...

LeetCode 138 https://leetcode.cn/problems/copy-list-with-random-pointer/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 简单的做法是直接用一个哈希表把两个链表中节点的对应关系存起来，在二次遍历的时候设置新链表的 next 和 random。 此外，我们可以把新链表和旧链表混在一起。依次复制每个节点（创建新节点并复制 val 和 next），把新节点直接插到原节点的后面，形成一个交错链表。如此一来，原链表节点的下一个节点，就是其对应的新链表节点了！ 然后遍历这个交错链表，假如节点 1 的 random 指向节点 3，那么就把节点 1′ 的 random 指向节点 3 的下一个节点 3′，这样就完成了对 random 指针的复制。 最后，从交错链表链表中分离出深拷贝后的链表。 时间复杂度：O(n)，其中 n 是链表的长度。 空间复杂度：O(1)。返回值不计入。 ...