LeetCode 11/24 11/25 周赛/双周赛

太长时间不参加周赛手生了很多，有时间就打，没时间刷熟 LeetCode Hot 100 + 面试题150 + LCR

双周赛

T3 3362. 零数组变换 III

题目大意

给定一个整数数组 nums 和二维数组 queries，每个操作 [li, ri] 可以将 nums[li] 到 nums[ri] 范围内的每个元素 最多减 1。

求最多可以删除多少个操作，使剩余操作仍能将 nums 变为全零数组。如果无法变为零数组，返回 -1。

代码实现

class Solution:
    def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:
        n = len(nums)  # 数组长度

        # 用于存储每个起点的终点区间
        g = defaultdict(list)
        for l, r in queries:
            g[l].append(r)

        ans = 0  # 被选中（未删除）的 queries 数量
        sel = []  # 当前被选中区间的终点（小根堆）
        hq = []   # 当前可选区间的终点（大根堆，用负数模拟）

        # 遍历 nums 的每一个位置
        for i, x in enumerate(nums):
            # 移除已经过期的区间（小于当前下标 i 的）
            while sel and sel[0] < i:
                heappop(sel)
            
            # 将起点为 i 的所有区间终点加入大根堆
            for r in g[i]:
                heappush(hq, -r)
            
            # 需要为当前下标 i 的值 x 找到足够的区间来覆盖
            while x > len(sel):
                # 如果当前没有可用的区间或区间不合法，返回 -1
                if not hq or -hq[0] < i:
                    return -1
                # 从最大终点区间中选取一个
                heappush(sel, -heappop(hq))
                ans += 1  # 统计被选中的区间数
        
        # 返回最多可以删除的 queries 数量
        return len(queries) - ans

T4 3363. 最多可收集的水果数目

题目大意

给定一个 n x n 的网格 fruits，其中 fruits[i][j] 表示房间 (i, j) 中的水果数量。三个小朋友分别从 (0,0)、(0,n-1) 和 (n-1,0) 出发，每人移动 n-1 次到达 (n-1,n-1)。 他们会收集经过房间的水果，且同一房间的水果只能被一个小朋友收集。求三人最多可以收集的水果总数。

代码实现

class Solution:
    def maxCollectedFruits(self, fruits: List[List[int]]) -> int:
        n = len(fruits)

        # 定义一个递归函数，计算从 (i, j) 到终点的最大收集水果数
        @cache
        def dfs(i: int, j: int) -> int:
            # 检查坐标是否越界（限制在网格内）
            if not (n - 1 - i <= j < n):
                return -inf
            # 如果到达起点 (0, x)，直接返回房间中的水果数量
            if i == 0:
                return fruits[i][j]
            # 三种可能的移动方式
            return max(
                dfs(i - 1, j - 1),  # 左上
                dfs(i - 1, j),      # 上
                dfs(i - 1, j + 1)   # 右上
            ) + fruits[i][j]

        # 统计第一条路径 (0, 0) 出发的小朋友收集的水果
        ans = sum(fruits[i][i] for i in range(n))

        # 计算第二条路径，从右上角 (0, n-1) 出发
        ans += dfs(n - 2, n - 1)  # 从倒数第二行往上递归计算
        dfs.cache_clear()

        # 对网格转置，相当于主对角线翻转，用于计算第三条路径
        fruits = list(zip(*fruits))

        # 计算第三条路径，从左下角 (n-1, 0) 出发
        ans += dfs(n - 2, n - 1)
        return ans

周赛

T3 3366. 最小数组和

题目大意

给定一个整数数组 nums 和三个整数 k、op1 和 op2，你需要通过以下两种操作尽可能减少数组元素的和：

  1. 操作 1: 选择一个下标 i，将 nums[i] 除以 2 并向上取整。每个下标最多只能应用一次此操作，最多可以应用 op1 次。
  2. 操作 2: 选择一个下标 i，仅当 nums[i] >= k 时，从 nums[i] 中减去 k。每个下标最多只能应用一次此操作，最多可以应用 op2 次。

两种操作可以应用于同一个下标，但每种操作最多只能应用一次。

你需要计算出经过任意次数的操作后，数组元素和的最小可能值。

代码实现（含注释）

