6004. 得到 0 的操作数

给你两个 非负 整数 num1 和 num2 。
每一步 操作 中，如果 num1 >= num2 ，你必须用 num1 减 num2 ；否则，你必须用 num2 减 num1 。

  • 例如，num1 = 5 且 num2 = 4 ，应该用 num1 减 num2 ，因此，得到 num1 = 1 和 num2 = 4 。然而，如果 num1 = 4且 num2 = 5 ，一步操作后，得到 num1 = 4 和 num2 = 1 。

返回使 num1 = 0 或 num2 = 0 的 操作数 。

示例 1：
输入：num1 = 2, num2 = 3 输出：3 解释： - 操作 1 ：num1 = 2 ，num2 = 3 。由于 num1 < num2 ，num2 减 num1 得到 num1 = 2 ，num2 = 3 - 2 = 1 。 - 操作 2 ：num1 = 2 ，num2 = 1 。由于 num1 > num2 ，num1 减 num2 。 - 操作 3 ：num1 = 1 ，num2 = 1 。由于 num1 == num2 ，num1 减 num2 。 此时 num1 = 0 ，num2 = 1 。由于 num1 == 0 ，不需要再执行任何操作。 所以总操作数是 3 。
示例 2：
输入：num1 = 10, num2 = 10 输出：1 解释： - 操作 1 ：num1 = 10 ，num2 = 10 。由于 num1 == num2 ，num1 减 num2 得到 num1 = 10 - 10 = 0 。 此时 num1 = 0 ，num2 = 10 。由于 num1 == 0 ，不需要再执行任何操作。 所以总操作数是 1 。

提示：

  • 0 <= num1, num2 <= 105

思路：
模拟即可

  1. class Solution {
  2.     public int countOperations(int nums1, int nums2) {
  3.         int cnt = 0;
  4.         while (nums1 != 0 && nums2 != 0) {
  5.             int max = Math.max(nums1, nums2);
  6.             int min = Math.min(nums1, nums2);
  7.             cnt++;
  8.             max -= min;
  9.             nums1 = max;
  10.             nums2 = min;
  11.         }
  12.         return cnt;
  13.     }
  14. }

6005. 使数组变成交替数组的最少操作数

给你一个下标从 0 开始的数组 nums ，该数组由 n 个正整数组成。
如果满足下述条件，则数组 nums 是一个 交替数组 ：

  • nums[i - 2] == nums[i] ，其中 2 <= i <= n - 1 。
  • nums[i - 1] != nums[i] ，其中 1 <= i <= n - 1 。

在一步 操作 中，你可以选择下标 i 并将 nums[i] 更改 为 任一 正整数。
返回使数组变成交替数组的 最少操作数 。

示例 1：
输入：nums = [3,1,3,2,4,3] 输出：3 解释： 使数组变成交替数组的方法之一是将该数组转换为 [3,1,3,1,3,1] 。 在这种情况下，操作数为 3 。 可以证明，操作数少于 3 的情况下，无法使数组变成交替数组。
示例 2：
输入：nums = [1,2,2,2,2] 输出：2 解释： 使数组变成交替数组的方法之一是将该数组转换为 [1,2,1,2,1]. 在这种情况下，操作数为 2 。 注意，数组不能转换成 [2,2,2,2,2] 。因为在这种情况下，nums[0] == nums[1]，不满足交替数组的条件。

提示：

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


