且听疯吟

leetcode biweekly conttest 84

2022-11-01

leetcode biweekly conttest 84

最近越来越没有时间参加周赛了，只能赛后来写题解了。第二题稍微有点意思，其余的题目确实没有多少亮点。最近有亮点的题目确实越来越少了。

6141. 合并相似的物品

题目

给你两个二维整数数组 items1 和 items2 ，表示两个物品集合。每个数组 items 有以下特质：

  • items[i] = [valuei, weighti] 其中 valuei 表示第 i 件物品的 价值 ，weighti 表示第 i 件物品的 重量 。
  • items 中每件物品的价值都是 唯一的 。
    请你返回一个二维数组 ret，其中 ret[i] = [valuei, weighti]， weighti 是所有价值为 valuei 物品的 重量之和 。

注意：ret 应该按价值 升序 排序后返回。

 

示例 1：

输入：items1 = [[1,1],[4,5],[3,8]], items2 = [[3,1],[1,5]]
输出：[[1,6],[3,9],[4,5]]
解释：
value = 1 的物品在 items1 中 weight = 1 ，在 items2 中 weight = 5 ，总重量为 1 + 5 = 6 。
value = 3 的物品再 items1 中 weight = 8 ，在 items2 中 weight = 1 ，总重量为 8 + 1 = 9 。
value = 4 的物品在 items1 中 weight = 5 ，总重量为 5 。
所以，我们返回 [[1,6],[3,9],[4,5]] 。

示例 2：

输入：items1 = [[1,1],[3,2],[2,3]], items2 = [[2,1],[3,2],[1,3]]
输出：[[1,4],[2,4],[3,4]]
解释：
value = 1 的物品在 items1 中 weight = 1 ，在 items2 中 weight = 3 ，总重量为 1 + 3 = 4 。
value = 2 的物品在 items1 中 weight = 3 ，在 items2 中 weight = 1 ，总重量为 3 + 1 = 4 。
value = 3 的物品在 items1 中 weight = 2 ，在 items2 中 weight = 2 ，总重量为 2 + 2 = 4 。
所以，我们返回 [[1,4],[2,4],[3,4]] 。

示例 3：

输入：items1 = [[1,3],[2,2]], items2 = [[7,1],[2,2],[1,4]]
输出：[[1,7],[2,4],[7,1]]
解释：
value = 1 的物品在 items1 中 weight = 3 ，在 items2 中 weight = 4 ，总重量为 3 + 4 = 7 。
value = 2 的物品在 items1 中 weight = 2 ，在 items2 中 weight = 2 ，总重量为 2 + 2 = 4 。
value = 7 的物品在 items2 中 weight = 1 ，总重量为 1 。
所以，我们返回 [[1,7],[2,4],[7,1]] 。

提示：

  • 1 <= items1.length, items2.length <= 1000
  • items1[i].length == items2[i].length == 2
  • 1 <= valuei, weighti <= 1000
  • items1 中每个 valuei 都是 唯一的 。
  • items2 中每个 valuei 都是 唯一的 。

地址

https://leetcode.cn/problems/merge-similar-items/

题意

直接遍历 + 哈希表

思路

  1. 简单题目，直接哈希表合并即可，或者直接遍历即可。
  2. 复杂度分析：
  • 时间复杂度：$O(n \log n)$，其中 $n$ 为数组的长度。
  • 空间复杂度：$O(n)$，其中 $n$ 为数组的长度。

代码

class Solution {
public:
    vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) {
        map<int,int> cnt;
        for (auto v : items1) {
            cnt[v[0]] += v[1];
        }
        for (auto v : items2) {
            cnt[v[0]] += v[1];
        }
        vector<vector<int>> ans;
        for (auto [w, v] : cnt) {
            vector<int> item = {w, v};
            ans.emplace_back(item);
        }
        return ans;
    }
};

6142. 统计坏数对的数目

题目

给你一个下标从 0 开始的整数数组 nums 。如果 i < j 且 j - i != nums[j] - nums[i] ，那么我们称 (i, j) 是一个 坏数对 。

