LeetCode-第440场周赛

Q1 将水果放入篮子Ⅱ

题目描述

给你两个长度为 n 的整数数组，fruits 和 baskets，其中 fruits[i] 表示第 i 种水果的 数量，baskets[j] 表示第 j 个篮子的 容量。

你需要对 fruits 数组从左到右按照以下规则放置水果：

• 每种水果必须放入第一个 容量大于等于 该水果数量的 最左侧可用篮子 中。
• 每个篮子只能装 一种 水果。
• 如果一种水果 无法放入 任何篮子，它将保持 未放置。

返回所有可能分配完成后，剩余未放置的水果种类的数量。

示例 1

输入： fruits = [4,2,5], baskets = [3,5,4]

输出： 1

解释：

• fruits[0] = 4 放入 baskets[1] = 5。
• fruits[1] = 2 放入 baskets[0] = 3。
• fruits[2] = 5 无法放入 baskets[2] = 4。

由于有一种水果未放置，我们返回 1。

示例 2

输入： fruits = [3,6,1], baskets = [6,4,7]

输出： 0

解释：

• fruits[0] = 3 放入 baskets[0] = 6。
• fruits[1] = 6 无法放入 baskets[1] = 4（容量不足），但可以放入下一个可用的篮子 baskets[2] = 7。
• fruits[2] = 1 放入 baskets[1] = 4。

由于所有水果都已成功放置，我们返回 0。

提示：

• n == fruits.length == baskets.length
• 1 <= n <= 100
• 1 <= fruits[i], baskets[i] <= 1000

题解-模拟

class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        n = len(fruits)
        count = 0
        for i in range(n):
            fruit = fruits[i]
            for j in range(n):
                if fruit <= baskets[j]:
                    count += 1
                    baskets[j] = 0 # 放完了剩余容量置为0
                    break

        return n - count

Q2 选出和最大的K个元素

题目描述

给你两个整数数组，nums1 和 nums2，长度均为 n，以及一个正整数 k 。

对从 0 到 n - 1 每个下标 i ，执行下述操作：

• 找出所有满足 nums1[j] 小于 nums1[i] 的下标 j 。
• 从这些下标对应的 nums2[j] 中选出 至多 k 个，并 最大化 这些值的总和作为结果。

返回一个长度为 n 的数组 answer ，其中 answer[i] 表示对应下标 i 的结果。

示例 1：

输入：nums1 = [4,2,1,5,3], nums2 = [10,20,30,40,50], k = 2

输出：[80,30,0,80,50]

解释：

• 对于 i = 0 ：满足 nums1[j] < nums1[0] 的下标为 [1, 2, 4] ，选出其中值最大的两个，结果为 50 + 30 = 80 。
• 对于 i = 1 ：满足 nums1[j] < nums1[1] 的下标为 [2] ，只能选择这个值，结果为 30 。
• 对于 i = 2 ：不存在满足 nums1[j] < nums1[2] 的下标，结果为 0 。
• 对于 i = 3 ：满足 nums1[j] < nums1[3] 的下标为 [0, 1, 2, 4] ，选出其中值最大的两个，结果为 50 + 30 = 80 。
• 对于 i = 4 ：满足 nums1[j] < nums1[4] 的下标为 [1, 2] ，选出其中值最大的两个，结果为 30 + 20 = 50 。

示例 2：

输入：nums1 = [2,2,2,2], nums2 = [3,1,2,3], k = 1

输出：[0,0,0,0]

解释：由于 nums1 中的所有元素相等，不存在满足条件 nums1[j] < nums1[i]，所有位置的结果都是 0 。

提示：

• n == nums1.length == nums2.length
• 1 <= n <= 10^5
• 1 <= nums1[i], nums2[i] <= 10^6
• 1 <= k <= n

题解-堆

import heapq

