本文主要是介绍LeetCode --- 412周赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目列表
3264. K 次乘运算后的最终数组 I
3266. K 次乘运算后的最终数组 II
3265. 统计近似相等数对 I
3267. 统计近似相等数对 II
一、K次乘预算后的最终数组 I & II
I 数据范围比较小，可以暴力模拟，代码如下
class Solution {
public:vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {int n = nums.size();while(k--){int pos = 0;for(int i = 1; i < n; i++){if(nums[pos] > nums[i])pos = i;}nums[pos] *= multiplier;}return nums;}
};II 的数据范围变大了，暴力会超时，需要优化，如何做？
这里我们需要找到一些规律：
1、假设数组nums中只有一个数字x，我们直接返回 x * multiplier ^ k
2、假设数组nums中有两个数字 x，y (x <= y)
1) x 太小(或者 k 太小 或者 multiplier 太小)，导致 x * multiplier ^ k < y
2) x 和 y 相近，x 乘以 m (m < k) 个的 multiplier 后，就会大于 y，即 x * multiplier ^ m > y，那么下一次 y * multiplier 一定大于 x * multiplier ^ m (我们对两边同除multiplier，可得y > x*multiplier^(m-1) 成立），所以后面的乘法操作就是这两个数字交替进行。
3、假设数组nums中有三个数字 x，y，z (x <= y <= z)，当 z 成为最小值，x 变成 X，y变成Y 时，假设 z <= Y <= X，由 2 可知，z * multiplier 必然大于 Y 和 X，下一个 Y * multiplier 必然大于 z，下一个 X * multiplier 必然大于 Y，同理后面的乘法操作就是这三个数字交替进行。
......
我们不难得出结论：当数组中的最大值成为最小值的时候，剩余的 操作次数 会被均匀的分配给每个数字，如果除不尽的化，会按照大小顺序分配多余的1次乘法操作
那么在数组中的最大值成为最小值之前的操作，我们只需要模拟即可，代码如下
class Solution {const int MOD = 1e9 + 7;using LL = long long;
public:LL POW(LL x, LL y){LL res = 1;while(y){if(y & 1) res = (res * x) % MOD;x = (x * x) % MOD;y >>= 1; }return res;}vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {if(multiplier == 1) return nums;int n = nums.size();int mx = ranges::max(nums);priority_queue<pair<LL,int>,vector<pair<LL,int>>,greater<>>pq;// 建堆for(int i = 0; i < n; i++)pq.emplace(nums[i], i);// while循环的时间复杂度，考虑最坏情况 k = 1e9 ，muiliplier = 2// nums = {1，1，1，1，...，1e9}, U = max(nums), n = len(nums)// 即每一个 1 都需要 logU 的时间变得 >= 1e9// 时间复杂度为 min(k, nlognlogU) = nlognlogUwhile(k && mx != pq.top().first){auto [x, i] = pq.top(); pq.pop();pq.emplace(x * multiplier, i);k--;}int j = 0;int p1 = POW(multiplier, k/n) % MOD;int p2 = POW(multiplier, k/n + 1) % MOD;while(pq.size()){auto [x, i] = pq.top(); pq.pop();nums[i] = x % MOD * (j < k % n ? p2 : p1) % MOD;j++;}return nums;}
};二、统计近似相等数对 I
题目一数据范围比较小，可以直接暴力模拟，代码如下
class Solution {
public:int countPairs(vector<int>& nums) {int n = nums.size(), ans = 0;auto check = [&](int i, int j)->bool{int x = nums[i], y = nums[j], ret = 0;int cnt1[10]{}, cnt2[10]{};while(x || y){if(x % 10 != y % 10){cnt1[x % 10]++;cnt2[y % 10]++;ret++;}x /= 10, y /= 10;}for(int i = 0; i < 10; i++)if(cnt1[i] != cnt2[i])return false;return ret == 0 || ret == 2;};for(int i = 0; i < n; i++){for(int j = i + 1; j < n; j++){ans += check(i, j);}}return ans;}
};三、统计近似相等数对 II
这种找匹配个数的题，很容易想到两数之和，用哈希表，边记录数字出现次数，边统计结果，这题也是同理，我们边记录数字出现次数，边统计当前遍历到的数字能变成哪些数字，在将这些数字的出现次数加入答案即可，代码如下
class Solution {
public:int countPairs(vector<int>& nums) {ranges::sort(nums);int ans = 0;unordered_map<int,int>mp;for(int x: nums){unordered_set<int> st = {x}; // 记录 x 能变成哪些数字string s = to_string(x);int m = s.size();for(int i = 0; i < m; i++){for(int j = i + 1; j < m; j++){swap(s[i], s[j]);st.insert(stoi(s));for(int p = i + 1; p < m; p++){for(int q = p + 1; q < m; q++){swap(s[p], s[q]);st.insert(stoi(s));swap(s[p], s[q]); // 注意要恢复现场}}swap(s[i], s[j]); // 注意要恢复现场}}for(auto e: st)ans += (mp.contains(e) ? mp[e] : 0);mp[x]++;}return ans;}
};这篇关于LeetCode --- 412周赛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
