LeetCode双周赛132 & 周赛401(240608/09)

3181. 执行操作可获得的最大总奖励 II周赛第四题

题目大意

给定一个整数数组 rewardValues，长度为 n，表示不同位置的奖励值。初始时，总奖励 x 为 0，所有下标都是未标记的。可以执行以下操作任意次：

  • 从区间 [0, n-1] 中选择一个未标记的下标 i。
  • 如果 rewardValues[i] 大于当前的总奖励 x，则将 rewardValues[i] 加到 x 上，并标记下标 i。

要求返回执行最优操作能够获得的最大总奖励。

实现思路

  1. 使用动态规划的思想解决问题，考虑如何选择操作能使得总奖励最大化。
  2. 使用一个状态 f 表示当前可以达到的最大总奖励的二进制表示。初始状态 f = 1 表示可以达到总奖励为 0 的状态。
  3. 遍历奖励值 rewardValues 的不同值，对每个值进行处理：
    • 将该奖励值作为新的状态加入到当前状态 f 中。
  4. 最终 f 的位长度减去 1 即为可以达到的最大总奖励。

该解法利用了动态规划和位运算的特性，通过状态的更新和转移，实现了对最优操作序列的求解，保证了时间复杂度在合理范围内。

class Solution:
    def maxTotalReward(self, r: List[int]) -> int:
        f = 1
        
        for v in sorted(set(r)):
            mask = (1 << v) - 1
            mask = mask & f 
            mask = mask << v
            f |= mask
        
        return f.bit_length() - 1

3177. 求出最长好子序列 II双周赛第四题

题目大意

给你一个整数数组 nums 和一个非负整数 k。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中存在不超过 k 个下标 i 使得 seq[i] != seq[i + 1]，那么我们称这个整数序列为 好序列。

请你返回 nums 中 好子序列 的最长长度。

实现思路

  1. 预处理：将 nums 中的元素离散化，即将每个元素映射到一个新的唯一整数，这样可以简化后续的处理。用 d 字典保存每个元素的离散化后的值。
  2. 动态规划：使用二维数组 f 记录当前子序列的最大长度，其中 f[nm][i] 表示以 nm 结尾且有 i 次不连续的最大长度。
    • 另用 mx 记录使用 i 次变换的最大长度，lst 记录该最大长度对应的最后一个元素。
  3. 状态转移：遍历 nums 中的每个元素 nm，并更新 f 和 mx、lst。
    • 如果 i > 0，则 f[nm][i] 更新为 f[lst[i-1]][i-1] + 1。
    • 更新 mx[i] 和 lst[i]，保证它们记录当前的最大值和对应元素。
  4. 结果：最终的结果为 res，记录所有情况下的最大长度。
class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        # 离散化
        d = {v: i for i, v in enumerate(set(nums))}
        if len(d) == 1:
            return len(nums)
        
        n = len(d)
        nums = [d[x] for x in nums]
        
        # 初始化动态规划数组
        f = [[0] * (k + 1) for _ in range(n + 1)]
        mx, lst = [0] * (k + 1), [0] * (k + 1)
        res = 0

        for nm in nums:
            for i in range(k, -1, -1):
                f[nm][i] += 1
                if i and f[lst[i - 1]][i - 1] + 1 > f[nm][i]:
                    f[nm][i] = f[lst[i - 1]][i - 1] + 1
                if f[nm][i] > mx[i]:
                    mx[i] = f[nm][i]
                    lst[i] = nm
                
                if f[nm][i] > res:
                    res = f[nm][i]

        return res