image.png
脑子不清醒的一场

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 都是 唯一的 。

思路：
可以用双指针来做

  1. class Solution {
  2.     public List<List<Integer>> mergeSimilarItems(int[][] a, int[][] b) {
  3.         int i = 0, j = 0;
  4.         int n = a.length, m = b.length;
  5.         Arrays.sort(a, (o1, o2) -> (o1[0] - o2[0]));
  6.         Arrays.sort(b, (o1, o2) -> (o1[0] - o2[0]));
  7.         List<List<Integer>> list = new ArrayList<>();
  8.         while (i < n && j < m) {
  9.             List<Integer> t = new ArrayList<>();
  10.             if (a[i][0] != b[j][0]) {
  11.                 if (a[i][0] < b[j][0]) {
  12.                     t.add(a[i][0]);
  13.                     t.add(a[i][1]);
  14.                     i++;
  15.                 } else {
  16.                     t.add(b[j][0]);
  17.                     t.add(b[j][1]);
  18.                     j++;
  19.                 }
  20.             } else {
  21.                 t.add(a[i][0]);
  22.                 t.add(a[i][1] + b[j][1]);
  23.                 i++;
  24.                 j++;
  25.             }
  26.             list.add(t);
  27.         }
  28.         while (i < n) {
  29.             List<Integer> t = new ArrayList<>();
  30.             t.add(a[i][0]);
  31.             t.add(a[i][1]);
  32.             i++;
  33.             list.add(t);
  34.         }
  35.         while (j < m) {
  36.             List<Integer> t = new ArrayList<>();
  37.             t.add(b[j][0]);
  38.             t.add(b[j][1]);
  39.             j++;
  40.             list.add(t);
  41.         }
  42.         return list;
  43.     }
  44. }
  1. 太难调了，还是用哈希表简单
  1. class Solution {
  2.     public List<List<Integer>> mergeSimilarItems(int[][] a, int[][] b) {
  3.         Map<Integer, Integer> map = new HashMap<>();
  4.         for (int[] p : a) {
  5.             map.merge(p[0], p[1], Integer::sum);
  6.         }
  7.         for (int[] p : b) {
  8.             map.merge(p[0], p[1], Integer::sum);
  9.         }
  10.         List<List<Integer>> res = new ArrayList<>();
  11.         for (int x : map.keySet()) {
  12.             int y = map.get(x);
  13.             List<Integer> t = new ArrayList<>();
  14.             t.add(x);
  15.             t.add(y);
  16.             res.add(t);
  17.         }
  18.         Collections.sort(res, (o1, o2) -> (o1.get(0) - o2.get(0)));
  19.         return res;
  20.     }
  21. }

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

思路：
变换一下式子得j - nums[j] == i - nums[i]
即统计所有x - nums[x]相同的数对的个数

  1. class Solution {
  2.     public long countBadPairs(int[] nums) {
  3.         Map<Integer, Integer> map = new HashMap<>();
  4.         long c = 0;
  5.         for (int i = 0; i < nums.length; i++) {
  6.             int x = i - nums[i];
  7.             c += i - map.getOrDefault(x, 0);
  8.             map.merge(x, 1, Integer::sum);
  9.         }
  10.         return c;
  11.     }
  12. }

6174. 任务调度器 II

显示英文描述
我的提交返回竞赛

  • 通过的用户数1955
  • 尝试过的用户数2467
  • 用户总通过次数2014
  • 用户总提交次数5120
  • 题目难度Medium

给你一个下标从 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

思路：
贪心

  1. class Solution {
  2.     public long taskSchedulerII(int[] tasks, int s) {
  3.         Map<Integer, Long> map = new HashMap<>();
  4.         long cur = 0;
  5.         for (int i = 0; i < tasks.length; i++) {
  6.             long pre = map.getOrDefault(tasks[i], -1000000L);
  7.             cur = Math.max(cur + 1, pre + s + 1);
  8.             map.put(tasks[i], cur);
  9.         }
  10.         return cur;
  11.     }
  12. }

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

显示英文描述
我的提交返回竞赛

  • 通过的用户数840
  • 尝试过的用户数1467
  • 用户总通过次数934
  • 用户总提交次数3650
  • 题目难度Hard

给你一个下表从 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

思路：
贪心 + 二分

  1. class Solution {
  2.     public long minimumReplacement(int[] nums) {
  3.         int n = nums.length;
  4.         long res = 0;
  5.         int pre = nums[n - 1];
  6.         for (int i = n - 2; i >= 0; i--) {
  7.             if (nums[i] <= pre) {
  8.                 pre = nums[i];
  9.                 continue;
  10.             }
  12.             int l = 1, r = nums[i];
  13.             while (l < r) {
  14.                 int mid = l + r >> 1;
  15.                 if (1.0 * nums[i] / mid <= pre)
  16.                     r = mid;
  17.                 else
  18.                     l = mid + 1;
  19.             }
  20.             res += l - 1;
  21.             pre = nums[i] / l;
  22.         }
  23.         return res;
  24.     }
  25. }