NeetCode刷题第20天(2025.2.1)

106 Best Time to Buy and Sell Stock with Cooldown 使用 Cooldown 买卖股票的最佳时间

给定一个整数数组价格，其中的价格 [i] 是第i天 NeetCoin 的价格。
您可以多次买卖一个 NeetCoin，但有以下限制：

• 出售 NeetCoin 后，第二天不能再购买一个（即有一天的冷却期）。
• 您一次最多只能拥有一个 NeetCoin。

您可以完成任意数量的交易。
返回您可以实现的最大利润。

示例1：
Input: prices = [1,3,4,0,4]
Output: 6
说明：第 0 天买入（价格 = 1），第 1 天卖出（价格 = 3），利润 = 3-1 = 2。然后在第 3 天买入（价格 = 0），在第 4 天卖出（价格 = 4），利润 = 4-0 = 4。总利润为 2 + 4 = 6。

示例2：
Input: prices = [1]
Output: 0

解题1： 递归
下面是根据题目绘制的一棵决策树

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 状态：buying or selling?
        # 如果 buying: i + 1
        # 如果 selling: i + 2

        dp = {}

        def dfs(i, buying):
            if i >= len(prices):
                return 0
            if (i, buying) in dp:
                return dp[(i, buying)]
            
            cooldown = dfs(i + 1, buying)
            if buying:
                buy = dfs(i + 1, not buying) - prices[i]
                dp[(i, buying)] = max(buy, cooldown)
            else:
                sell = dfs(i + 2, not buying) + prices[i]
                dp[(i, buying)] = max(sell, cooldown)
            return dp[(i, buying)]
        return dfs(0, True)

时间复杂度: $O(2^n)$
空间复杂度: $O(n)$

107 Coin Change II 换币 II

您将获得一个整数数组硬币，代表不同面额的硬币（例如 1 美元、5 美元等）和一个代表目标金额的整数金额。
返回总计达到 amount 的非重复组合的数量。如果无法补足金额，则返回 0。
您可以假设每个硬币的数量不受限制，并且硬币中的每个值都是唯一的。

示例1：
Input: amount = 4, coins = [1,2,3]
Output: 4
解释：
1+1+1+1 = 4
1+1+2 = 4
2+2 = 4
1+3 = 4

示例2：
Input: amount = 7, coins = [2,4]
Output: 0

解题1： 二维动态规划（自下而上）

如果我们使用常规的决策树，通过上面可以看到，会存在重复。那么如何消除呢？

这里我们每个子树的子孙节点只可以添加该值之后的硬币就可以消除冗余。比如这里的2，之后我们只可以添加coins中2及其后面的硬币（即2和5）。
使用dfs进行循环，这里的i是coins的索引，a则是目前为止的综合。如果总和大于amount就停止，表示该路径不满足条件，返回0。

这里的1我们从下往上看。最后一个1表示，当我们使用硬币5时，有几种组合使得和为0，显然是0，当用0和硬币。倒数第二个1表示，当使用硬币2和5时，有几种可能使得结果为0，显然也是1种。

在这个位置中，当我们加入一个硬币2时，所需的值就是1-2=-1，显然超出范围不合理。我们每次向右硬币值个单位和向下看，两者的和就是该位置的值。

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        
        dp = [[0] * (len(coins) + 1) for i in range(amount + 1)]
        dp[0] = [1] * (len(coins) + 1)

        for a in range(1, amount + 1):
            for i in range(len(coins) - 1, -1, -1):
                dp[a][i] = dp[a][i + 1]
                if a - coins[i] >= 0:
                    dp[a][i] += dp[a - coins[i]][i]
        return dp[amount][0]

时间复杂度: $O(n\ast a)$
空间复杂度: $O(n\ast a)$
n是硬币的数量，a 是给定的数量。

108 Target Sum 目标总和

您将获得一个整数数组 nums 和一个整数目标。
对于数组中的每个数字，您可以选择将其相加或相减为总和。