思路：
分奇偶统计各元素出现个数，排序后分情况讨论，只有1个数的特判一下

  1. class Solution {
  2.     public int minimumOperations(int[] nums) {
  3.         if (nums.length <= 1) return 0;
  4.         Map<Integer, Integer> m1 = new HashMap<>();
  5.         Map<Integer, Integer> m2 = new HashMap<>();
  6.         int c1 = 0, c2 = 0;
  7.         for (int i = 0; i < nums.length; i++) {
  8.             if (i % 2 == 0) {
  9.                 m1.merge(nums[i], 1, Integer::sum);
  10.                 c1++;
  11.             } else {
  12.                 m2.merge(nums[i], 1, Integer::sum);
  13.                 c2++;
  14.             }
  15.         }
  16.         PriorityQueue<int[]> q1 = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]);
  17.         PriorityQueue<int[]> q2 = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]);
  18.         for (int x : m1.keySet()) {
  19.             q1.offer(new int[]{x, m1.get(x)});
  20.         }
  21.         for (int x : m2.keySet()) {
  22.             q2.offer(new int[]{x, m2.get(x)});
  23.         }
  25.         int[] x1 = q1.poll(), y1 = q2.poll();
  26.         if (x1[0] != y1[0]) {
  28.             return c1 - x1[1] + c2 - y1[1];
  29.         } else {
  30.             boolean f1 = q1.isEmpty(), f2 = q2.isEmpty();
  31.             if (f1 && f2) {
  33.                 return Math.min(x1[1], y1[1]);
  34.             } else if (f1 && !f2) {
  35.                 int[] y2 = q2.poll();
  36.                 return Math.min(x1[1] + c2 - y1[1], c2 - y2[1]);
  37.             } else if (!f1 && f2) {
  38.                 int[] x2 = q1.poll();
  39.                 return Math.min(y1[1] + c1 - x1[1], c1 - x2[1]);
  40.             } else {
  41.                 int[] x2 = q1.poll(), y2 = q2.poll();
  43.                 return Math.min(c1 - x1[1] + c2 - y2[1], c1 - x2[1] + c2 - y1[1]);
  44.             }
  45.         }
  46.     }
  47. }

6006. 拿出最少数目的魔法豆

给你一个 正 整数数组 beans ，其中每个整数表示一个袋子里装的魔法豆的数目。
请你从每个袋子中 拿出 一些豆子（也可以 不拿出），使得剩下的 非空 袋子中（即 至少 还有 一颗 魔法豆的袋子）魔法豆的数目 相等 。一旦魔法豆从袋子中取出，你不能将它放到任何其他的袋子中。
请你返回你需要拿出魔法豆的 最少数目。

示例 1：
输入：beans = [4,1,6,5] 输出：4 解释： - 我们从有 1 个魔法豆的袋子中拿出 1 颗魔法豆。 剩下袋子中魔法豆的数目为：[4,0,6,5] - 然后我们从有 6 个魔法豆的袋子中拿出 2 个魔法豆。 剩下袋子中魔法豆的数目为：[4,0,4,5] - 然后我们从有 5 个魔法豆的袋子中拿出 1 个魔法豆。 剩下袋子中魔法豆的数目为：[4,0,4,4] 总共拿出了 1 + 2 + 1 = 4 个魔法豆，剩下非空袋子中魔法豆的数目相等。 没有比取出 4 个魔法豆更少的方案。
示例 2：
输入：beans = [2,10,3,2] 输出：7 解释： - 我们从有 2 个魔法豆的其中一个袋子中拿出 2 个魔法豆。 剩下袋子中魔法豆的数目为：[0,10,3,2] - 然后我们从另一个有 2 个魔法豆的袋子中拿出 2 个魔法豆。 剩下袋子中魔法豆的数目为：[0,10,3,0] - 然后我们从有 3 个魔法豆的袋子中拿出 3 个魔法豆。 剩下袋子中魔法豆的数目为：[0,10,0,0] 总共拿出了 2 + 2 + 3 = 7 个魔法豆，剩下非空袋子中魔法豆的数目相等。 没有比取出 7 个魔法豆更少的方案。

提示：

  • 1 <= beans.length <= 105
  • 1 <= beans[i] <= 105

思路：
排序后枚举每个数作为最终的整数即可

  1. class Solution {
  2.     public long minimumRemoval(int[] beans) {
  3.         int n = beans.length;
  4.         Arrays.sort(beans);
  6.         long min = Long.MAX_VALUE;
  7.         long[] pre = new long[n + 1];
  8.         for (int i = 1; i <= n; i++)
  9.                 pre[i] = pre[i - 1] + beans[i - 1];
  10.         for (int i = 1; i <= n; i++) {
  11.             int x = beans[i - 1];
  12.             min = Math.min(min, pre[i - 1] + pre[n] - pre[i] - (n - i) * 1L * x);
  13.         }
  14.         return min;
  15.     }
  16. }

