LeetCode 78 https://leetcode.cn/problems/subsets/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 子集型回溯，选或不选。 时间复杂度：\(O(n2^n)\)，其中 n 为 nums 的长度。每次都是选或不选，递归次数为一个满二叉树的节点个数，那么一共会递归 \(O(2^n)\) 次（等比数列和），再算上加入答案时复制 path 需要 O(n) 的时间，所以时间复杂度为 \(O(n2^n)\)。 空间复杂度：O(n)。返回值的空间不计。 ...
LeetCode 151 https://leetcode.cn/problems/reverse-words-in-a-string/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 先翻转整个字符串，再分别翻转每一个单词。 时间复杂度：O(n)，其中 n 为输入字符串的长度。 空间复杂度：O(n)，用来存储字符串分割之后的结果。 ...
LCR 140 https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 前后指针找链表倒数第 k 个节点。 时间复杂度：O(n)，其中 n 为链表的长度。我们使用快慢指针，只需要一次遍历即可，复杂度为 O(n)。 空间复杂度：O(1)。 ...
LeetCode 105 https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题使用递归从二叉树的前序和中序遍历构造二叉树。首先找到中序遍历中根节点的位置，它左边就是左子树的长度。然后构造左右子树的前序和中序遍历，递归调用，构造二叉树。 时间复杂度：\(O(n^2)\)，其中 n 为 preorder 的长度。最坏情况下二叉树是一条链，我们需要递归 O(n) 次，每次都需要 O(n) 的时间查找 preorder[0] 和复制数组。 空间复杂度：\(O(n^2)\)。 ...
LeetCode 41 https://leetcode.cn/problems/first-missing-positive/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 灵神题解：https://leetcode.cn/problems/first-missing-positive/solutions/3655377/huan-zuo-wei-tong-guo-li-zi-li-jie-suan-qa94e/ 一般地，为了兼容「当前学生是真身，坐在正确的座位上」和「当前学生是影分身，且其真身坐在正确的座位上」两种情况，我们可以把 i=nums[i] 套一层 nums，用 nums[i]=nums[nums[i]] 判断。 无论「当前学生是真身，坐在正确的座位上」还是「当前学生是影分身，且其真身坐在正确的座位上」，上式都是成立的。 如果「当前学生是真身，不坐在正确的座位上」，那么上式左边是当前学生的学号，右边是要交换的学生的学号。 如果「当前学生是影分身，且其真身不坐在正确的座位上」，那么上式左边是当前学生的学号，右边是要交换的学生的学号。虽然是用影分身交换的，但交换后，可以认为真身已经坐在了正确的座位上。 代码实现时，由于 nums 的下标是从 0 开始的，通过学号访问下标，要把学号减一。 时间复杂度：O(n)，其中 n 是 nums 的长度。虽然我们写了个二重循环，但每次交换都会把一个学生换到正确的座位上，所以总交换次数至多为 n，所以内层循环的总循环次数是 O(n) 的，所以时间复杂度是 O(n)。 空间复杂度：O(1)。 ...
LeetCode 76 https://leetcode.cn/problems/minimum-window-substring/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 这是滑动窗口的题目。s 覆盖 t 的意思就是对 t 中的每个字母，s 里的出现次数都不小于 t 里的出现次数。出现次数使用哈希表来计数，在本题可以使用数组来进行优化。 时间复杂度：O(∣Σ∣m+n)，其中 m 为 s 的长度，n 为 t 的长度，∣Σ∣ 为字符集合的大小，本题字符均为英文字母，所以 ∣Σ∣=52。注意 left 只会增加不会减少，left 每增加一次，我们就花费 O(∣Σ∣) 的时间。因为 left 至多增加 m 次，所以二重循环的时间复杂度为 O(∣Σ∣m)，再算上统计 t 字母出现次数的时间 O(n)，总的时间复杂度为 O(∣Σ∣m+n)。 空间复杂度：O(∣Σ∣)。如果创建了大小为 128 的数组，则 ∣Σ∣=128。 ...
LeetCode 43 https://leetcode.cn/problems/multiply-strings/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 高精度乘法，模拟竖式计算。 为了方便处理进位，先用一个倒序的 int 类型数组来存储计算结果，最后再将结果转回字符串。 数组的长度初始化为 m + n，如果最高位为 0，则将长度减一。 时间复杂度：O(mn)。 空间复杂度：O(m+n)。 ...
LeetCode 322 https://leetcode.cn/problems/coin-change/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 完全背包题目。与 0-1 背包的不同是转移方程中右边的 i 变成 i + 1，说明可以重复取同一个元素。 f[i + 1][c] = min(f[i][c], f[i + 1][c - w[i]] + v[i]) 时间复杂度：O(n⋅amount)，其中 n 为 coins 的长度。 空间复杂度：O(n⋅amount)。 ...
LeetCode 70 https://leetcode.cn/problems/climbing-stairs/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 斐波那契数列。f[i] = f[i - 1] + f[i - 2]。 时间复杂度：O(n)。 空间复杂度：O(n)。 ...
LeetCode 32 https://leetcode.cn/problems/longest-valid-parentheses/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是一道一维 DP 的题目。f[i] 表示以 i 结尾的最长有效括号的长度。由于有效括号只会以 ‘)’ 结尾，所以只在当前字符为 ‘)’ 时的状态转移。 当前一个字符为 ‘(’ 时，转移到 f[i] = f[i - 2] + 2。 当第 i - f[i - 1] - 1 个字符为 ‘(’ 时，将原本不连续的两段长度合并，即转移到 f[i] = f[i - 1] + f[i - f[i - 1] - 2] + 2。 时间复杂度： O(n)，其中 n 为字符串的长度。我们只需遍历整个字符串一次，即可将 dp 数组求出来。 空间复杂度： O(n)。我们需要一个大小为 n 的 dp 数组。 ...