• 例如，如果 nums = [1, 2]，则一个可能的和将是 “+1-2=-1”。

如果 nums=[1,1]，则有两种不同的方法可以将输入的数字相加得到 0 的总和：“+1-1” 和 “-1+1”。
返回您可以构建表达式的不同方法的数量，以便总和等于 target。

示例1：
Input: nums = [2,2,2], target = 2
Output: 3
说明：有 3 种不同的方法可以将输入的数字相加得到 2 的总和。
+2 +2 -2 = 2
+2 -2 +2 = 2
-2 +2 +2 = 2

解题1： 递归

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        dp = {} # (index, cur_sum) -> num of ways

        def backtrack(i, cur_sum):
            # 为了减少重复的计算，可以存储已经计算过的
            if (i, cur_sum) in dp:
                return dp[(i, cur_sum)]
            
            if i == len(nums):
                return 1 if cur_sum == target else 0
            
            dp[(i, cur_sum)] = (
                # 加上或减去
                backtrack(i + 1, cur_sum + nums[i]) +
                backtrack(i + 1, cur_sum - nums[i])
            )
            return dp[(i, cur_sum)]
        return backtrack(0, 0)

时间复杂度: $O(2^n)$
空间复杂度: $O(n)$

109 Interleaving String 交错字符串

有三个字符串 s1，s2 和 s3。如果 s3 是由 s1 和 s2 交错形成的，返回 true，否则返回 false。
交错两个字符串 s 和 t 是通过将 s 和 t 分别划分为 n 和 m 子字符串来完成的，其中满足以下条件：

• |n - m| <= 1，即 s 和 t 的子字符串数量之差最多为 1。
• t = t1 + t2 + … + tm
• 交错s 和 t 是 s1 + t1 + s2 + t2 + …或 t1 + s1 + t2 + s2 + …

您可以假设 s1、s2 和 s3 由小写英文字母组成。

示例1：
Input: s1 = "aaaa", s2 = "bbbb", s3 = "aabbbbaa"
Output: true

示例2：
Input: s1 = "abc", s2 = "xyz", s3 = "abxzcy"
Output: false

解题1： 递归

这是决策树，这里括号里分别表示s1和s2的索引，每当匹配到一个，就+1。

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        def dfs(i, j, k):
            # 判断三个字符串是否都遍历完了
            if k == len(s3):
                return (i == len(s1) and (j == len(s2)))
            if i < len(s1) and s1[i] == s3[k]:
                if dfs(i + 1, j, k + 1):
                    return True
            if j < len(s2) and s2[j] == s3[k]:
                if dfs(i, j + 1, k + 1):
                    return True
            return False
        return dfs(0, 0, 0)

时间复杂度: $O(n^2)$
空间复杂度: $O(1)$

解题1： 递归

这是决策树，这里括号里分别表示s1和s2的索引，每当匹配到一个，就+1。

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False
        
        dp = [[False] * (len(s2) + 1) for i in range(len(s1) + 1)]
        dp[len(s1)][len(s2)] = True

        for i in range(len(s1), -1, -1):
            for j in range(len(s2), -1, -1):
                if i < len(s1) and s1[i] == s3[i + j] and dp[i + 1][j]:
                    dp[i][j] = True
                if j < len(s2) and s2[j] == s3[i + j] and dp[i][j + 1]:
                    dp[i][j] = True
        return dp[0][0]

时间复杂度: $O(m\ast n)$
空间复杂度: $O(m\ast n)$

110 Edit Distance 编辑距离

您将获得两个字符串 word1 和 word2，每个字符串都由小写英文字母组成。
您可以对 word1 执行三个作，次数不受限制：

• 在任意位置插入字符
• 删除任意位置的字符
• 替换任意位置的字符

返回使 word1 等于 word2 的最小作数。

示例1：
Input: word1 = "monkeys", word2 = "money"
Output: 2

示例2：
Input: word1 = "neatcdee", word2 = "neetcode"
Output: 3

