算法题记录 37

2873.有序三元组中的最大值1（1270）

给你一个下标从 0 开始的整数数组 nums 。

请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。

下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。

涉及知识点

贪心，前后缀

解决思路

可以直接暴力求解，但是时间复杂度为O(n^3)，所以我们可以结合贪心策略用前后缀记录来求解。

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums)
        suf_max = [0] * (n + 1)
        for i in range(n - 1, 1, -1):
            suf_max[i] = max(suf_max[i + 1], nums[i])

        ans = pre_max = 0
        for j, x in enumerate(nums):
            ans = max(ans, (pre_max - x) * suf_max[j + 1])
            pre_max = max(pre_max, x)
        return ans

139.单词拆分（中等）

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

涉及知识点

动态规划

解决思路

可以用动态规划来解决，dp[i]表示前i个字符是否可以被拆分成字典中的单词。

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

        for i in range(1, n + 1):
            for j in range(i):
                if dp[j] and s[j:i] in word_set:
                    dp[i] = True
                    break

        return dp[n]

300.最长递增子序列（中等）

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

涉及知识点

动态规划

解决思路

我们用dp[i]来表示以nums[i]结尾的最长递增字序列的长度。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n=len(nums)
        dp=[1]*n
        for i in range(1,n):
            for j in range(i):
                if nums[i]>nums[j]:
                    dp[i]=max(dp[i],dp[j]+1)
        return max(dp)

152.乘积最大子数组（中等）

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

涉及知识点

动态规划

解决思路

考虑有负数的情况，负数的乘积可能会变正数，所以我们要维护两个数组，一个是最大值，一个是最小值。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        f_max = [0] * n
        f_min = [0] * n
        f_max[0] = f_min[0] = nums[0]
        for i in range(1, n):
            x = nums[i]
            # 把 x 加到右端点为 i-1 的（乘积最大/最小）子数组后面，
            # 或者单独组成一个子数组，只有 x 一个元素
            f_max[i] = max(f_max[i - 1] * x, f_min[i - 1] * x, x)
            f_min[i] = min(f_max[i - 1] * x, f_min[i - 1] * x, x)
        return max(f_max)

416.分割等和子集（中等）

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

涉及知识点

动态规划

解决思路

化归成背包问题，求一个子集的和为sum(nums)/2。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n=len(nums)
        s=sum(nums)
        if s%2!=0:
            return False
        target=s//2
        @cache
        def dfs(i:int,target:int)->bool:
            if target==0:
                return True
            if i>=n or target<0:
                return False
            return dfs(i+1,target-nums[i]) or dfs(i+1,target)
        return dfs(0,target)

声明

题目均来源于leetcode公开题库，部分方法解析来源于高赞题解，如有不妥请联系。