且听疯吟

leetcode weekly contest 331

2023-02-09

leetcode weekly contest 331

后面两题还算是不错的题目。

2558. 从数量最多的堆取走礼物

给你一个整数数组 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 <= 103
  • 1 <= gifts[i] <= 109
  • 1 <= k <= 103

地址

https://leetcode.cn/contest/weekly-contest-330/problems/count-distinct-numbers-on-board/

题意

堆

思路

  1. 简单题目直接模拟即可，每次从堆中取出最大的元素 $x$，然后将 $\sqrt{x}$ 放入队列，重复 $k$ 次后，我们求队列中所有元素的和；
  2. 复杂度分析：
  • 时间复杂度：$O(n + k \log n)$，其中 $n$ 为数组的长度，$k$ 为取出的次数。
  • 空间复杂度：$O(n)$。

代码

class Solution {
public:
    long long pickGifts(vector<int>& gifts, int k) {
        priority_queue<int, vector<int>, less<int>> pq;
        for (auto v : gifts) {
            pq.emplace(v);
        }
        long long res = 0;
        for (int i = 0; i < k; i++) {
            int x = pq.top();
            pq.pop();
            pq.emplace(sqrt(x));
        }
        while (!pq.empty()) {
            res += pq.top();
            pq.pop();
        }
        return res;
    }
};

2559. 统计范围内的元音字符串数

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

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

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

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

示例 1：

输入：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：

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

提示：

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

地址

https://leetcode.cn/contest/biweekly-contest-96/problems/minimum-operations-to-make-array-equal-ii/

题意

前缀和

思路

  1. 我们直接统计前 $i$ 个字符中的元音字符统计次数的前缀和，此时查询时 $[l,r]$ 时，我们直接利用前缀和 $presum[r] - presum[l-1]$ 即可求得区间 $[l,r]$ 内的元音字母统计次数。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 为数组的长度。
  • 空间复杂度：$O(1)$。

代码

class Solution {
public:
    vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
        int n = words.size();
        vector<int> arr(n);
        unordered_set<char> cnt({'a', 'e', 'i', 'o', 'u'});
        for (int i = 0; i < n; i++) {
            if (cnt.count(words[i][0]) && cnt.count(words[i].back())) {
                arr[i] = 1;
            }
        }
        vector<int> presum(n + 1);
        for (int i = 0; i < n; i++) {
            presum[i + 1] = presum[i] + arr[i];
        }
        vector<int> res;
        for (auto v : queries) {
            int l = v[0], r = v[1];
            res.emplace_back(presum[r + 1] - presum[l]);
        }
        return res;
    }
};

2560. 打家劫舍 IV

沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。

由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。

小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。

给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。

另给你一个整数数组 k ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。

返回小偷的 最小 窃取能力。

示例 1：

输入：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：

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

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= (nums.length + 1)/2

地址

https://leetcode.cn/contest/weekly-contest-331/problems/house-robber-iv/

题意

二分查找、贪心

思路

  1. 题目本身比较简单，根据题目的提示即可知道本题需要用到二分查找 $1 \le nums[i] \le 10^9$。此时我们二分枚举可能的最小值 $x$。我们如何检测 $x$ 合法？由于题目只要求不能抢劫相邻的房屋，此时我们只需要依次从左向右取数据即可，若要保证每次取时间隔大于 $1$，我们应当尽可能的取左侧的数据，只需要保证每次取时相邻的数据间隔大于 $1$ 即可。
  2. 复杂度分析
  • 时间复杂度：时间复杂度为 $O(n \log U)$，$n$ 表示数组的长度，$U$ 表示数组中最大的数字。
  • 空间复杂度：时间复杂度为 $O(1)$。

代码

class Solution {
public:
    int minCapability(vector<int>& nums, int k) {
        int n = nums.size();
        int l = 0, r = *max_element(nums.begin(), nums.end());
        int res = 0;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            int pre = -2, tot = 0;
            for (int i = 0; i < n; i++) {
                if (nums[i] <= mid && i - pre > 1) {
                    pre = i;
                    tot++;
                }
            }
            if (tot >= k) {
                res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return res;
    }
};

2561. 重排水果

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

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

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

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

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

示例 1：

输入：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：

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

提示：

  • basket1.length == bakste2.length
  • 1 <= basket1.length <= 105
  • 1 <= basket1i,basket2i <= 109

地址

https://leetcode.cn/contest/weekly-contest-331/problems/rearranging-fruits/

题意

思维题目 + 贪心

思路

