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

一、本周周赛总结

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

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

链接: 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. 统计范围内的元音字符串数

链接: 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

链接: 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. 重排水果

链接: 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     

六、参考链接