第 367 场 LeetCode 周赛题解

A 找出满足差值条件的下标 I

模拟

class Solution {
public:vector<int> findIndices(vector<int> &nums, int indexDifference, int valueDifference) {int n = nums.size();for (int i = 0; i < n; i++)for (int j = 0; j <= i; j++)if (i - j >= indexDifference && abs(nums[i] - nums[j]) >= valueDifference)return {i, j};return {-1, -1};}
};

---

B 最短且字典序最小的美丽子字符串

枚举：先枚举美丽子字符串的长度以求其最短长度 $len$ ，然后遍历求长为 $len$ 的字典序最小的美丽子字符串。

class Solution {
public:string shortestBeautifulSubstring(string s, int k) {int n = s.size();vector<int> ps(n + 1);//前缀和for (int i = 0; i < n; i++)ps[i + 1] = ps[i] + (s[i] == '1' ? 1 : 0);for (int len = k; len <= n; len++) {int find = 0;for (int i = 0, j = i + len - 1; j < n; i++, j++) {if (ps[j + 1] - ps[i] == k)//子字符串s[i,j]中1的个数恰好等于 kfind = 1;}string res = "";if (find) {for (int i = 0, j = i + len - 1; j < n; i++, j++) {if (ps[j + 1] - ps[i] == k) {if (res.empty() || s.substr(i, len) < res)res = s.substr(i, len);}}return res;}}return "";}
};

---

C 找出满足差值条件的下标 II

前缀极值：设 $j\le i$ ，且 $i-j\ge indexDifference$，为了使 $abs(nums[i]-nums[j])$ 尽量大，$nums[i]$ 应该尽量小或尽量大，所以预处理求出前缀极小值数组 $mn$ （ m n [ i ] = a r g m i n 0 ≤ k ≤ i { n u m s [ k ] } mn[i]=argmin_{0\le k\le i} \{nums[k]\} mn[i]=argmin0≤k≤i​{nums[k]} ）和前缀极大值数组 $mx$（ m x [ i ] = a r g m a x 0 ≤ k ≤ i { n u m s [ k ] } mx[i]=argmax_{0\le k\le i} \{nums[k]\} mx[i]=argmax0≤k≤i​{nums[k]} ），然后枚举 $i$ 。

class Solution {
public:vector<int> findIndices(vector<int> &nums, int indexDifference, int valueDifference) {int n = nums.size();int mx[n], mn[n];mx[0] = 0;mn[0] = 0;for (int i = 1; i < n; i++) {mx[i] = nums[mx[i - 1]] > nums[i] ? mx[i - 1] : i;mn[i] = nums[mn[i - 1]] < nums[i] ? mn[i - 1] : i;}for (int i = 0; i < n; i++) {if (i - indexDifference >= 0) {if (abs(nums[i] - nums[mx[i - indexDifference]]) >= valueDifference)return {i, mx[i - indexDifference]};if (abs(nums[i] - nums[mn[i - indexDifference]]) >= valueDifference)return {i, mn[i - indexDifference]};}}return {-1, -1};}
};

---

D 构造乘积矩阵

前后缀处理：设 $pre[i]$ 为前 $i+1$ 行元素之积，设 $suf[i]$ 为后 $grid.size()-i$ 行元素之积，设 $left[i][j]$ 为第 $i$ 行前 $j+1$ 个
元素之积，设 $right[i][j]$ 为第 $i$ 行后 $grid[0].size()-j$ 个元素之积，则$p[i][j]=pre[i-1]\times suf[i+1]\times left[i][j-1]\times right[i][j+1]$

class Solution {
public:using ll = long long;vector<vector<int>> constructProductMatrix(vector<vector<int>> &grid) {int m = grid.size(), n = grid[0].size();int mod = 12345;vector<vector<int>> res(m, vector<int>(n));vector<ll> row(m, 1), pre(m, 1), suf(m, 1);for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++)row[i] = row[i] * grid[i][j] % mod;pre[i] = i != 0 ? pre[i - 1] * row[i] % mod : row[i];}for (int i = m - 1; i >= 0; i--)suf[i] = i != m - 1 ? suf[i + 1] * row[i] % mod : row[i];vector<ll> left(n), right(n);for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++)left[j] = j != 0 ? left[j - 1] * grid[i][j] % mod : grid[i][j];for (int j = n - 1; j >= 0; j--)right[j] = j != n - 1 ? right[j + 1] * grid[i][j] % mod : grid[i][j];int other = (i != 0 ? pre[i - 1] : 1) * (i != m - 1 ? suf[i + 1] : 1) % mod;for (int j = 0; j < n; j++)res[i][j] = other * (j != 0 ? left[j - 1] : 1) % mod * (j != n - 1 ? right[j + 1] : 1) % mod;}return res;}
};