第 373 场 LeetCode 周赛题解

A 循环移位后的矩阵相似检查

模拟

class Solution {
public:
    bool areSimilar(vector<vector<int>> &mat, int k) {
        int m = mat.size(), n = mat[0].size();
        k %= n;
        auto g = mat;
        for (int i = 0; i < m; i++)
            if (i & 1)
                rotate(mat[i].begin(), mat[i].begin() + n - k, mat[i].end());
            else
                rotate(mat[i].begin(), mat[i].begin() + k, mat[i].end());
        return g == mat;
    }
};

B 统计美丽子字符串 I

前缀和：枚举子数组，用前缀和记录当前子数组的元音字符数

class Solution {
public:
    int beautifulSubstrings(string s, int k) {
        int n = s.size();
        unordered_set<char> vo{'a', 'e', 'i', 'o', 'u'};
        vector<int> sv(n + 1);
        for (int i = 0; i < n; i++)
            sv[i + 1] = vo.count(s[i]) ? sv[i] + 1 : sv[i];
        int res = 0;
        for (int l = 0; l < n; l++)
            for (int r = l; r < n; r++)
                if (auto v = sv[r + 1] - sv[l];v * 2 == r - l + 1 && v * v % k == 0)
                    res++;
        return res;
    }
};

C 交换得到字典序最小的数组

排序：排序后的 $n u m s$ 可以划分成若干子数组，其中每个子数组中相邻元素之差不超过 $l imi t$ ，可以通过交换得到的字典序最小的数组即为：每个子数组在原数组所在位置上按非降序排序得到的数组

class Solution {
public:
    vector<int> lexicographicallySmallestArray(vector<int> &nums, int limit) {
        int n = nums.size();
        vector<pair<int, int>> li(n);
        for (int i = 0; i < n; i++)
            li[i] = {i, nums[i]};
        sort(li.begin(), li.end(), [](pair<int, int> &x, pair<int, int> &y) { return x.second < y.second; });//按值排序
        for (int i = 0, j = 0; i < n; i = ++j) {
            while (j + 1 < n && li[j + 1].second - li[j].second <= limit)//找到当前分组的右边界
                j++;
            vector<pair<int, int>> t{li.begin() + i, li.begin() + j + 1};
            sort(li.begin() + i, li.begin() + j + 1);//按原数组中下标排序
            for (int k = i; k <= j; k++)
                nums[li[k].first] = t[k - i].second;
        }
        return nums;
    }
};

D 统计美丽子字符串 II

前缀和 + 哈希：设 $v_{k}$ 表示 $s$ 长为 $k$ 的前缀中的元音字符数，设 $c_{k}$ 表示 $s$ 长为 $k$ 的前缀中的非元音字符数，若 $s [l, r]$ 为美丽子字符串，则有 $v_{r+1}-v_{l}=c_{r+1}-c_{l}$ , 即 $v_{r+1}-c_{r+1}=v_{l}-c_{l}$ ，且 $v_{r+1}-v_{l})^2\%k=0$ ，不妨设 $w=v_{r+1}-v_{l}$ ，则 $v_l \equiv v_{r+1}-w (mod\;k)$ ，所以前面出现过的满足 $v_{l}-c_{l}$ 且 $v_l \equiv v_{r+1}-w (mod\;k)$ 的 $l$ 可以使 $s [l, r]$ 为美丽子字符串

class Solution {
public:
    using ll = long long;

    long long beautifulSubstrings(string s, int k) {
        vector<int> li;
        for (int i = 0; i < k; i++)
            if (i * i % k == 0)
                li.push_back(i);
        map<pair<int, int>, int> cnt;
        unordered_set set_vo{'a', 'e', 'i', 'o', 'u'};
        cnt[{0, 0}] = 1;
        ll res = 0;
        for (int i = 0, v = 0, c = 0; i < s.size(); i++) {
            if (set_vo.count(s[i]))
                v++;
            else
                c++;
            for (auto w: li) {
                auto vl = ((v - w) % k + k) % k;
                if (auto it = cnt.find({v - c, vl});it != cnt.end())
                    res += it->second;
            }
            cnt[{v - c, v % k}]++;
        }
        return res;
    }
};