力扣第 467 场周赛

569
Contest
LeetCode
本文最后更新于 3 分钟前，文中所描述的信息可能已发生改变。

3683. 完成一个任务的最早时间 - 力扣（LeetCode） ​

题目类型 ​

#遍历

解题思路 ​

参考：这道题很简单！

示例代码 ​

python
class Solution:
    def earliestTime(self, tasks: List[List[int]]) -> int:
        return min(s + t for s, t in tasks)

3684. 至多 K 个不同元素的最大和 - 力扣（LeetCode） ​

题目类型 ​

#哈希 #排序 #堆

解题思路 ​

参考：这道题很简单！

示例代码 ​

python
class Solution:
    def maxKDistinct(self, nums: List[int], k: int) -> List[int]:
        return heapq.nlargest(k, set(nums))
python
class Solution:
    def maxKDistinct(self, nums: List[int], k: int) -> List[int]:
        return sorted(set(nums), reverse=True)[: k]

3685. 含上限元素的子序列和 - 力扣（LeetCode） ​

题目类型 ​

#01背包 #位运算 #计数排序

解题思路 ​

01 背包，在更新背包的同时，计算限定值是否能够满足条件

示例代码 ​

python
class Solution:
    def subsequenceSumAfterCapping(self, nums: List[int], k: int) -> List[bool]:
        n = len(nums)
        f = [False] * (k + 1)
        f[0] = True
        ans = [False] * (n + 1)

        i = 0
        nums.sort()
        for x in range(1, n + 1):
            while i < n and nums[i] == x:
                for j in range(k, x - 1, -1):
                    f[j] = f[j] or f[j - x]
                i += 1

            for j in range(min(n - i, k // x) + 1):
                if f[k - j * x]:
                    ans[x] = True
                    break
        return ans[1:]
python
class Solution:
    def subsequenceSumAfterCapping(self, nums: List[int], k: int) -> List[bool]:
        n = len(nums)
        f = 1
        u = (1 << (k + 1)) - 1
        ans = [False] * (n + 1)

        i = 0
        nums.sort()
        for x in range(1, n + 1):
            while i < n and nums[i] == x:
                f |= (f << x) & u
                i += 1

            for j in range(min(n - i, k // x) + 1):
                if f >> (k - j * x) & 1:
                    ans[x] = True
                    break
        return ans[1:]

3686. 稳定子序列的数量 - 力扣（LeetCode） ​

题目类型 ​

#子序列DP #记忆化搜索

解题思路 ​

考虑子序列结尾状态，结尾有 0-1 个奇数或偶数，记得取模

示例代码 ​

python
class Solution:
    def countStableSubsequences(self, nums: List[int]) -> int:
        mod = 1_000_000_007
        f = [0] * 4
        for i, x in enumerate(nums):
            if x % 2:
                f[3] = (f[3] + f[1]) % mod
                f[1] = (f[1] + f[0] + f[2] + 1) % mod
            else:
                f[2] = (f[2] + f[0]) % mod
                f[0] = (f[0] + f[1] + f[3] + 1) % mod
        return sum(f) % mod
力扣第 165 场双周赛
力扣第 466 场周赛