Leetcode 背题

发表于 Disqus：

今天开始了漫长的刷题流程。之前只是简单做了一些题目，保持手感，但今天开始，就要为面试正式准备了。

之前一直在思考一个问题：如何高效地刷 Leetcode。我认为，要高效地刷题，首先就得背题。书读百遍，其义自见，大语言模型经过大量训练，也锻炼出了写代码的能力。同样地，我相信 Leetcode 也一样，通过多次练习，答案自然会浮现，量变产生质变。

53. Maximum Subarray

解题思路可以使用 Kadane’s Algorithm，代码如下：

1
2
3
4
5
6
def maxSubArray(nums):
    max_current = max_global = nums[0]
    for num in nums[1:]:
        max_current = max(num, max_current + num)
        max_global = max(max_global, max_current)
    return max_global

这是一个典型的动态规划题目，上面的算法其实隐藏了动态规划的本质。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
        }
        return *max_element(dp.begin(), dp.end());
    }
};

这段代码更好地体现了动态规划的思想。

理解 dp[i] = max(nums[i] + dp[i-1], nums[i]) 的公式可以从动态规划的角度来解析。这个公式的核心在于“在每一个位置上，我们要做出一个最优选择”。以下是详细解释：

1. dp[i] 的含义是什么？

  • dp[i] 表示以位置 i 结尾的 最大子数组和。

2. 为什么比较 nums[i] + dp[i-1] 和 nums[i]？

  • 核心问题是：当前的最大子数组和是否应该包括之前的部分（dp[i-1]）？
    • **nums[i] + dp[i-1]**：如果 dp[i-1] 是正数，加上当前的 nums[i] 会让子数组和变大，那么我们选择累加。
    • **nums[i]**：如果 dp[i-1] 是负数，我们选择从当前位置重新开始一个新的子数组，因为负数只会拖累当前和。

3. 为什么不用比较后续的数？

  • 我们在比较时，是假设数组在位置 i 停止。也就是说，我们考虑 [0:i] 这个范围内的最大值，对于位置 i 来说，要么加上之前的子数组，要么放弃之前的子数组，只采用当前的数。
  • 然后，我们遍历整个数组，找出在每个位置停下来的最大值，最终返回最大的那个值。

57. Insert Interval

这是一个经典的区间合并问题，需要将新插入的区间合并到已有的区间中。

可以使用分解法来解决：

  • 第一步，将不重叠且在 newInterval 之前的区间添加到结果中。
  • 第二步，合并所有可能重叠的区间到 newInterval 中，注意这里的判断条件。
  • 第三步，将剩余的区间添加到结果中。

注意，合并区间的判断条件是前一个区间的开始小于等于后一个区间的结束，即 intervals[i][0] <= newInterval[1]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        ret_list = []
        i = 0

        while i < len(intervals) and intervals[i][1] < newInterval[0]:
            ret_list.append(intervals[i])
            i += 1

        while i < len(intervals) and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(intervals[i][0], newInterval[0])
            newInterval[1] = max(intervals[i][1], newInterval[1])
            i += 1

        ret_list.append(newInterval)

        while i < len(intervals):
            ret_list.append(intervals[i])
            i += 1

        return ret_list

只要注意细节，这个题目其实并不难。

300. Longest Increasing Subsequence

显然是一个动态规划问题。

dp[i] 表示以某个数字结尾的最长递增子序列的长度。

每次加入一个元素，我们更新当前的 dp 数组，如果当前数字比之前的小，它们的结果就加 1。

注意，第一个 dp[i] 是从下标 1 开始的。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1] * len(nums)

        for i in range(1, len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)

复杂度分析：

  • 时间复杂度：$O(n^2)$，因为有两个嵌套的循环。
  • 空间复杂度：$O(n)$，因为需要一个长度为 n 的 dp 数组。

674. Longest Continuous Increasing Subsequence

这是一个简单题目，但仍然值得理解。

1
2
3
4
5
6
7
class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        dp = [1] * len(nums)
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                dp[i] = max(dp[i], dp[i-1] + 1)
        return max(dp)

392. Is Subsequence

1
2
3
4
5
6
7
8
9
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i = 0
        j = 0
        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                i += 1
            j += 1
        return i == len(s)

这个题目可以用双指针法，以 t 为基准，如果 s 中有相同字符就向前推进，如果 s 到结尾了，说明匹配完成。

115. Distinct Subsequences

这个问题要求我们找到字符串 s 中有多少不同的子序列等于字符串 t。

首先，我们需要定义 dp，其中 dp[i][j] 表示从 s 的前 i 个字符中形成 t 的前 j 个字符的不同子序列数。

  • dp[i][0] 表示当 t 为空串时，结果为 1。
  • dp[0][j] 表示从空串中形成 t，结果为 0。

对于 dp[i][j]，其结果取决于位置 i 和 j 的字符：

  • 如果两者相等，结果等于不匹配 s[i-1] 的情况（dp[i-1][j]）加上匹配的情况（dp[i-1][j-1]）。
  • 如果不相等，则结果等于 dp[i-1][j]。

注意，这里 i, j 指的是前 i 个和前 j 个字符。

此外，dp[0][0] 初始化为 1，因为空字符串是任何字符串的子序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        dp = [[0 for _ in range(len(t) + 1)] for _ in range(len(s) + 1)]
        for i in range(len(s) + 1):
            dp[i][0] = 1

        for j in range(1, len(t) + 1):
            for i in range(1, len(s) + 1):
                if s[i-1] == t[j-1]:
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
                else:
                    dp[i][j] = dp[i-1][j]

        return dp[-1][-1]