Posts

LeetCode 120 https://leetcode.cn/problems/triangle/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ f[i][j] = min(f[i+1][j],f[i+1][j+1]) + triangle[i][j] 时间复杂度：O(n^2)，其中 n 为 triangle 的长度。 空间复杂度：O(n^2)。 ...

LeetCode 678 https://leetcode.cn/problems/valid-parenthesis-string/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 括号匹配的问题可以用栈求解。 如果字符串中没有星号，则只需要一个栈存储左括号，在从左到右遍历字符串的过程中检查括号是否匹配。 在有星号的情况下，需要两个栈分别存储左括号和星号。从左到右遍历字符串，进行如下操作。 如果遇到左括号，则将当前下标存入左括号栈。 如果遇到星号，则将当前下标存入星号栈。 如果遇到右括号，则需要有一个左括号或星号和右括号匹配，由于星号也可以看成右括号或者空字符串，因此当前的右括号应优先和左括号匹配，没有左括号时和星号匹配： 如果左括号栈不为空，则从左括号栈弹出栈顶元素； 如果左括号栈为空且星号栈不为空，则从星号栈弹出栈顶元素； 如果左括号栈和星号栈都为空，则没有字符可以和当前的右括号匹配，返回 false。 遍历结束之后，左括号栈和星号栈可能还有元素。为了将每个左括号匹配，需要将星号看成右括号，且每个左括号必须出现在其匹配的星号之前。当两个栈都不为空时，每次从左括号栈和星号栈分别弹出栈顶元素，对应左括号下标和星号下标，判断是否可以匹配，匹配的条件是左括号下标小于星号下标，如果左括号下标大于星号下标则返回 false。 最终判断左括号栈是否为空。如果左括号栈为空，则左括号全部匹配完毕，剩下的星号都可以看成空字符串，此时 s 是有效的括号字符串，返回 true。如果左括号栈不为空，则还有左括号无法匹配，此时 s 不是有效的括号字符串，返回 false。 时间复杂度：O(n)，其中 n 是字符串 s 的长度。需要遍历字符串一次，遍历过程中每个字符的操作时间都是 O(1)，遍历结束之后对左括号栈和星号栈弹出元素的操作次数不会超过 n。 空间复杂度：O(n)，其中 n 是字符串 s 的长度。空间复杂度主要取决于左括号栈和星号栈，两个栈的元素总数不会超过 n。 ...

LCR 139 https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 双指针。 时间复杂度 O(N) ： N 为数组 actions 长度，双指针 i, j 共同遍历整个数组。 空间复杂度 O(1) ： 双指针 i, j 使用常数大小的额外空间。 ...

LeetCode 287 https://leetcode.cn/problems/find-the-duplicate-number/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题不允许修改数组，因此不能使用原地哈希。使用快慢指针法，同环形链表题目。 时间复杂度：O(n)。「Floyd 判圈算法」时间复杂度为线性的时间复杂度。 空间复杂度：O(1)。我们只需要常数空间存放若干变量。 ...

LeetCode 189 https://leetcode.cn/problems/rotate-array/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 轮转数组只需要三步，反转整个数组，反转前 k 个元素，反转后 n - k 个。 时间复杂度：O(n)，其中 n 是 nums 的长度。 空间复杂度：O(1)。 ...

LeetCode 516 https://leetcode.cn/problems/longest-palindromic-subsequence/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 区间 DP，从大区间转移到小区间。f[i][j] 为 s[i] 到 s[j] 的最长回文子序列。 if (s[i] == s[j]) { f[i][j] = 2 + f[i + 1][j - 1]; } else { f[i][j] = max(f[i + 1][j], f[i][j - 1];) } 时间复杂度：O(n^2)，其中 n 为 s 的长度。动态规划的时间复杂度 = 状态个数 × 单个状态的转移个数。本题中状态个数等于 O(n^2)，而单个状态的转移个数为 O(1)，因此时间复杂度为 O(n^2)。 空间复杂度：O(n^2)。 ...

LeetCode 213 https://leetcode.cn/problems/house-robber-ii/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 分类讨论，考虑是否偷 nums[0]： 如果偷 nums[0]，那么 nums[1] 和 nums[n−1] 不能偷，问题变成从 nums[2] 到 nums[n−2] 的非环形版本，调用 198 题的代码解决； 如果不偷 nums[0]，那么问题变成从 nums[1] 到 nums[n−1] 的非环形版本，同样调用 198 题的代码解决。 这两种方案覆盖了所有情况（毕竟 nums[0] 只有偷与不偷，没有第三种选择），所以取两种方案的最大值，即为答案。 时间复杂度：O(n)。其中 n 为 nums 的长度。 空间复杂度：O(1)。仅用到若干额外变量。为了写起来方便，Python 和 JS 使用了切片（忽略带来的空间），不使用切片的写法请参考其它语言。 ...

LCR 187 https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 动态规划。状态转移方程 f[i] = (f[i - 1] + target) % i。 时间复杂度 O(n) ： 状态转移循环 n − 1 次使用 O(n) 时间，状态转移方程计算使用 O(1) 时间； 空间复杂度 O(1) ： 使用常数大小的额外空间； ...

LeetCode 106 https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 时间复杂度：\(O(n^2)\)，其中 n 为 postorder 的长度。最坏情况下二叉树是一条链，我们需要递归 O(n) 次，每次都需要 O(n) 的时间查找 postorder[n−1] 和复制数组。 空间复杂度：\(O(n^2)\)。 ...

LeetCode 225 https://leetcode.cn/problems/implement-stack-using-queues/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 使用一个队列时，为了满足栈的特性，即最后入栈的元素最先出栈，同样需要满足队列前端的元素是最后入栈的元素。 入栈操作时，首先获得入栈前的元素个数 n，然后将元素入队到队列，再将队列中的前 n 个元素（即除了新入栈的元素之外的全部元素）依次出队并入队到队列，此时队列的前端的元素即为新入栈的元素，且队列的前端和后端分别对应栈顶和栈底。 由于每次入栈操作都确保队列的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除队列的前端元素并返回即可，获得栈顶元素操作只需要获得队列的前端元素并返回即可（不移除元素）。 由于队列用于存储栈内的元素，判断栈是否为空时，只需要判断队列是否为空即可。 时间复杂度：入栈操作 O(n)，其余操作都是 O(1)，其中 n 是栈内的元素个数。 空间复杂度：O(n)，其中 n 是栈内的元素个数。需要使用一个队列存储栈内的元素。 ...