请你返回 nums 中 坏数对 的总数目。

示例 1：

输入：nums = [4,1,3,3]
输出：5
解释：数对 (0, 1) 是坏数对，因为 1 - 0 != 1 - 4 。
数对 (0, 2) 是坏数对，因为 2 - 0 != 3 - 4, 2 != -1 。
数对 (0, 3) 是坏数对，因为 3 - 0 != 3 - 4, 3 != -1 。
数对 (1, 2) 是坏数对，因为 2 - 1 != 3 - 1, 1 != 2 。
数对 (2, 3) 是坏数对，因为 3 - 2 != 3 - 3, 1 != 0 。
总共有 5 个坏数对，所以我们返回 5 。

示例 2：

输入：nums = [1,2,3,4,5]
输出：0
解释：没有坏数对。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

地址

https://leetcode.cn/problems/count-number-of-bad-pairs/

题意

数学

思路

  1. 题目要求 $j - i \neq nums[j] - nums[i]$， 该不等式可以转换为 $nums[i] - i \neq nums[j] - j$，我们因此可以找到不是坏的数对的数目 $tot$，总的数对数目为 $\dfrac{n \times (n - 1)}{2}$，则可以知道坏的数对的数目为 $\dfrac{n \times (n - 1)}{2} - tot$。我们可以用哈希表统计每个元素 $x = nums[i] - i$ 的出现次数。
  2. 可能更复杂的解法还有线段树之类的解法。
  3. 复杂度分析：
  • 时间复杂度：时间复杂度为 $O(n)$，$n$ 表示数组的长度。
  • 空间复杂度：$O(n)$，$n$ 表示数组的长度。

代码

class Solution {
public:
    long long countBadPairs(vector<int>& nums) {
        long long ans = 0;
        int n = nums.size();
        unordered_map<int,int> cnt;
        for (int i = 0; i < n; i++) {
            int x = nums[i] - i;
            if (cnt.count(x)) {
                ans += cnt[x];
            }
            cnt[x]++;
        }
        return (long long)(n - 1) * n / 2 - ans;
    }
};

6174. 任务调度器 II

题目

给你一个下标从 0 开始的正整数数组 tasks ，表示需要 按顺序 完成的任务，其中 tasks[i] 表示第 i 件任务的 类型 。

同时给你一个正整数 space ，表示一个任务完成 后 ，另一个 相同 类型任务完成前需要间隔的 最少 天数。

在所有任务完成前的每一天，你都必须进行以下两种操作中的一种：

  • 完成 tasks 中的下一个任务
  • 休息一天
    请你返回完成所有任务所需的 最少 天数。

 

示例 1：

输入：tasks = [1,2,1,2,3,1], space = 3
输出：9
解释：
9 天完成所有任务的一种方法是：
第 1 天：完成任务 0 。
第 2 天：完成任务 1 。
第 3 天：休息。
第 4 天：休息。
第 5 天：完成任务 2 。
第 6 天：完成任务 3 。
第 7 天：休息。
第 8 天：完成任务 4 。
第 9 天：完成任务 5 。
可以证明无法少于 9 天完成所有任务。

示例 2：

输入：tasks = [5,8,8,5], space = 2
输出：6
解释：
6 天完成所有任务的一种方法是：
第 1 天：完成任务 0 。
第 2 天：完成任务 1 。
第 3 天：休息。
第 4 天：休息。
第 5 天：完成任务 2 。
第 6 天：完成任务 3 。
可以证明无法少于 6 天完成所有任务。

提示：

  • 1 <= tasks.length <= 105
  • 1 <= tasks[i] <= 109
  • 1 <= space <= tasks.length

地址

https://leetcode.cn/problems/task-scheduler-ii/

题意

模拟 + 哈希表