class Solution:
    def minArraySum(self, nums: List[int], k: int, op1: int, op2: int) -> int:
        # 初始化变量
        n = len(nums)
        # 创建 DP 表 f，其中 f[i][j][x] 表示处理前 i 个元素时，使用 j 次操作 1 和 x 次操作 2 的最小和
        f = [[[float('inf')] * (op2 + 1) for _ in range(op1 + 1)] for _ in range(2)]
        f[0][0][0] = 0  # 初始状态，未操作时和为 0

        # 动态规划迭代
        for i in range(1, n + 1):  # 遍历每个元素
            cur, prev = i % 2, (i - 1) % 2  # 当前和前一状态的索引
            for j in range(op1 + 1):  # 遍历操作 1 的使用次数
                for x in range(op2 + 1):  # 遍历操作 2 的使用次数
                    # 不对 nums[i-1] 操作
                    f[cur][j][x] = f[prev][j][x] + nums[i - 1]

                    # 如果可以使用操作 1
                    if j > 0:
                        f[cur][j][x] = min(
                            f[cur][j][x], 
                            f[prev][j - 1][x] + math.ceil(nums[i - 1] / 2)
                        )

                    # 如果可以使用操作 2 且 nums[i-1] >= k
                    if x > 0 and nums[i - 1] >= k:
                        f[cur][j][x] = min(
                            f[cur][j][x], 
                            f[prev][j][x - 1] + max(nums[i - 1] - k, 0)
                        )

                    # 如果可以同时使用操作 1 和操作 2
                    if j > 0 and x > 0:
                        reduced = math.ceil(nums[i - 1] / 2)  # 操作 1 后的值
                        if reduced >= k:  # 操作 1 后仍可应用操作 2
                            f[cur][j][x] = min(
                                f[cur][j][x], 
                                f[prev][j - 1][x - 1] + max(reduced - k, 0)
                            )
                        if nums[i - 1] >= k:  # 操作 2 后仍可应用操作 1
                            after_sub = nums[i - 1] - k
                            f[cur][j][x] = min(
                                f[cur][j][x], 
                                f[prev][j - 1][x - 1] + math.ceil(after_sub / 2)
                            )

        # 计算最终结果
        res = float('inf')
        for j in range(op1 + 1):
            for x in range(op2 + 1):
                res = min(res, f[n % 2][j][x])  # 取所有可能状态的最小值

        return res

T4 3367. 移除边之后的权重最大和

题目大意

给定一棵有 nnn 个节点的无向树，树中每条边有权重，节点编号从 000 到 n−1n-1n−1。输入是一个长度为 n−1n-1n−1 的二维整数数组 edges，其中每个元素 [u_i, v_i, w_i]表示节点 ui 和 vi之间有一条权重为 wi 的边。

任务是：

  • 移除零条或多条边，使得每个节点与最多 kkk 个其他节点直接相连。
  • 在满足上述条件下，剩余边的权重之和最大化。

返回满足条件的 最大可能权重和。

代码实现

class Solution:
    def maximizeSumOfWeights(self, edges: List[List[int]], k: int) -> int:
        # 建立邻接表存储树的结构
        graph = defaultdict(list)
        for x, y, weight in edges:
            graph[x].append((y, weight))
            graph[y].append((x, weight))
        
        # 深度优先搜索，返回 (不选当前节点的最大权重和, 选当前节点的最大权重和)
        def dfs(node: int, parent: int) -> Tuple[int, int]:
            # `not_choose` 表示当前节点不选择时的最大权重和
            not_choose = 0
            # `inc` 存储所有子树中权重的增量值（选择 vs 不选择子树）
            increments = []

            # 遍历子节点
            for neighbor, weight in graph[node]:
                if neighbor == parent:
                    continue  # 跳过父节点，避免回环
                nc, c = dfs(neighbor, node)  # 子节点递归计算
                not_choose += nc  # 累加子节点不选时的最大权重和
                # 如果选择子节点可以增加权重，将增量存入 `increments`
                delta = c + weight - nc
                if delta > 0:
                    increments.append(delta)
            
            # 按增量从大到小排序，取前 k 或 k-1 个
            increments.sort(reverse=True)
            choose_k = not_choose + sum(increments[:k])  # 选 k 个增量
            choose_k_minus_1 = not_choose + sum(increments[:k - 1])  # 选 k-1 个增量
            
            return choose_k, choose_k_minus_1
        
        # 递归从根节点开始，返回最大可能的权重和
        return max(dfs(0, -1))