力扣376周赛

力扣第376场周赛

找出缺失和重复的数字

map模拟

class Solution {
public:vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {int n = grid.size() , m = grid[0].size();map<int,int>mi;for(int i = 0 ; i < n ; i ++){for(int j = 0 ; j < m ; j ++){mi[grid[i][j]] ++;}}vector<int> ans;for(int i = 1 ; i <= n * n ; i ++){if(mi[i] > 1)ans.push_back(i);}for(int i = 1 ; i <= n * n ; i ++){if(mi[i] == 0)ans.push_back(i);}return ans;}
};

划分数组并满足最大差限制

排序后直接模拟

class Solution {
public:vector<vector<int>> divideArray(vector<int>& nums, int k) {vector<vector<int> >ans;vector<vector<int> >res;int n = nums.size();ranges::sort(nums);bool f = true;if(n % 3 != 0)f = false;for(int i = 0 ; i + 2 < n ; i += 3){int a = nums[i] , c = nums[i + 2];if(c - a > k)f = false;ans.push_back({a , nums[i + 1] , c});}if(f == false)return res;return ans;}
};

使数组成为等数数组的最小代价

找到中位数再二分最近的回文

//代码来自TsReaper
bool inited = false;
vector<int> good;void init() {if (inited) return;inited = true;for (int i = 1; i < 10; i++) good.push_back(i);// 首先枚举回文数一半的长度 len，以及这一半数值的上限 pfor (int p = 10, len = 1; p <= 1e4; p *= 10, len++) {// 枚举回文数的一半具体是什么数for (int i = 1; i < p; i++) if (i % 10 != 0) {// 把每个数位拆开来vector<int> vec;for (int x = i, j = len; j > 0; x /= 10, j--) vec.push_back(x % 10);// 回文数长度是偶数的情况int v = 0;for (int j = 0; j < len; j++) v = v * 10 + vec[j];for (int j = len - 1; j >= 0; j--) v = v * 10 + vec[j];good.push_back(v);// 回文数长度是奇数的情况，需要枚举中间那一位是什么数for (int k = 0; k < 10; k++) {v = 0;for (int j = 0; j < len; j++) v = v * 10 + vec[j];v = v * 10 + k;for (int j = len - 1; j >= 0; j--) v = v * 10 + vec[j];good.push_back(v);}}}sort(good.begin(), good.end());
}class Solution {
public:long long minimumCost(vector<int>& nums) {init();int n = nums.size();sort(nums.begin(), nums.end());// 计算所有数都变成 x 的代价auto get = [&](int x){long long res = 0;for(int i = 0 ; i < n ; i ++){res += abs(nums[i] - x);}return res;};long long ans = 1e18;int idx = lower_bound(good.begin(), good.end(), nums[n / 2]) - good.begin();ans = min(ans, get(good[idx]));if (idx - 1 >= 0) ans = min(ans, get(good[idx - 1]));return ans;}
};

执行操作使频率分数最大

滑动窗口统计化成中位数的最小步骤

//代码来自TsReaper
class Solution {
public:int maxFrequencyScore(vector<int>& nums, long long k) {int n = nums.size();nums.push_back(0);sort(nums.begin(), nums.end());// 预处理前缀和long long f[n + 1];f[0] = 0;for (int i = 1; i <= n; i++) f[i] = f[i - 1] + nums[i];// 求把 nums[L] 到 nums[R] 全部变成中位数的最小代价auto gao = [&](int L, int R) {// 找到中位数的下标int mid = (L + R) / 2;long long l = 1LL * nums[mid] * (mid - L + 1) - (f[mid] - f[L - 1]);long long r =  ((f[R] - f[mid]) - 1LL * nums[mid] * (R - mid));return l + r;};int ans = 0;// 滑动窗口//i右端点j左端点for (int i = 1, j = 1; i <= n; i++) {while (j <= i && gao(j, i) > k) j++;ans = max(ans, i - j + 1);}return ans;}
};

–