第 133 场 LeetCode 双周赛题解

A 使所有元素都可以被 3 整除的最少操作数

遍历 $nums$ ，每有一个不被 $3$ 整除的数，则操作数加 $1$

class Solution {public:int minimumOperations(vector<int>& nums) {int res = 0;for (auto x : nums)if (x % 3 != 0)res++;return res;}
};

---

B 使二进制数组全部等于 1 的最少操作次数 I

遍历：顺序遍历 $nums$ 中的长为 $3$ 的子数组，若子数组首元素为 $0$ ，则反转子数组，最终判断 $nums$ 的最后两个元素是否为 $1$

class Solution {public:int minOperations(vector<int>& nums) {int n = nums.size();int res = 0;for (int i = 0; i < n - 2; i++)if (nums[i] == 0) {res++;nums[i + 1] ^= 1;nums[i + 2] ^= 1;}if (nums[n - 2] == 0 || nums[n - 1] == 0)return -1;return res;}
};

---

C 使二进制数组全部等于 1 的最少操作次数 II

遍历：顺序遍历 $nums$ ，记录当前操作的总次数，对于每个遍历到的位置，若当前操作次数为偶数则当前位置的元素不变，否则当前位置元素反转

class Solution {public:int minOperations(vector<int>& nums) {int res = 0;for (auto x : nums)if ((x + res) % 2 == 0)res++;return res;}
};

---

D 统计逆序对的数目

动态规划：设 $p[i,j]$ 为 $i+1$ 个不同的数形成的恰有 $j$ 个逆序对的排列的数目(模 $1e9+7$)，通过枚举排列的最后一个元素来进行状态转移，转移过程注意不满足题目条件的排列，可以通过记忆化搜索实现

class Solution {public:using ll = long long;ll mod = 1e9 + 7;int numberOfPermutations(int n, vector<vector<int>>& requirements) {vector<int> cnt(n, -1);for (auto& it : requirements)cnt[it[0]] = it[1];//固定要求vector<vector<ll>> p(n, vector<ll>(cnt[n - 1] + 1, INT64_MIN));function<ll(int, int)> get = [&](int loc, int k) {//记忆化搜索if (k < 0)return 0LL;if (p[loc][k] != INT64_MIN)return p[loc][k];if (cnt[loc] != -1 && cnt[loc] != k)//不满足要求return p[loc][k] = 0;if (loc == 0)return p[loc][k] = k == 0 ? 1 : 0;p[loc][k] = 0;for (int i = 0; i <= loc; i++) {//枚举最后一位p[loc][k] += get(loc - 1, k - (loc - i));p[loc][k] %= mod;}return p[loc][k];};return (get(n - 1, cnt[n - 1]) + mod) % mod;}
};