Decade
Leetcode 331场周赛
Zhongjun Qiu 元婴开发者
  2025-02-05 14:58:56   2025-04-29 21:27:59    2.3k Words  9 Mins  

Q1 从数量最多的堆取走礼物 [Easy] 题解

Q2 6347. 统计范围内的元音字符串数 - 力扣（Leetcode） [Medium] 题解

Q3 6346. 打家劫舍 IV - 力扣（LeetCode） [Medium] 题解

Q4 6345. 重排水果 - 力扣（LeetCode） [Hard] 题解

Q1

从数量最多的堆取走礼物

给你一个整数数组 gifts ，表示各堆礼物的数量。每一秒，你需要执行以下操作：

  • 选择礼物数量最多的那一堆。
  • 如果不止一堆都符合礼物数量最多，从中选择任一堆即可。
  • 选中的那一堆留下平方根数量的礼物（向下取整），取走其他的礼物。

返回在 k 秒后剩下的礼物数量。

示例 1：

输入：gifts = [25,64,9,4,100], k = 4
输出：29
解释： 
按下述方式取走礼物：
- 在第一秒，选中最后一堆，剩下 10 个礼物。
- 接着第二秒选中第二堆礼物，剩下 8 个礼物。
- 然后选中第一堆礼物，剩下 5 个礼物。
- 最后，再次选中最后一堆礼物，剩下 3 个礼物。
最后剩下的礼物数量分别是 [5,8,9,4,3] ，所以，剩下礼物的总数量是 29 。

示例 2：

输入：gifts = [1,1,1,1], k = 4
输出：4
解释：
在本例中，不管选中哪一堆礼物，都必须剩下 1 个礼物。 
也就是说，你无法获取任一堆中的礼物。 
所以，剩下礼物的总数量是 4 。

提示：

  • 1 <= gifts.length <= 10^3
  • 1 <= gifts[i] <= 10^9
  • 1 <= k <= 10^3

思路

​ 搞个堆模拟即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public long pickGifts(int[] gifts, int k) {
        long ans = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>((x, y)->y-x);
        for (int i : gifts) pq.add(i);
        for (int i = 0;i < k;i++){
            int x = pq.poll();
            int ne = (int)Math.floor(Math.sqrt(x));
            pq.add(ne);
        }
        while (!pq.isEmpty()) ans += pq.poll();
        return ans;
    }
}

复杂度分析

  • 时间复杂度：O(klog n)
  • 空间复杂度：O(n)

Q2

6347. 统计范围内的元音字符串数 - 力扣（Leetcode）

给你一个下标从 0 开始的字符串数组 words 以及一个二维整数数组 queries 。

每个查询 queries[i] = [li, ri] 会要求我们统计在 words 中下标在 li 到 ri 范围内（包含 这两个值）并且以元音开头和结尾的字符串的数目。

返回一个整数数组，其中数组的第 i 个元素对应第 i 个查询的答案。

注意：元音字母是 'a'、'e'、'i'、'o' 和 'u' 。

示例 1：

1
2
3
4
5
6
7
输入：words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]
输出：[2,3,0]
解释：以元音开头和结尾的字符串是 "aba"、"ece"、"aa" 和 "e" 。
查询 [0,2] 结果为 2（字符串 "aba" 和 "ece"）。
查询 [1,4] 结果为 3（字符串 "ece"、"aa"、"e"）。
查询 [1,1] 结果为 0 。
返回结果 [2,3,0] 。

示例 2：

1
2
3
输入：words = ["a","e","i"], queries = [[0,2],[0,1],[2,2]]
输出：[3,2,1]
解释：每个字符串都满足这一条件，所以返回 [3,2,1] 。

提示：

  • 1 <= words.length <= 10^5
  • 1 <= words[i].length <= 40
  • words[i] 仅由小写英文字母组成
  • sum(words[i].length) <= 3 * 10^5
  • 1 <= queries.length <= 10^5
  • 0 <= queries[j][0] <= queries[j][1] < words.length

思路

n, m数量级很容易让我们想到 O(n) 预处理和 O(1) 查询。因为题目中需要求一段区间里的符合条件数量，所以想到用前缀和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def vowelStrings(self, w: List[str], q: List[List[int]]) -> List[int]:
        n, m = len(w), len(q)
        ans = []
        cnt = [0]*(n+1)
        hs = set(['a', 'e', 'i', 'o', 'u'])
        for i in range(1, n+1):
            cur = w[i-1]
            cnt[i] = cnt[i-1]
            if cur[0] in hs and cur[len(cur)-1] in hs:
                cnt[i] += 1
        for i in range(m):
            x, y = q[i][0], q[i][1]
            ans.append(cnt[y+1]-cnt[x])
        return ans

复杂度分析

  • 时间复杂度：O(n + m)
  • 空间复杂度：O(n)

Q3

6346. 打家劫舍 IV - 力扣（LeetCode）

沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。

给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。另给你一个整数数组 k ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。返回小偷的 最小 窃取能力。

示例 1：

1
2
3
4
5
6
7
8
输入：nums = [2,3,5,9], k = 2
输出：5
解释：
小偷窃取至少 2 间房屋，共有 3 种方式：
- 窃取下标 0 和 2 处的房屋，窃取能力为 max(nums[0], nums[2]) = 5 。
- 窃取下标 0 和 3 处的房屋，窃取能力为 max(nums[0], nums[3]) = 9 。
- 窃取下标 1 和 3 处的房屋，窃取能力为 max(nums[1], nums[3]) = 9 。
因此，返回 min(5, 9, 9) = 5 。