  1. 本身替换的思路确实难了一些，首先我们自然而然的想到，将两个数组中相同的元素全部剔除掉，相同的元素则不用交换，我们只交换不同的元素。我们假设将 $basket1$ 中相同的元素剔除掉后剩余的元素组成的数组为 $arr1$，将 $basket2$ 中相同的元素剔除掉后剩余的元素组成的数组为 $arr2$，此时我们知道一定包含下面的处理:
  • 两个数组的长度一定相等，如果不相等无论如何都无法完成交换相等；
  • 两个数组的长度一定都是偶数，且其中每个元素出现的次数都为偶数次，为什么每个元素出现的次数都为偶数次，因为我们假设交换了 $(x,y), x \neq y$，此时 $arr1$ 中多了一个 $y$ 少了一个 $x$，此时 $arr2$ 中多了一个 $x$ 少了一个 $y$，此时交换之前的 $arr1$ 一定至少含有 $2$ 个 $x$，交换之前的 $arr2$ 一定至少含有 $2$ 个 $y$，否则两个数组仍然不相等，交换则没有任何意义；
  • 假设 $arr1$ 的数组长度为 $m$，则我们此时最多只需要交换 $\frac{m}{2}$ 次即可，每次交换时我们尽量取两个数组中剩余元素较小的值进行交换；
  • 假设 $a$ 为两个数组中都已经共有的元素，此时如果要交换 $(x,y)$，我们可以将 $arr1$ 中的 $x$ 与 $arr2$ 中的 $a$ 交换，将 $arr1$ 中的 $a$ 与 $arr2$ 中的 $y$ 交换，这样交换的代价则为 $2a$；
  • 综上我们每次交换时要么选择二者已经拥有的共同元素的最小值的元素 $minVal$ 交换两次，代价为 $2 * minVal$；要么选择二者非共同元素的最小值进行交换，交换的代价为 $\min(arr1, arr2)$；
  • 每次交换完成后 $(x,y)$ 则为两个数组共同拥有的元素，此时我们可以同时更新 $minVal$；
  1. 复杂度分析：
  • 时间复杂度：$O(n \log n)$，其中 $n$ 为数组的长度。
  • 空间复杂度：$O(n)$。

代码

class Solution {
public:
    bool check(vector<int> &arr) {
        if (arr.size() % 2) {
            return false;
        }
        for (int i = 0; i < arr.size(); i += 2) {
            if (arr[i] != arr[i + 1]) {
                return false;
            }
        }
        return true;
    }

    long long minCost(vector<int>& basket1, vector<int>& basket2) {
        sort(basket1.begin(), basket1.end());
        sort(basket2.begin(), basket2.end());
        int n = basket1.size();
        vector<int> arr1, arr2;
        vector<int> arr;
        int i = 0, j = 0;
        while(i < n && j < n) {
            if (basket1[i] == basket2[j]) {
                arr.emplace_back(basket1[i]);
                i++, j++;
            } else if (basket1[i] < basket2[j]) {
                arr1.emplace_back(basket1[i]);
                i++;
            } else {
                arr2.emplace_back(basket2[j]);
                j++;
            }
        }
        while (i < n) {
            arr1.emplace_back(basket1[i++]);
        }
         while (j < n) {
            arr2.emplace_back(basket2[j++]);
        }
        if (arr1.size() != arr2.size()) {
            return -1;
        }
        if (!check(arr1) || !check(arr2)) {
            return -1;
        }
        long long ans = 0;
        int minVal = max(basket1[n - 1], basket2[n - 1]);
        if (arr.size() > 0) {
            minVal = min(arr[0], minVal);
        }
        int l1 = 0, l2 = 0;
        int m = arr1.size() / 2;
        for (int i = 0; i < m; i++) {
            if (arr1[l1] < arr2[l2]) {
                if (2 * minVal < arr1[l1]) {
                    ans += 2 * minVal;
                } else {
                    ans += arr1[l1];
                }
                minVal = min(minVal, arr1[l1]);
                l1 += 2;
            } else {
                if (2 * minVal < arr2[l2]) {
                    ans += 2 * minVal;
                } else {
                    ans += arr2[l2];
                }
                minVal = min(minVal, arr2[l2]);
                l2 += 2;
            }
        }
        return ans;
    }
};

欢迎关注和打赏，感谢支持！

Tags: 力扣周赛 题解
← leetcode biweekly contest 97 leetcode weekly contest 332 →

扫描二维码，分享此文章