image.png
手速场！

6120. 数组能形成多少数对

给你一个下标从 0 开始的整数数组 nums 。在一步操作中，你可以执行以下步骤：

  • 从 nums 选出 两个 相等的 整数
  • 从 nums 中移除这两个整数，形成一个 数对

请你在 nums 上多次执行此操作直到无法继续执行。
返回一个下标从 0 开始、长度为 2 的整数数组 answer 作为答案，其中 _answer[0] _是形成的数对数目，answer[1] 是对 nums 尽可能执行上述操作后剩下的整数数目。

示例 1：
输入：nums = [1,3,2,1,3,2,2] 输出：[3,1] 解释： nums[0] 和 nums[3] 形成一个数对，并从 nums 中移除，nums = [3,2,3,2,2] 。 nums[0] 和 nums[2] 形成一个数对，并从 nums 中移除，nums = [2,2,2] 。 nums[0] 和 nums[1] 形成一个数对，并从 nums 中移除，nums = [2] 。 无法形成更多数对。总共形成 3 个数对，nums 中剩下 1 个数字。
示例 2：
输入：nums = [1,1] 输出：[1,0] 解释：nums[0] 和 nums[1] 形成一个数对，并从 nums 中移除，nums = [] 。 无法形成更多数对。总共形成 1 个数对，nums 中剩下 0 个数字。
示例 3：
输入：nums = [0] 输出：[0,1] 解释：无法形成数对，nums 中剩下 1 个数字。

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

思路：
排序 + 模拟
时间复杂度：O(nlogn)

  1. class Solution {
  2.     public int[] numberOfPairs(int[] nums) {
  3.         int n = nums.length, c = 0;
  4.         Arrays.sort(nums);
  5.         for (int i = 0; i < n; i++) {
  6.             if (i + 1 < n && nums[i] == nums[i + 1]) {
  7.                 c++;
  8.                 i++;
  9.             }
  10.         }
  11.         return new int[]{c, n - c * 2};
  12.     }
  13. }

6164. 数位和相等数对的最大和

给你一个下标从 0 开始的数组 nums ，数组中的元素都是 正 整数。请你选出两个下标 i 和 j（i != j），且 nums[i] 的数位和 与 nums[j] 的数位和相等。
请你找出所有满足条件的下标 i 和 j ，找出并返回 _nums[i] + nums[j] 可以得到的 最大值 。_

示例 1：
输入：nums = [18,43,36,13,7] 输出：54 解释：满足条件的数对 (i, j) 为： - (0, 2) ，两个数字的数位和都是 9 ，相加得到 18 + 36 = 54 。 - (1, 4) ，两个数字的数位和都是 7 ，相加得到 43 + 7 = 50 。 所以可以获得的最大和是 54 。
示例 2：
输入：nums = [10,12,19,14] 输出：-1 解释：不存在满足条件的数对，返回 -1 。

提示：

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

思路：
数数 + 排序
时间复杂度：O(nlogn)

  1. class Solution {
  2.     public int maximumSum(int[] nums) {
  3.         int N = 200;
  4.         List<Integer>[] list = new ArrayList[N];
  5.         for (int i = 0; i < N; i++)
  6.             list[i] = new ArrayList<>();
  8.         for (int x : nums) {
  9.             int c = 0;
  10.             int t = x;
  11.             while (t > 0) {
  12.                 c += t % 10;
  13.                 t /= 10;
  14.             }
  15.             list[c].add(x);
  16.         }
  18.         int max = -1;
  19.         for (int i = 0; i < N; i++) {
  20.             if (list[i].size() >= 2) {
  21.                 int n = list[i].size();
  22.                 Collections.sort(list[i]);
  23.                 max = Math.max(max, list[i].get(n - 1) + list[i].get(n - 2));
  24.             }
  25.         }
  26.         return max;
  27.     }
  28. }

6121. 裁剪数字后查询第 K 小的数字

给你一个下标从 0 开始的字符串数组 nums ，其中每个字符串 长度相等 且只包含数字。
再给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [ki, trimi] 。对于每个 queries[i] ，你需要：

  • 将 nums 中每个数字 裁剪 到剩下 最右边 trimi 个数位。
  • 在裁剪过后的数字中，找到 nums 中第 ki 小数字对应的 下标 。如果两个裁剪后数字一样大，那么下标 更小 的数字视为更小的数字。
  • 将 nums 中每个数字恢复到原本字符串。

请你返回一个长度与 queries 相等的数组 _answer，其中 answer[i]是第 i _次查询的结果。
提示：

  • 裁剪到剩下 x 个数位的意思是不断删除最左边的数位，直到剩下 x 个数位。
  • nums 中的字符串可能会有前导 0 。

