欢迎大家加QQ群：623375442，可以方便群里面交流。
100345. Find Minimum Operations to Make All Elements Divisible by Three
给你一个整数数组 nums 。一次操作中，你可以将 nums 中的 任意 一个元素增加或者减少 1 。
请你返回将 nums 中所有元素都可以被 3 整除的 最少 操作次数。
测试样例：
输入：nums = [1,2,3,4]
输出：3
解释：通过以下 3 个操作，数组中的所有元素都可以被 3 整除：将 1 减少 1 。将 2 增加 1 。将 4 减少 1 。
解答：非常简单的数学题。% 3之后，看当前数利用加法还是减法可以更快的到达3的倍数。
class Solution {
public int minimumOperations(int[] nums) {
int res = 0;
for (int n : nums) {
int r = n % 3;
res += Math.min(3 - r, r);
}
return res;
}
}100344. Minimum Operations to Make Binary Array Elements Equal to One I
给你一个二进制数组 nums 。
你可以对数组执行以下操作 任意 次（也可以 0 次）：
- 选择数组中 任意连续 3 个元素，并将它们 全部反转 。
反转 一个元素指的是将它的值从 0 变 1 ，或者从 1 变 0 。
请你返回将 nums 中所有元素变为 1 的 最少 操作次数。如果无法全部变成 1 ，返回 -1 。
测试样例：
输入：nums = [0,1,1,1,0,0]
输出：3
解释：我们可以执行以下操作：
- 选择下标为 0 ，1 和 2 的元素并反转，得到 nums = [1,0,0,1,0,0] 。
- 选择下标为 1 ，2 和 3 的元素并反转，得到 nums = [1,1,1,0,0,0] 。
- 选择下标为 3 ，4 和 5 的元素并反转，得到 nums = [1,1,1,1,1,1] 。
解答：暴力遍历，如果当前数字不符合要求，那么就尝试一次操作。
class Solution {
public int minOperations(int[] nums) {
int res = 0;
for (int i = 0; i < nums.length; ++i) {
if (nums[i] == 0) {
if (i + 2 >= nums.length) return -1;
nums[i] ^= 1;
nums[i + 1] ^= 1;
nums[i + 2] ^= 1;
++res;
}
}
return res;
}
}
100346. Minimum Operations to Make Binary Array Elements Equal to One II
给你一个二进制数组 nums 。
你可以对数组执行以下操作 任意 次（也可以 0 次）：
- 选择数组中 任意 一个下标 i ，并将从下标 i 开始一直到数组末尾 所有 元素 反转 。
反转 一个元素指的是将它的值从 0 变 1 ，或者从 1 变 0 。
请你返回将 nums 中所有元素变为 1 的 最少 操作次数。
测试样例：
输入：nums = [0,1,1,0,1]
输出：4
解释：我们可以执行以下操作：
- 选择下标 i = 1 执行操作，得到 nums = [0,0,0,1,0] 。
- 选择下标 i = 0 执行操作，得到 nums = [1,1,1,0,1] 。
- 选择下标 i = 4 执行操作，得到 nums = [1,1,1,0,0] 。
- 选择下标 i = 3 执行操作，得到 nums = [1,1,1,1,1] 。
解答：没啥难度，类似前缀和。记录一下当前数字的反转次数。如果当前数经过计算之后，不满足要求，那么就翻转一下。
class Solution {
public int minOperations(int[] nums) {
int res = 0, xor = 0;
for (int n : nums) {
if ((n ^ xor) == 0) {
++res;
xor ^= 1;
}
}
return res;
}
}100333. Count the Number of Inversions
给你一个整数 n 和一个二维数组 requirements ，其中 requirements[i] = [endi, cnti] 表示这个要求中的末尾下标和 逆序对 的数目。
整数数组 nums 中一个下标对 (i, j) 如果满足以下条件，那么它们被称为一个 逆序对 ：
- i < j 且 nums[i] > nums[j]
请你返回 [0, 1, 2, ..., n - 1] 的 排列 perm 的数目，满足对 所有 的 requirements[i] 都有 perm[0..endi] 恰好有 cnti 个逆序对。
由于答案可能会很大，将它对 10^9 + 7 取余 后返回。
测试样例：
输入：n = 3, requirements = [[2,2],[0,0]]
输出：2
解释：两个排列为：
- [2, 0, 1]
- 前缀 [2, 0, 1] 的逆序对为 (0, 1) 和 (0, 2) 。
- 前缀 [2] 的逆序对数目为 0 个。
- [1, 2, 0]
- 前缀 [1, 2, 0] 的逆序对为 (0, 2) 和 (1, 2) 。
- 前缀 [1] 的逆序对数目为 0 个。
解答：这题我觉得还挺难的，但是看AC的人还挺多的。大致思路可以参考这题903. Valid Permutations for DI Sequence。也是类似的map的思路。然后遍历到第i个数的时候，最后一位为0，那么当前的位数需要增加i，1就是i - 1。。。以此类推。唯一需要注意的是，还需要满足requirement。
class Solution {
private static final int mod = 1_000_000_007;
public int numberOfPermutations(int n, int[][] requirements) {
int[] rq = new int[n];
Arrays.fill(rq, -1);
int max = 0;
for (int[] r : requirements) {
rq[r[0]] = r[1];
max = Math.max(max, r[1]);
}
if (rq[0] > 0) {
return 0;
}
int[] cur = new int[max + 1];
cur[0] = 1;
for (int i = 1; i < n; ++i) {
int[] next = new int[max + 1];
int sum = 0;
for (int j = 0; j <= max; ++j) {
sum = (sum + cur[j]) % mod;
if (rq[i] == -1 || rq[i] == j) {
next[j] = sum;
}
if (j >= i) {
sum = (sum + mod - cur[j - i]) % mod;
}
}
cur = next;
}
return cur[max];
}
}