6007. 数组的最大与和

给你一个长度为 n 的整数数组 nums 和一个整数 numSlots ，满足2 numSlots >= n 。总共有 numSlots 个篮子，编号为 1 到 numSlots 。
你需要把所有 n 个整数分到这些篮子中，且每个篮子 至多 有 2 个整数。一种分配方案的 与和 定义为每个数与它所在篮子编号的 *按位与运算 结果之和。

  • 比方说，将数字 [1, 3] 放入篮子 1 中，[4, 6] 放入篮子 2 中，这个方案的与和为 (1 AND 1) + (3 AND 1) + (4 AND 2) + (6 AND 2) = 1 + 1 + 0 + 2 = 4 。

请你返回将 nums 中所有数放入_ _numSlots 个篮子中的最大与和。

示例 1：
输入：nums = [1,2,3,4,5,6], numSlots = 3 输出：9 解释：一个可行的方案是 [1, 4] 放入篮子 1 中，[2, 6] 放入篮子 2 中，[3, 5] 放入篮子 3 中。 最大与和为 (1 AND 1) + (4 AND 1) + (2 AND 2) + (6 AND 2) + (3 AND 3) + (5 AND 3) = 1 + 0 + 2 + 2 + 3 + 1 = 9 。
示例 2：
输入：nums = [1,3,10,4,7,1], numSlots = 9 输出：24 解释：一个可行的方案是 [1, 1] 放入篮子 1 中，[3] 放入篮子 3 中，[4] 放入篮子 4 中，[7] 放入篮子 7 中，[10] 放入篮子 9 中。 最大与和为 (1 AND 1) + (1 AND 1) + (3 AND 3) + (4 AND 4) + (7 AND 7) + (10 AND 9) = 1 + 1 + 3 + 4 + 7 + 8 = 24 。 注意，篮子 2 ，5 ，6 和 8 是空的，这是允许的。

提示：

  • n == nums.length
  • 1 <= numSlots <= 9
  • 1 <= n <= 2 * numSlots
  • 1 <= nums[i] <= 15

思路：
状态压缩DP
状态表示：f[i]表示当前篮子的状态为i时能表示的所有方案
这里篮子的状态意思是将每个篮子看作三进制的某一位，例如1022从低位到高位意思是第一个篮子已经放了2个数，第二个篮子已经放了2个数，以此类推。。
属性：最大与和

状态转移：考虑当前状态i，统计各个位上数字之和cnt，得出目前应处理哪一个数，如果cnt >= n说明所有数字已经被处理过了。跳过即可
枚举nums[cnt]放在哪一个篮子里
更新对应状态即可
例如i = 1022说明当前应该处理nums[5]假设把它放在第三个篮子里new_state = 1122
f[new_state] = Math.max(f[new_state], f[i] + 3 & nums[5]

  1. class Solution {
  2.     public int maximumANDSum(int[] nums, int numSlots) {
  3.         int n = nums.length, m = numSlots;
  4.         int M = (int)Math.pow(3, m);
  6.         int[] f = new int[M];
  7.         int res = 0;
  8.         for (int i = 0; i < M; i++) {
  9.             int cnt = 0, x = i;
  10.             for (int j = 0; j < m; j++) {
  11.                 cnt += x % 3;
  12.                 x /= 3;
  13.             }
  15.             if (cnt < n) {
  16.                 x = i;
  17.                 for (int j = 1, p = 1; j <= m; j++, p *= 3) {
  18.                     if (x % 3 < 2) {
  19.                         f[i + p] = Math.max(f[i + p], f[i] + (j & nums[cnt]));
  20.                     }
  21.                     x /= 3;
  22.                 }
  23.             } else
  24.                 res = Math.max(res, f[i]);
  25.         }
  26.         return res;
  27.     }
  28. }