LeetCode笔记：Weekly Contest 331

• LeetCode笔记：Weekly Contest 331
  • 1. 题目一
    • 1. 解题思路
    • 2. 代码实现
  • 2. 题目二
    • 1. 解题思路
    • 2. 代码实现
  • 3. 题目三
    • 1. 解题思路
    • 2. 代码实现
  • 4. 题目四
    • 1. 解题思路
    • 2. 代码实现

• 比赛链接：https://leetcode.com/contest/weekly-contest-331

1. 题目一

给出题目一的试题链接如下：

• 2558. Take Gifts From the Richest Pile

1. 解题思路

这一题就是按照题意操作一下就行了，我们预先对原数组进行排序，然后不断取最大元素开根号即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def pickGifts(self, gifts: List[int], k: int) -> int:
        gifts = sorted(gifts)
        for _ in range(k):
            g = gifts.pop()
            bisect.insort(gifts, int(math.sqrt(g)))
        return sum(gifts)
           

提交代码评测得到：耗时47ms，占用内存14MB。

2. 题目二

给出题目二的试题链接如下：

• 2559. Count Vowel Strings in Ranges

1. 解题思路

这一题我的思路就是首先找到那些符合条件的字符串，然后用一个累积数组即可快速地求得某一范围内得符合条件的字符串的个数了。

2. 代码实现

给出python代码实现如下：

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        def count_vowel(w):
            return 1 if w[0] in "aeiou" and w[-1] in "aeiou" else 0
        
        cnt = [count_vowel(w) for w in words]
        cnt = [0] + list(accumulate(cnt))
        res = [cnt[r+1] - cnt[l] for l, r in queries]
        return res
           

提交代码评测得到：耗时637ms，占用内存55MB。

3. 题目三

给出题目三的试题链接如下：

• 2560. House Robber IV

1. 解题思路

这一题我最开始的思路是通过动态规划来进行处理，但是遇到了超时问题。后来调整思路变成二分法就可以直接通过了，只要想到了，倒是也没啥难度可言。

2. 代码实现

给出python代码实现如下：

class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        n = len(nums)
        
        def is_possible(m):
            i, cnt = 0, 0
            while i < n and cnt < k:
                if nums[i] <= m:
                    cnt += 1
                    i += 2
                else:
                    i += 1
            return cnt >= k
        
        i, j = 0, max(nums)
        while j-i > 1:
            t = (i+j) // 2
            if is_possible(t):
                j = t
            else:
                i = t
        return j
           

提交代码评测得到：耗时1378ms，占用内存24.9MB。

4. 题目四

给出题目四的试题链接如下：

• 2561. Rearranging Fruits

1. 解题思路

这一题思路还是挺清晰的，就是统计一下两个数组之间的item的gap，如果某一个元素两边的差值为奇数，那么无论如何也无法两边配平。

而对于可以配平的情况，我们就可以快速地获取两个数组各自需要移动的元素，剩下的问题就是如何计算交换所需的最小cost。

这里其实有两种情况需要讨论，第一种是直接对两个元素进行交换，第二种是通过另一个很小的元素作为媒介，用两次交换来配平两个元素，我们需要考察这两者之间的最小值作为两个元素交换所需的最小cost。

然后，我们只需要求和所有的cost即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def minCost(self, basket1: List[int], basket2: List[int]) -> int:
        cnt = defaultdict(int)
        for u, v in zip(basket1, basket2):
            cnt[u] += 1
            cnt[v] -= 1
        move_in, move_out = [], []
        for k, v in cnt.items():
            if v % 2 == 1:
                return -1
            elif v > 0:
                move_out.extend([k] * (v // 2))
            else:
                move_in.extend([k] * (-v // 2))
        if move_in == []:
            return 0
        _min = min(cnt.keys())
        move_in = sorted(move_in)
        move_out = sorted(move_out, reverse=True)
        return sum(min(2*_min, min(x, y)) for x, y in zip(move_in, move_out))
           

提交代码评测得到：耗时813ms，占用内存36.9MB。