第 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());elserotate(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 交换得到字典序最小的数组

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

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(modk)$，所以前面出现过的满足 $v_l-c_l$ 且 $v_l\equiv v_{r+1}-w(modk)$ 的 $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++;elsec++;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;}
};