示例 1：
输入：nums = [“102”,”473”,”251”,”814”], queries = [[1,1],[2,3],[4,2],[1,2]] 输出：[2,2,1,0] 解释： 1. 裁剪到只剩 1 个数位后，nums = [“2”,”3”,”1”,”4”] 。最小的数字是 1 ，下标为 2 。 2. 裁剪到剩 3 个数位后，nums 没有变化。第 2 小的数字是 251 ，下标为 2 。 3. 裁剪到剩 2 个数位后，nums = [“02”,”73”,”51”,”14”] 。第 4 小的数字是 73 ，下标为 1 。 4. 裁剪到剩 2 个数位后，最小数字是 2 ，下标为 0 。 注意，裁剪后数字 “02” 值为 2 。
示例 2：
输入：nums = [“24”,”37”,”96”,”04”], queries = [[2,1],[2,2]] 输出：[3,0] 解释： 1. 裁剪到剩 1 个数位，nums = [“4”,”7”,”6”,”4”] 。第 2 小的数字是 4 ，下标为 3 。 有两个 4 ，下标为 0 的 4 视为小于下标为 3 的 4 。 2. 裁剪到剩 2 个数位，nums 不变。第二小的数字是 24 ，下标为 0 。

提示：

  • 1 <= nums.length <= 100
  • 1 <= nums[i].length <= 100
  • nums[i] 只包含数字。
  • 所有 nums[i].length 的长度 相同 。
  • 1 <= queries.length <= 100
  • queries[i].length == 2
  • 1 <= ki <= nums.length
  • 1 <= trimi <= nums[0].length

思路：
暴力
时间复杂度：O(n3logn)

  1. class Solution {
  2.     public int[] smallestTrimmedNumbers(String[] nums, int[][] q) {
  3.         int n = q.length, m = nums.length;
  4.         int[] res = new int[n];
  6.         Node[] node = new Node[m];
  7.         for (int i = 0; i < n; i++) {
  8.             int k = q[i][0], len = q[i][1];
  9.             for (int j = 0; j < m; j++) {
  10.                 node[j] = new Node(nums[j].substring(nums[j].length() - len, nums[j].length()), j);
  11.             }
  12.             Arrays.sort(node, (o1, o2) -> (o1.s.equals(o2.s) ? o1.id - o2.id : o1.s.compareTo(o2.s)));
  13.             res[i] = node[k - 1].id;
  14.         }
  15.         return res;
  16.     }
  18.     class Node {
  19.         String s;
  20.         int id;
  21.         Node(String s, int id) {
  22.             this.s = s;
  23.             this.id = id;
  24.         }
  25.     }
  26. }

6122. 使数组可以被整除的最少删除次数

给你两个正整数数组 nums 和 numsDivide 。你可以从 nums 中删除任意数目的元素。
请你返回使 nums 中 最小 元素可以整除 numsDivide 中所有元素的 最少 删除次数。如果无法得到这样的元素，返回 -1 。
如果 y % x == 0 ，那么我们说整数 x 整除 y 。

示例 1：
输入：nums = [2,3,2,4,3], numsDivide = [9,6,9,3,15] 输出：2 解释： [2,3,2,4,3] 中最小元素是 2 ，它无法整除 numsDivide 中所有元素。 我们从 nums 中删除 2 个大小为 2 的元素，得到 nums = [3,4,3] 。 [3,4,3] 中最小元素为 3 ，它可以整除 numsDivide 中所有元素。 可以证明 2 是最少删除次数。
示例 2：
输入：nums = [4,3,6], numsDivide = [8,2,6,10] 输出：-1 解释： 我们想 nums 中的最小元素可以整除 numsDivide 中的所有元素。 没有任何办法可以达到这一目的。

提示：

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

思路：
找到nums中最小的数x满足x整除所有numsDivide中的数
时间复杂度：O(n + logmax(nums[i]))

  1. class Solution {
  2.     public int minOperations(int[] nums, int[] p) {
  3.         int x = p[0];
  4.         for (int i = 1; i < p.length; i++) {
  5.             x = gcd(x, p[i]);
  6.         }
  8.         Arrays.sort(nums);
  9.         int i = 0;
  11.         while (i < nums.length && x % nums[i] != 0)
  12.             i++;
  13.         if (i == nums.length) return -1;
  14.         return i;
  15.     }
  17.     int gcd(int a, int b) {
  18.         return b == 0 ? a : gcd(b, a % b);
  19.     }
  20. }

势能分析入门：计算多个数gcd的复杂度