LeetCode 912 https://leetcode.cn/problems/sort-an-array/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是手撕堆排序，使用最大堆。在本题中因为不会有新的元素插入，只需要实现自顶向下修复堆的操作即可。建堆时从最后一个非叶子结点开始，依次调用 repair 函数。然后每次将堆顶元素与堆的最后一个元素交换，堆的大小减一，修复堆。最后数组即为升序排列。反之，如果降序排列使用最小堆。 时间复杂度：O(nlogn)。初始化建堆的时间复杂度为 O(n)，建完堆以后需要进行 n−1 次调整，一次调整的时间复杂度为 O(logn)，那么 n−1 次调整即需要 O(nlogn) 的时间复杂度。因此，总时间复杂度为 O(n+nlogn)=O(nlogn)。 空间复杂度：O(1)。只需要常数的空间存放若干变量。 ...

LeetCode 283 https://leetcode.cn/problems/move-zeroes/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 题目要求在不复制数组的情况下原地对数组进行操作。 直接把 nums 当作栈，用一个变量 stackSize 表示栈的大小，初始值为 0。 入栈就是把 nums[stackSize] 置为 nums[i]，同时把 stackSize 加一。 最后把 nums 中的下标从 stackSize 到 n−1 的数都置为 0。 时间复杂度：O(n)，其中 n 是 nums 的长度。 空间复杂度：O(1)。 ...

LeetCode 24 https://leetcode.cn/problems/swap-nodes-in-pairs/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ K 个一组反转链表的简单版本。 时间复杂度：O(n)，其中 n 为链表长度。 空间复杂度：O(1)。仅用到若干额外变量。 ...

LeetCode 226 https://leetcode.cn/problems/invert-binary-tree/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 递归调用 invertTree(root.left)，获取到左子树翻转后的结果 left。 递归调用 invertTree(root.right)，获取到右子树翻转后的结果 right。 交换左右儿子，即更新 root.left 为 right，更新 root.right 为 left。 返回 root。 递归边界：如果 root 是空节点，返回空。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。 ...

LeetCode 83 https://leetcode.cn/problems/remove-duplicates-from-sorted-list/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 判断下个节点，与当前节点相同就删除。 时间复杂度：O(n)，其中 n 为链表的长度。 空间复杂度：O(1)，仅用到若干额外变量。 ...

LeetCode 139 https://leetcode.cn/problems/word-break/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 划分型 DP 一般定义 f[i] 表示长为 i 的前缀 a[:i] 能否划分。 枚举最后一个子数组的左端点 L，从 f[L] 转移到 f[i]，并考虑 a[L:i] 是否满足要求。 这道题首先为了方便判断是否在单词表中，先把 wordDict 转成 unordered_set。另外，本题 wordDict 至多有 1000 个字符串，但最多只有 20 种不同的长度，所以应该枚举长度，而不是枚举 wordDict 中的字符串。 时间复杂度：\(O(mL+nL^2)\)，其中 m 是 wordDict 的长度，L 是 wordDict 中字符串的最长长度，n 是 s 的长度。创建哈希集合需要 O(mL) 的时间。由于每个状态只会计算一次，动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间。本题状态个数等于 O(n)，单个状态的计算时间为 \(O(L^2)\)（注意判断子串是否在哈希集合中需要 O(L) 的时间），所以记忆化搜索的时间复杂度为 \(O(nL^2)\)。 空间复杂度：O(mL+n)。哈希集合需要 O(mL) 的空间。记忆化搜索需要 O(n) 的空间。 ...

LeetCode 209 https://leetcode.cn/problems/minimum-size-subarray-sum/description/ 难度：209 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 满足单调性，可以使用滑动窗口。 时间复杂度：O(n)，其中 n 为 nums 的长度。虽然写了个二重循环，但是内层循环中对 left 加一的总执行次数不会超过 n 次，所以总的时间复杂度为 O(n)。 空间复杂度：O(1)，仅用到若干额外变量。 ...

LeetCode 718 https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 类似最长公共子序列，这题是求连续子数组。定义 f[i+1][j+1] 表示以 nums1[i] 结尾的子数组和以 nums2[j] 结尾的子数组的最长公共子数组的长度。 如果 nums1[i] != nums2[j]，那么 f[i+1][j+1]=0。 如果 nums1[i] == nums2[j]，那么问题变成以 nums1[i−1] 结尾的子数组和以 nums2[j−1] 结尾的子数组的最长公共子数组的长度，即 f[i+1][j+1]=f[i][j]+1。相当于在以 nums1[i−1] 结尾的子数组后面添加 nums1[i]，在以 nums2[j−1] 结尾的子数组后面添加 nums2[j]。 初始值：f[0][j]=f[i][0]=0，空子数组没有公共部分。 答案：所有 f[i][j] 的最大值。 时间复杂度：O(nm)，其中 n 是 nums1 的长度，m 是 nums2 的长度。 空间复杂度：O(nm)。 ...

LeetCode 169 https://leetcode.cn/problems/majority-element/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ Boyer-Moore 投票算法 我们维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0； 我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x： 如果 x 与 candidate 相等，那么计数器 count 的值增加 1； 如果 x 与 candidate 不等，那么计数器 count 的值减少 1。 在遍历完成后，candidate 即为整个数组的众数。 时间复杂度：O(n)。Boyer-Moore 算法只对数组进行了一次遍历。 空间复杂度：O(1)。Boyer-Moore 算法只需要常数级别的额外空间。 ...

LeetCode 227 https://leetcode.cn/problems/basic-calculator-ii/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是包含加减乘除，但没有括号的表达式求值。可以使用一个栈来解决。 使用 op 记录上一个运算符是什么。遍历字符串，如果当前字符是数字，就更新数字，如果是运算符或者已经到了最后一个字符，那么根据上一个运算符来操作。如果是加减，那么直接将当前数字加入栈中。如果是乘除，直接操作栈顶元素。然后将 op 更新为当前字符。 最后只需要将栈中所有元素加起来即可。为了方便遍历，栈使用 vector 实现。 时间复杂度：O(n)，其中 n 为字符串 s 的长度。需要遍历字符串 s 一次，计算表达式的值。 空间复杂度：O(n)，其中 n 为字符串 s 的长度。空间复杂度主要取决于栈的空间，栈的元素个数不超过 n。 ...