NeetCode刷题第19天(2025.1.31)

099 Maximum Product Subarray 最大乘积子数组

给定一个整数数组 nums，找到数组中乘积最大的子数组并返回它。
子数组是数组中连续的非空元素序列。
您可以假设输出将适合 32 位整数。

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

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

解题1：

如果全部都是正数的话，他们的乘积一定是连续递增的。

这里可以每次都标记一个最大和一个最小值。有一个特殊情况，就是当0出现的时候，因为0乘以任何数都为0，所以这个时候我们要跳过0，把最大最小值从1开始重新计数。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        res = max(nums)
        curMin, curMax = 1, 1

        for n in nums:
            if n == 0:
                curMin, curMax = 1, 1
                continue
            tmp = curMax * n
            curMax = max(tmp, n * curMin, n)
            curMin = min(tmp, n * curMin, n)
            res = max(res, curMax)
        return res

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

100 Word Break 断字

给定一个字符串 s 和一个字符串 wordDict 字典，如果s可以分割成一个以空格分隔的字典单词序列，则返回true 。
您可以无限次重复使用字典中的单词。您可以假设所有字典单词都是唯一的。

示例1：
Input: s = "neetcode", wordDict = ["neet","code"]
Output: true
说明：返回 true，因为 “neetcode” 可以拆分为 “neet” 和 “code”。

示例2：
Input: s = "applepenapple", wordDict = ["apple","pen","ape"]
Output: true
说明：返回 true，因为 “applepenapple” 可以拆分为 “apple”、“pen” 和 “apple”。请注意，我们可以重复使用单词，也可以不使用所有单词。

示例3：
Input: s = "catsincars", wordDict = ["cats","cat","sin","in","car"]
Output: false

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

这里我们的决策树是按照wordDict中的词来划定每个节点的。

这里我们从后往前。当i=7的时候，sub_s=“e”,长度为1，而wordDict中的长度都大于他，显然不可能匹配到，所以dp[7]=False。

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False] * (len(s) + 1)
        dp[len(s)] = True

        for i in range(len(s) - 1, -1, -1):
            for w in wordDict:
                if (i + len(w)) <= len(s) and s[i : i + len(w)] == w:
                    dp[i] = dp[i + len(w)]
                if dp[i]:
                    break
        return dp[0]

时间复杂度: $O(n\ast m\ast t)$
空间复杂度: $O(n)$
n 是字符串 s 的长度 ， m 是 中的 wordDict 单词数， t 是 中 wordDict 任何单词的最大长度。

101 Longest Increasing Subsequence 最长递增的子序列

给定一个整数数组 nums ，返回最长的严格递增的子序列的长度。
子序列是一个序列，它可以通过删除一些元素或不删除元素而不更改其余字符的相对顺序来从给定序列派生。
例如， “cat” 是 “crabt” 的子序列。

示例1：
Input: nums = [9,1,4,2,3,3,7]
Output: 4
说明：最长递增的子序列是 [1,2,3,7]，长度为 4。

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

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

LIS[2]可能是1或者1+LIS[3],但是nums[2]<nums[3],所以1+LIS[3]就排除了。

在LIS[0]的时候，因为后面的都比1大，所以要把该位置和后面都进行相加，然后选择最大的。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        LIS = [1] * len(nums)

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

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

102 Maximum Product Subarray 最大乘积子数组

给定一个整数数组 nums，找到数组中乘积最大的子数组并返回它。
子数组是数组中连续的非空元素序列。
您可以假设输出将适合 32 位整数。

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

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

解题1：

class Solution:
    def countSubstrings(self, s: str) -> int:
        res = 0

        for i in range(len(s)):
            res += self.countPali(s, i, i)
            res += self.countPali(s, i, i + 1)
        return res
    
    def countPali(self, s, l, r):
        res = 0
        while l >= 0 and r < len(s) and s[l] == s[r]:
            res += 1
            l -= 1
            r += 1
        return res

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