示例 2：

1
2
3
输入：nums = [2,7,9,3,1], k = 2
输出：2
解释：共有 7 种窃取方式。窃取能力最小的情况所对应的方式是窃取下标 0 和 4 处的房屋。返回 max(nums[0], nums[4]) = 2 。

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= (nums.length + 1)/2

思路

最小的最大偷窃金额，完美符合最大化最小值和最小化最大值问题，一眼二分。

再来思考给定一个最大偷窃金额 t，如何判断是否能偷 k 个。

这里用贪心，从左往右遍历，如果金额小于 t, 在判断前一个有没有偷：如果没偷，答案加一；如果偷了，那这次就不偷。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minCapability(int[] nums, int k) {
        int n = nums.length;
        int l = 1, r = (int)1e9;
        while (l <= r){
            int m = l+r >> 1;
            if (ck(nums, m, k)) r = m-1;
            else l = m+1;
        }return l;
    }
    public boolean ck(int[] nums, int t, int k){
        int pre = -2, s = 0;
        for (int i = 0;i < nums.length;i++){
            if (nums[i] <= t){
                if (i-pre >= 2){
                    s++;
                    pre = i;
                }
            }
        }return s >= k;
    }
}

复杂度分析

  • 时间复杂度：O(nlog m), m = max (nums[i])
  • 空间复杂度：O(1)

Tips

最大化最小值和最小化最大值一般都是二分的代名词。具体主要思考两个问题：

  • 二分什么？（直接二分答案、二分第一个大于 a[i] 的数···）
  • check() 函数怎么实现？

Q4

6345. 重排水果 - 力扣（LeetCode）

你有两个果篮，每个果篮中有 n 个水果。给你两个下标从 0 开始的整数数组 basket1 和 basket2 ，用以表示两个果篮中每个水果的成本。

你希望两个果篮相等。为此，可以根据需要多次执行下述操作：

  • 选中两个下标 i 和 j ，并交换 basket1 中的第 i 个水果和 basket2 中的第 j 个水果。
  • 交换的成本是 min(basket1i,basket2j) 。

根据果篮中水果的成本进行排序，如果排序后结果完全相同，则认为两个果篮相等。

返回使两个果篮相等的最小交换成本，如果无法使两个果篮相等，则返回 -1 。

示例 1：

1
2
3
输入：basket1 = [4,2,2,2], basket2 = [1,4,1,2]
输出：1
解释：交换 basket1 中下标为 1 的水果和 basket2 中下标为 0 的水果，交换的成本为 1 。此时，basket1 = [4,1,2,2] 且 basket2 = [2,4,1,2] 。重排两个数组，发现二者相等。

示例 2：

1
2
3
输入：basket1 = [2,3,4,1], basket2 = [3,2,5,1]
输出：-1
解释：可以证明无法使两个果篮相等。

提示：

  • basket1.length == bakste2.length
  • 1 <= basket1.length <= 1^05
  • 1 <= basket1i,basket2i <= 10^9

思路

首先统计每种水果的总数，如果某种水果出现奇数次答案为 False。

其次统计两个篮子中多出的水果 X, Y ，即需要交换掉的水果。对于每个水果，有两种删除方式：

  • 用 x 和 y 里的最小值与另一个数组里的最大值进行配对。这样经过一次操作就能删除 x 和 y 里各一个元素。
  • 借助所有水果里的最小值进行配对。假设最小值为 k, 则将第一个篮子中 k1与 k 交换，消耗 k ；再将第二个篮子中 k2 与 k 交换， 消耗 k，且 k 这个水果重新回到原来的篮子。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minCost(self, b1: List[int], b2: List[int]) -> int:
        d1,d2 = defaultdict(int),defaultdict(int)
        d = defaultdict(int)
        for i in b1: d1[i] += 1
        for i in b2: d2[i] += 1
        for i in b1+b2: d[i] += 1
        for i in d:
            if d[i]%2 == 1: return -1
        a = []
        for i in d1:
            if d1[i]>d[i]//2: a.extend([i]*(d1[i]-d[i]//2))
        for i in d2:
            if d2[i]>d[i]//2: a.extend([i]*(d2[i]-d[i]//2))
        a.sort()
        ans, minv = 0, min(i for i in d)
        for i in range(len(a)//2):
            ans += min(2*minv, a[i])
        return ans

复杂度分析

  • 时间复杂度：O(nlog n)
  • 空间复杂度：O(n)
Leetcode 331场周赛
2025/02/05/Leetcode-331场周赛/
Author
Zhongjun Qiu
Published
2025-02-05 14:58
License
 REWARD AUTHOR
 Comments
Comment plugin failed to load
Loading comment plugin
  1. Q1
    1. 思路
    2. 代码
    3. 复杂度分析
  2. Q2
    1. 思路
    2. 代码
    3. 复杂度分析
  3. Q3
    1. 思路
    2. 代码
    3. 复杂度分析
    4. Tips
  4. Q4
    1. 思路
    2. 代码
    3. 复杂度分析
  1. Q1
    1. 思路
    2. 代码
    3. 复杂度分析
  2. Q2
    1. 思路
    2. 代码
    3. 复杂度分析
  3. Q3
    1. 思路
    2. 代码
    3. 复杂度分析
    4. Tips
  4. Q4
    1. 思路
    2. 代码
    3. 复杂度分析