LeetCode 134 https://leetcode.cn/problems/gas-station/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 如果 gas 之和小于 cost 之和，那么答案不存在。从示例 1 的计算过程可以发现，我们可以先计算从 0 号加油站出发的油量变化，然后从中找到油量最低时所处的加油站（3 号加油站），即为答案。 时间复杂度：O(n)，其中 n 是 gas 的长度。 空间复杂度：O(1)。 ...
LeetCode 400 https://leetcode.cn/problems/nth-digit/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 已知 x 位数共有 9×10^x−1 个，所有 x 位数的位数之和是 x × 9×10^x−1。使用 d 和 count 分别表示当前遍历到的位数和当前位数下的所有整数的位数之和，初始时 d=1，count=9。每次将 n 减去 d×count，然后将 d 加 1，将 count 乘以 10，直到 n≤d×count，此时的 d 是目标数字所在整数的位数，n 是所有 d 位数中从第一位到目标数字的位数。 为了方便计算目标数字，使用目标数字在所有 d 位数中的下标进行计算，下标从 0 开始计数。令 index=n−1，则 index 即为目标数字在所有 d 位数中的下标，index 的最小可能取值是 0。 时间复杂度：O(log10 n)。用 d 表示第 n 位数字所在整数的位数，循环需要遍历 d 次，由于 d=O(log10 n)，因此时间复杂度是 O(log10 n)。 空间复杂度：O(1)。 ...
LeetCode 679 https://leetcode.cn/problems/24-game/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 无论表达式是什么样的，我们总是可以从中选两个数最先计算。计算后，变成包含三个数字的表达式。同样地，这个表达式也可以从中选两个数最先计算，依此类推。 每次从剩余牌中取两张牌，执行计算，合并成一张新牌。所以每次计算后会减少一张牌，得到一个新的数组 newCards。用 newCards 递归调用 judgePoint24，直到只剩一张牌。判断这张牌的数字是否等于 24。 一共有六种运算方式：加减乘除，其中减和除有两种不同的顺序。注意除法需要保证分母不为 0。有两种方法实现除法：浮点数、分数类。如果用浮点数的话，会有舍入误差。但本题只有 4 张牌，舍入误差不会很大，取 ϵ=1e−9 足矣。如果两数绝对差小于 ϵ，则认为两数相等。 时间复杂度：O(n!⋅6^n)，其中 n 是 cards 的长度。 空间复杂度：O(n^2)。递归 O(n) 层，每层消耗 O(n) 空间。 ...
LeetCode 210 https://leetcode.cn/problems/course-schedule-ii/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 拓扑排序，每次将入度为 0 的节点加入队列。 时间复杂度: O(n+m)，其中 n 为课程数，m 为先修课程的要求数。 空间复杂度: O(n+m)。 ...
LeetCode 611 https://leetcode.cn/problems/valid-triangle-number/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 为了能够使用相向双指针，先对数组从小到大排序，然后枚举最长边。因为如果枚举最短边，当 a + b < c 时，增大 b 或 减少 c 都可以满足条件，无法知道移动哪一个指针。 外层循环枚举最长边 c=nums[k]，内层循环用相向双指针枚举 a=nums[i] 和 b=nums[j]，具体如下： 初始化左右指针 i=0, j=k−1。 如果 nums[i]+nums[j]>c，由于数组是有序的，nums[j] 与下标 i′ 在 [i,j−1] 中的任何 nums[i′] 相加，都是 >c 的，因此直接找到了 j−i 个合法方案，加到答案中，然后将 j 减一。 如果 nums[i]+nums[j]≤c，由于数组是有序的，nums[i] 与下标 j′ 在 [i+1,j] 中的任何 nums[j′] 相加，都是 ≤c 的，因此后面无需考虑 nums[i]，将 i 加一。 重复上述过程直到 i≥j 为止。 时间复杂度：O(n^2)，其中 n 为 nums 的长度。 空间复杂度：O(1)。忽略排序的栈开销。 ...
LeetCode 44 https://leetcode.cn/problems/wildcard-matching/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 动态规划，我们用 dp[i][j] 表示字符串 s 的前 i 个字符和模式 p 的前 j 个字符是否能匹配。状态转移方程为 if (p[j - 1] == '*') { dp[i][j] = dp[i][j - 1] | dp[i - 1][j]; } else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } 时间复杂度：O(mn)，其中 m 和 n 分别是字符串 s 和模式 p 的长度。 空间复杂度：O(mn)，即为存储所有 (m+1)(n+1) 个状态需要的空间。此外，在状态转移方程中，由于 dp[i][j] 只会从 dp[i][..] 以及 dp[i−1][..] 转移而来，因此我们可以使用滚动数组对空间进行优化，即用两个长度为 n+1 的一维数组代替整个二维数组进行状态转移，空间复杂度为 O(n)。 ...
LeetCode 85 https://leetcode.cn/problems/maximal-rectangle/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题是 LeetCoce 84 柱状图中最大的矩形的升级版，枚举矩形的底边，做 m 次 largestRectangleArea。如果 matrix[i][j]=0，那么没有柱子，高度等于 0。否则，在上一行柱子的基础上，把柱子高度增加 1。 时间复杂度：O(mn)，其中 m 和 n 分别为 matrix 的行数和列数。做 m 次 84 题，每次 O(n)。 空间复杂度：O(n)。 ...
LeetCode 384 https://leetcode.cn/problems/shuffle-an-array/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ Knuth 洗牌算法，i 从 n - 1 遍历到 0，j 为 [0, i] 中的随机数，交换 i，j。 取随机数的方法为 rand() % (i + 1)。rand() 函数定义在 cstdlib 头文件中。 时间复杂度： 初始化：O(n)，其中 n 为数组中的元素数量。我们需要 O(n) 来初始化 original。 reset：O(n)。我们需要 O(n) 将 original 复制到 nums。 shuffle：O(n)。我们只需要遍历 n 个元素即可打乱数组。 空间复杂度：O(n)。记录初始状态需要存储 n 个元素。 ...
LeetCode 9 https://leetcode.cn/problems/palindrome-number/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 反转前一半数字。特判 x<0 的情况，此时 x 一定不是回文数。特判 x > 0 且 x 个位数是 0 的情况，由于 x 的最高位一定不是 0，所以 x 一定不是回文数。 时间复杂度：如果 x≤0 则时间复杂度为 O(1)，否则时间复杂度为 O(logx)。 空间复杂度：O(1)。 ...
LeetCode 887 https://leetcode.cn/problems/super-egg-drop/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 定义状态为 dfs(i,j)，表示在有 i 次操作机会和 j 枚鸡蛋的情况下，可以让我们能确定 f 值的最大建筑层数。 在 dfs(i−1,j−1)+1 楼扔第一枚鸡蛋： 如果鸡蛋碎了，接下来只需要在 [1,dfs(i−1,j−1)] 中扔鸡蛋，就可以确定 f 的值。 如果鸡蛋没碎，问题变成在有 i−1 次操作机会和 j 枚鸡蛋的情况下，可以让我们能确定 f 值的最大建筑层数。这个子问题的答案 dfs(i−1,j)，加上 dfs(i−1,j−1) + 1，就是原问题的答案 dfs(i,j)。 所以有 dfs(i,j) = dfs(i−1,j) + dfs(i−1,j−1) + 1 时间复杂度：O(nk)。瓶颈主要在创建数组上。 空间复杂度：O(nk)。 ...