思路

  1. 感觉这个题目出的挺无聊，直接模拟即可，我们设哈希表 $prev$，其中 $prev[x]$ 表示任务 $x$ 最后一次发生的时间。我们遍历每个任务 $task[i]$，有以下两种情况需要处理，设上一个任务的完成时间为 $now$:
  • 如果当前的任务 $task[i]$ 之前没有出现过，则此时当前任务的完成时间肯定为 $now + 1$，且此时 $prev[task[i]] = now + 1$，且此时更新 $now = now + 1$；
  • 如果当前的任务 $task[i]$ 之前出现过，由于相同的任务的间隔必须大于 $space$, 因此当前任务的完成时间要么是 $now + 1$ 和 $prev[task[i]] + space + 1$ 之间的较大值，则此时 $now = \max(now + 1,prev[task[i]] + space + 1) $, 更新 $prev[task[i]] = now$；
  1. 复杂度分析：
  • 时间复杂度：时间复杂度为 $O(n)$，其中 $n$ 表示数组的长度。
  • 空间复杂度：空间复杂度为 $O(n)$，其中 $n$ 表示数组的长度。

代码

class Solution {
public:
    long long taskSchedulerII(vector<int>& tasks, int space) {
        unordered_map<int,long long> prev;
        int n = tasks.size();
        long long now = 0;
        for(int i = 0; i < n; i++) {
            if (prev.count(tasks[i])) {
                now = max(now, prev[tasks[i]] + space);
            } 
            now++;
            prev[tasks[i]] = now;
        }
        return now;
    }
};

6144. 将数组排序的最少替换次数

题目

给你一个下表从 0 开始的整数数组 nums 。每次操作中，你可以将数组中任何一个元素替换为 任意两个 和为该元素的数字。
比方说，nums = [5,6,7] 。一次操作中，我们可以将 nums[1] 替换成 2 和 4 ，将 nums 转变成 [5,2,4,7] 。
请你执行上述操作，将数组变成元素按 非递减 顺序排列的数组，并返回所需的最少操作次数。

 

示例 1：

输入：nums = [3,9,3]
输出：2
解释：以下是将数组变成非递减顺序的步骤：
- [3,9,3] ，将9 变成 3 和 6 ，得到数组 [3,3,6,3] 
- [3,3,6,3] ，将 6 变成 3 和 3 ，得到数组 [3,3,3,3,3] 
总共需要 2 步将数组变成非递减有序，所以我们返回 2 。

示例 2：

输入：nums = [1,2,3,4,5]
输出：0
解释：数组已经是非递减顺序，所以我们返回 0 。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

地址

https://leetcode.cn/problems/minimum-replacements-to-sort-the-array/

题意

贪心算法

思路

  1. 首先我们为了减少替换次数，此时我们应当保证最后面的数尽可能的大，才能保证前面的数尽可能的不被替换。因此我们从后往前遍历数组，对于第 $i$ 个元素，如果出现 $nums[i] > nums[i + 1]$，此时我们应该进行拆分，但在拆分时需要的技巧是需要满足两个条件:
  • 拆分的出数的序列中的最大值一定要满足小于等于 $nums[i+1]$;
  • 拆分的出数的序列中的最小值一定要尽可能的大;

如何满足以上条件的拆分法，所有需要切分的最少次数 $k = \dfrac{nums[i]}{nums[i+1]}$。此时可以知道切分后最小的数为 $x = \lfloor\dfrac{nums[i]}{k + 1} \rfloor$。

  1. 复杂度分析：
  • 时间复杂度：$O(n)$，$n$ 表示数组的长度。
  • 空间复杂度：$O(1)$。

代码

class Solution {
public:
    long long minimumReplacement(vector<int>& nums) {
        int n = nums.size();
        long long ans = 0;
        int mx = INT_MAX;
        for (int i = n - 1; i >= 0; i--) {
            if (nums[i] > mx) {
                int div = (nums[i] - 1) / mx;
                ans += div;
                mx = nums[i] / (div + 1);
            } else {
                mx = nums[i];
            }
        }
        return ans;
    }
};

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

Tags: 力扣周赛
← leetcode conttest 305 leetcode conttest 304 →

扫描二维码，分享此文章