class Solution:
    def findMaxSum(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        n = len(nums1)
        ans = [0] * n
        items = sorted([(nums1[i], nums2[i], i) for i in range(n)], key=lambda x: x[0])
        
        groups = []
        current_group = []
        prev_num = None
        
        for item in items:
            num = item[0]
            if prev_num is not None and num != prev_num:
                groups.append(current_group)
                current_group = []
            current_group.append(item)
            prev_num = num
        if current_group:
            groups.append(current_group)
        
        sum_k = 0
        heap = []
        
        for group in groups:
            # 设置该组所有元素的answer为当前总和
            for num, val, idx in group:
                ans[idx] = sum_k
            
            # 处理该组的nums2值，降序排序后尝试加入堆
            vals = [item[1] for item in group]
            vals.sort(reverse=True)
            
            for val in vals:
                if len(heap) < k:
                    heapq.heappush(heap, val)
                    sum_k += val
                else:
                    if val > heap[0]:
                        sum_k += val - heapq.heappop(heap)
                        heapq.heappush(heap, val)
        
        return ans

Q3 将水果放入篮子Ⅲ\

题目描述

与Q1题面一致

提示：

• n == fruits.length == baskets.length
• 1 <= n <= 10^5
• 1 <= fruits[i], baskets[i] <= 10^9

题解-线段树

class SegmentTreeNode:
    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.left = None
        self.right = None
        self.max_val = 0

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.root = self.build(0, self.n - 1, data)
    
    def build(self, l, r, data):
        node = SegmentTreeNode(l, r)
        if l == r:
            node.max_val = data[l]
            return node
        mid = (l + r) // 2
        node.left = self.build(l, mid, data)
        node.right = self.build(mid + 1, r, data)
        node.max_val = max(node.left.max_val if node.left else 0, node.right.max_val if node.right else 0)
        return node
    
    def query_leftmost(self, target):
        return self._query_leftmost(self.root, target)
    
    def _query_leftmost(self, node, target):
        if node.max_val < target:
            return -1
        if node.l == node.r:
            return node.l if node.max_val >= target else -1
        left_pos = self._query_leftmost(node.left, target)
        if left_pos != -1:
            return left_pos
        return self._query_leftmost(node.right, target)
    
    def update(self, pos, value):
        self._update(self.root, pos, value)
    
    def _update(self, node, pos, value):
        if node.l == node.r == pos:
            node.max_val = value
            return
        mid = (node.l + node.r) // 2
        if pos <= mid:
            self._update(node.left, pos, value)
        else:
            self._update(node.right, pos, value)
        node.max_val = max(node.left.max_val if node.left else 0, node.right.max_val if node.right else 0)

class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        n = len(fruits)
        st = SegmentTree(baskets)
        count = 0
        for fruit in fruits:
            pos = st.query_leftmost(fruit)
            if pos != -1:
                count += 1
                st.update(pos, 0)
        return n - count

Q4 删除一个冲突对后最大子数组数目

题目描述

给你一个整数 n，表示一个包含从 1 到 n 按顺序排列的整数数组 nums。此外，给你一个二维数组 conflictingPairs，其中 conflictingPairs[i] = [a, b] 表示 a 和 b 形成一个冲突对。

从 conflictingPairs 中删除 恰好 一个元素。然后，计算数组 nums 中的非空子数组数量，这些子数组都不能同时包含任何剩余冲突对 [a, b] 中的 a 和 b。

返回删除 恰好 一个冲突对后可能得到的 最大 子数组数量。

子数组 是数组中一个连续的 非空 元素序列。

示例 1

输入： n = 4, conflictingPairs = [[2,3],[1,4]]

输出： 9

解释：

• 从 conflictingPairs 中删除 [2, 3]。现在，conflictingPairs = [[1, 4]]。
• 在 nums 中，存在 9 个子数组，其中 [1, 4] 不会一起出现。它们分别是 [1]，[2]，[3]，[4]，[1, 2]，[2, 3]，[3, 4]，[1, 2, 3] 和 [2, 3, 4]。
• 删除 conflictingPairs 中一个元素后，能够得到的最大子数组数量是 9。

示例 2

输入： n = 5, conflictingPairs = [[1,2],[2,5],[3,5]]

输出： 12

解释：

• 从 conflictingPairs 中删除 [1, 2]。现在，conflictingPairs = [[2, 5], [3, 5]]。
• 在 nums 中，存在 12 个子数组，其中 [2, 5] 和 [3, 5] 不会同时出现。
• 删除 conflictingPairs 中一个元素后，能够得到的最大子数组数量是 12。

提示：

• 2 <= n <= 10^5
• 1 <= conflictingPairs.length <= 2 * n
• conflictingPairs[i].length == 2
• 1 <= conflictingPairs[i][j] <= n
• conflictingPairs[i][0] != conflictingPairs[i][1]

题解

来源于灵茶山艾符

class Solution:
    def maxSubarrays(self, n: int, conflictingPairs: List[List[int]]) -> int:
        group = [[] for _ in range(n + 1)]
        for a, b in conflictingPairs:
            if a > b:
                a, b = b, a
            group[a].append(b)
        
        ans = 0
        extra = [0] * (n + 2)
        b = [n + 1, n + 1] # 最小b和次小b
        for a in range(n, 0, -1):
            b = sorted(b + group[a])[:2]
            ans += b[0] - a
            extra[b[0]] += b[1] - b[0]
        
        return ans + max(extra)