103 Partition Equal Subset Sum 分区等于子集和

您将获得一个正整数 nums 数组。
如果可以将数组划分为两个子集，即 subset1 和 subset2，其中 sum（subset1） == sum（subset2），则返回 true。否则，返回 false。

示例1：
Input: nums = [1,2,3,4]
Output: true
说明：数组可以分区为 [1， 4] 和 [2， 3]。

示例2：
Input: nums = [1,2,3,4,5]
Output: false

解题1：
要把元素分成和相等的两部分，那就先把所有元素相加再除以2，就知道每个部分是多少。下面是决策树。


我们每在决策树中使用一个元素，就把该元素从数组中去除，使用余下的子数组。同时，左右子树的target表示我们还需呀多少，每次更新一层，我们就会更新i和target。

我们使用自下而上的动态规划，在set中列出所有可能的和的情况。首先最后一个5和默认0开始，往前面一个位置遍历，0+11=11，5+11=16，添加到set中，此时set={0,5,11,16}。接下来是5，再把我和刚才的set中每个位置元素相加，依次类推，得到最终的set集合。

class Solution:
    def countSubstrings(self, s: str) -> int:
        res = 0

        for i in range(len(s)):
            res += self.countPali(s, i, i)
            res += self.countPali(s, i, i + 1)
        return res
    
    def countPali(self, s, l, r):
        res = 0
        while l >= 0 and r < len(s) and s[l] == s[r]:
            res += 1
            l -= 1
            r += 1
        return res

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

104 Unique Paths 唯一路径

有一个 m x n 网格，您可以在任何时间点向下或向右移动。
给定两个整数 m 和 n，返回从网格左上角 （grid[0][0]） 到右下角 （grid[m - 1][n - 1]） 可以采用的可能的唯一路径的数量。
您可以假设输出将适合 32 位整数。

示例1：
Input: m = 3, n = 6
Output: 21

示例2：
Input: m = 3, n = 7
Output: 28

解题1： 动态规划（空间优化）

我们从终点开始往回走。因为我们只有向下和向右两条路径，所以每个位置可能的路径数就是下面和右面已知路径的总和。

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 这里先设置最后一行都为1
        row = [1] * n
        
        # 从下往上计算每行
        for i in range(m - 1):
            # 每行都先置为1
            newRow = [1] * n
            # 因为最右侧的一列只可以往下走，所以路径只有一个
            # 需要从倒数第二轮开始遍历
            for j in range(n - 2, -1, -1):
                newRow[j] = newRow[j + 1] + row[j]
            row = newRow
        return row[0]

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

105 Longest Common Subsequence 最长公共 Subsequence

给定两个字符串 text1 和 text2，如果存在一个字符串，则返回两个字符串之间最长的公共子序列的长度，否则返回 0。
子序列是一个序列，它可以通过删除一些元素或不删除元素而不更改其余字符的相对顺序来从给定序列派生。
例如，“cat” 是 “crabt” 的子序列。
两个字符串的公共子序列是存在于两个字符串中的子序列。

示例1：
Input: text1 = "cat", text2 = "crabt" 
Output: 3 
解释： 最长的公共子序列是 “cat”，长度为 3。

示例2：
Input: text1 = "abcd", text2 = "abcd"
Output: 4

示例3：
Input: text1 = "abcd", text2 = "efgh"
Output: 0

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

这里是一个二维的矩阵，刚开始都初始化为0。我们从右下往左上进行遍历。当匹配到一个字符的时候就把右下位置+1的值赋值到该位置。

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # 初始化二维矩阵
        dp = [[0 for j in range(len(text2) + 1)] for i in range(len(text1) + 1)]

        for i in range(len(text1) - 1, -1, -1):
            for j in range(len(text2) - 1, -1, -1):
                if text1[i] == text2[j]:
                    dp[i][j] = 1 + dp[i + 1][j + 1]
                else:
                    dp[i][j] = max(dp[i][j + 1], dp[i + 1][j])
        return dp[0][0]

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