第 376 场 LeetCode 周赛题解

A 找出缺失和重复的数字

模拟

class Solution {
public:
    vector<int> findMissingAndRepeatedValues(vector<vector<int>> &grid) {
        int n = grid.size();
        vector<int> vis(n * n + 1);
        for (auto &r: grid)
            for (auto &c: r)
                vis[c]++;
        vector<int> res(2);
        for (int i = 1; i <= n * n; i++)
            if (vis[i] == 2)
                res[0] = i;
            else if (vis[i] == 0)
                res[1] = i;
        return res;
    }
};

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

贪心：为了使组内元素之差尽可能小，所以只将排序后相邻的三个元素依次划分为一个子数组

class Solution {
public:
    vector<vector<int>> divideArray(vector<int> &nums, int k) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        for (int i = 0; i < nums.size(); i += 3)
            if (nums[i + 2] - nums[i] > k)
                return {};
            else {
                res.push_back({nums[i], nums[i + 1], nums[i + 2]});
            }
        return res;
    }
};

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

枚举：首先对 $nums$ 排序，若 $nums$ 的中位数 $mid$ 为回文数则将 $nums$ 中各元素变为 $mid$ 即可产生最小代价，否则 $y$ 应该是小于 $mid$ 的且最接近 $mid$ 的回文数 或 大于 $mid$ 的且最接近 $mid$ 的回文数

class Solution {
public:
    using ll = long long;

    bool ispow10(int x) {
        while (x % 10 == 0)
            x /= 10;
        return x == 1;
    }

    vector<int> find_val(int x) {//找到最接近x的几个回文数
        vector<int> res;
        string s = to_string(x);
        if (ispow10(x)) {
            if (x == 1e9)
                return {(int) 1e9 - 1};
            else if (x == 1)
                return {x};
            else
                return {x + 1, x - 1};
        } else if (ispow10(x + 1) || ispow10(x - 1))
            return {x};

        if (s.size() % 2 == 0) {
            string left = s.substr(0, s.size() / 2);
            vector<int> d{1, 0, -1};
            for (auto di: d) {
                string nleft = to_string(stol(left) + di);
                string r = string(nleft.rbegin(), nleft.rend());
                ll t = stol(nleft + r);
                if (t < 1e9) {
                    res.push_back(t);
                }
            }
        } else {
            string left = s.substr(0, s.size() / 2 + 1);
            vector<int> d{1, 0, -1};
            for (auto di: d) {
                string nleft = to_string(stol(left) + di);
                string r = string(nleft.rbegin() + 1, nleft.rend());
                ll t = stol(nleft + r);
                if (t < 1e9) {
                    res.push_back(t);
                }
            }
        }
        return res;
    }

    long long minimumCost(vector<int> &nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int x = n % 2 == 0 ? (nums[(n - 1) / 2] + nums[n / 2]) / 2 : nums[n / 2];
        auto tar = find_val(x);
        ll res = INT64_MAX;
        for (auto ti: tar) {
            ll t = 0;
            for (auto it: nums)
                t += abs(it - ti);
            res = min(res, t);
        }
        return res;
    }
};

D 执行操作使频率分数最大

二分+枚举：二分答案 $mid$，在排序后的 $nums$ 中枚举长为 $mid$ 的子数组，判断该将该子数组变为同一元素的最少操作（变为该子数组的中位数即可产生最少操作数）数是否不超过 $k$

class Solution {
public:
    using ll = long long;

    int maxFrequencyScore(vector<int> &nums, long long k) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<ll> ps(n + 1);//前缀和
        for (int i = 0; i < n; i++)
            ps[i + 1] = ps[i] + nums[i];
        int l = 1, r = n;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            int find = 0;
            for (int l = 0, r = mid - 1; r < n; l++, r++) {//子数组nums[l,r]
                int cen = (l + r) / 2;
                int tar = nums[cen];//将子数组各元素变为tar产生最少操作数
                ll t = 1LL * tar * (cen - l + 1) - (ps[cen + 1] - ps[l]) + ps[r + 1] - ps[cen + 1] - 1LL * tar * (r - cen);
                if (k >= t) {
                    find = 1;
                    break;
                }
            }
            if (find)
                l = mid;
            else
                r = mid - 1;
        }
        return l;
    }
};