[LeetCode周赛复盘] 第 331 场周赛20230205

一、本周周赛总结

T1 堆+二分。 T2 前缀和/树状数组,区间查询。 T3 二分答案。 T4 计数+排序+枚举答案。

二、 [Easy] 6348. 从数量最多的堆取走礼物

链接:

1. 题目描述

2. 思路分析

首先每次要取最大，还得放回，立刻想到用堆，直接模拟。 后来由于开方怕浮点型出问题，补了个开方向下取整的二分写法。 由于py是最小堆，因此元素要取反。

注意 32位整数开方整数部分是准确的;64位就不准了。记住这个结论。

3. 代码实现

def kf(x):  # 二分开方向下取整
    def ok(p):
        return p*p > x
    return bisect_left(range(x+1),True,key=ok)-1

class Solution:
    def pickGifts(self, gifts: List[int], k: int) -> int:
        h = []
        for v in gifts:
            heappush(h, -v)
        ans = sum(gifts)
        while k and h:
            v = -heappop(h)
            l = kf(v)
            ans -= v-l
            heappush(h, -l)
            k -= 1
        return ans

三、[Medium] 6347. 统计范围内的元音字符串数

链接:

1. 题目描述

2. 思路分析

前缀和区间查询。 把字符串预处理之后就变成01，区间查询1的个数即可。 由于不用更新，直接前缀和即可。 比赛时我写了树状数组，蠢。

3. 代码实现

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        n = len(words)
        a = [int(v[0] in aeiou and v[-1] in aeiou) for v in words]
        p = [0] + list(accumulate(a))
        return [p[r+1] - p[l] for l, r in queries]

四、[Medium] 6346. 打家劫舍 IV

链接:

1. 题目描述

2. 思路分析

二分答案。 设能力为x，当x变大时，能偷的房子也变大。因此具有单调性。 只要找到最小的能偷到k的x即可。 check函数内部可以贪心，因为当i和i+1都可以取时，取i一定优于取i+1.

3. 代码实现

class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        n = len(nums)

        def ok(x):
            cnt = 0
            pre = -2
            for i in range(n):
                if i > pre + 1 and nums[i] <= x:
                    cnt += 1
                    pre = i
            return cnt >= k
        return bisect_left(range(0, max(nums) + 1), True,lo=1, key=ok)

五、[Hard] 6345. 重排水果

链接:

1. 题目描述

2. 思路分析

比赛时写了双指针，其实没必要。 直接用一个数组排序，取前一半即可。 注意，可以用最小的数当跳板，交换两次。 另外计数器也可以直接用同一个。

分别计数b1比b2多的数，b2比b1多的数。要换过去的数是cnt//2，因此cnt是奇数就无法满足。 记差分别是a和b，一定是a中小的交换b中大的，即反着匹配交换。

3. 代码实现

class Solution:
    def minCost(self, b1: List[int], b2: List[int]) -> int:
        n = len(b1)
        a = []
        cnt = Counter()
        for x,y in zip(b1,b2):
            cnt[x] += 1
            cnt[y] -= 1
        for k,v in cnt.items():
            if v & 1:
                return -1 
            a.extend([k]*abs(v//2))
        a.sort()
        mn = min(b1+b2)
        ans = 0
        for v in a[:len(a)//2]:
            ans += min(v,2*mn)
        return ans