解题1：


动态规划图。这里最下面和最右面还有空的两行。以上面图为例，顶部的3表示当w2为空，w1中有abd三字母时最少的操作次数。下面的2则表示当w2为空，w1为bd两字母时最少的操作次数。

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        cache =[[float("inf")] * (len(word2) + 1) for i in range(len(word1) + 1)]

        for j in range(len(word2) + 1):
            cache[len(word1)][j] = len(word2) - j
        for i in range(len(word1) + 1):
            cache[i][len(word2)] = len(word1) - i

        # 自下而上的动态规划
        for i in range(len(word1) - 1, -1, -1):
            for j in range(len(word2) - 1, -1, -1):
                if word1[i] == word2[j]:
                    cache[i][j] = cache[i + 1][j + 1]
                else:
                    cache[i][j] = 1 + min(cache[i + 1][j], cache[i][j + 1], cache[i + 1][j + 1])
        return cache[0][0]

时间复杂度: $O(m\ast n)$
空间复杂度: $O(m\ast n)$
m 是 word1 的长度，n 是 word2 的长度。

111 Maximum Subarray 最大子数组

给定一个整数数组 nums ，找到总和最大的子数组并返回总和。
子数组是数组中连续的非空元素序列。

示例1：
Input: nums = [2,-3,4,-2,2,1,-1,4]
Output: 8
说明：子数组 [4，-2,2,1，-1,4] 的最大和为 8。

解题1： Kadane 算法
如果前面的数或者前面子数组相加的和为负数，那他们就起了反向的作用，我们需要重新计数最大和。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxSub = nums[0]
        curSum = 0

        for n in nums:
            if curSum < 0:
                curSum = 0
            curSum += n
            maxSub = max(maxSub, curSum)
        return maxSub

时间复杂度: $O(n)$
空间复杂度: $O(1)$

112 Jump Game 跳跃游戏

你得到一个整数数组 nums，其中每个元素 nums[i] 表示你在该位置的最大跳跃长度。
如果可以访问从索引 0 开始的最后一个索引，则返回 true，否则返回 false。

示例1：
Input: nums = [1,2,0,1,0]
Output: true
解释：首先从索引 0 跳转到 1，然后从索引 1 跳转到 3，最后从索引 3 跳转到 4。

示例2：
Input: nums = [-2,-1]
Output: 2

解题1： 贪婪算法

这是一棵决策树，但是我们可以看到2其实已经访问过了。同时，我们可以知道，如果到了2，那么就不可能成功，所以这里设置dp[2] = False。

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        goal = len(nums) - 1

        for i in range(len(nums) - 1, -1, -1):
            if i + nums[i] >= goal:
                goal = i
        return True if goal == 0 else False

时间复杂度: $O(n)$
空间复杂度: $O(1)$

113 Jump Game II 跳跃游戏 II

给你一个整数数组，其中 nums [i] 表示从索引 i 向右跳跃的最大长度。例如，如果你在 nums [i] 处，你可以跳到任何索引 i + j，其中：

• j <= nums[i]
• i + j < nums.length

您最初位于 nums[0] 处。
返回到达数组中最后一个位置的最小跳转次数 （index nums.length - 1）。您可能会假设总是有一个有效的答案。

示例1：
Input: nums = [2,4,1,1,1,1]
Output: 2
说明：从索引 0 跳转到索引 1，然后从索引 1 跳转到最后一个索引。

示例2：
Input: nums = [2,1,2,1,0]
Output: 2

解题1： 广度优先搜索 （Greedy）

class Solution:
    def jump(self, nums: List[int]) -> int:
        res = 0
        l = r = 0

        while r < len(nums) - 1:
            farthest = 0
            for i in range(l, r + 1):
                farthest = max(farthest, i + nums[i])
            l = r + 1
            r = farthest
            res += 1
        return res

时间复杂度: $O(n)$
空间复杂度: $O(1)$