LeetCode --- 436周赛

题目列表

3446. 按对角线进行矩阵排序
3447. 将元素分配给有约束条件的组
3448. 统计可以被最后一个数位整除的子字符串数目
3449. 最大化游戏分数的最小值

一、按对角线进行矩阵排序

直接模拟，遍历每一个斜对角线，获取斜对角线上的数字，排序后重新赋值即可。

这里教大家一个从右上角往左下角依次遍历斜对角线的方法，对于每一条对角线上的任意元素 $grid[i][j]$，我们会发现 $i-j$ 为一个定值，以 $3\times 3$ 的矩阵为例，从右上角往左下角 $i-j$ 分别为 $-2,-1,0,1,2$，只要加上一个偏移量 $3$，就会变成 $1,2,3,4,5$

由此可以推导出一个公式，对于一个 $n\times m$ 的矩阵，令 $k=m+i-j$，让 $k=1,2,...,n+m-1$，可以依次遍历每一条斜对角线，其中 $i\in [0,n-1]，j=m+i-k$

代码如下

// C++
class Solution {
public:vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {int n = grid.size(), m = grid[0].size();// 令 k = m - j + i => j = m - k + i , i = k - m + j// 当 i = 0 时，j = m - k// 当 i = n - 1 时，j = m - k + n - 1for(int k = 1; k < n + m; k++){int min_j = max(m - k, 0); // 注意越界int max_j = min(m - k + n - 1, m - 1); // 注意越界vector<int> res;for(int j = min_j; j <= max_j; j++){res.push_back(grid[k - m + j][j]);}if(min_j > 0) ranges::sort(res);else ranges::sort(res, greater<>());for(int j = min_j; j <= max_j; j++){grid[k - m + j][j] = res[j - min_j];}}return grid;}
};

# Python
class Solution:# k = m + i - j# i = 0, j = m - k# i = n - 1, j = m - k + n - 1def sortMatrix(self, grid: List[List[int]]) -> List[List[int]]:n, m = len(grid), len(grid[0])for k in range(1, n+m):min_j = max(m - k, 0)max_j = min(m - k + n - 1, m - 1)res = [grid[k - m + j][j] for j in range(min_j, max_j + 1)]res.sort(reverse=min_j==0)for j, val in zip(range(min_j, max_j + 1), res):grid[k - m + j][j] = valreturn grid

二、将元素分配给有约束条件的组

我们可以优先计算出 $elements$ 中数字的倍数情况，存放在 $f[x]$ 中，$f[x]=i$ 表示 $x$ 能被 $elements[i]$ 整除，如果有多个 $i$ 符合条件，取最左边的那个，然后根据 $f[x]$ 中的结果给 $groups$ 中的数进行赋值即可，具体操作见代码，如下

// C++
class Solution {
public:vector<int> assignElements(vector<int>& groups, vector<int>& elements) {int n = groups.size(), m = elements.size();int mx = ranges::max(groups);vector<int> f(mx + 1, -1);// 时间复杂度分析// 当elements=[1,2,3,...,x]时，达到最坏时间复杂度//  mx/1+mx/2+...+mx/x//= mx(1+1/2+1/3+...+1/x)//= mx*log(x)for(int i = 0; i < m; i++){int x = elements[i];if(x > mx || f[x] != -1) continue;for(int j = 1; j < mx/x + 1; j++){if(f[x*j] == -1){f[x*j] = i;}}}vector<int> ans(n);for(int i = 0; i < n; i++){ans[i] = f[groups[i]];}return ans;}
};

# Python
class Solution:def assignElements(self, groups: List[int], elements: List[int]) -> List[int]:mx = max(groups)f = [-1] * (mx + 1)for i, x in enumerate(elements):if x > mx or f[x] != -1:continuefor j in range(x, mx+1, x):if f[j] < 0:f[j] = ireturn [f[x] for x in groups]

三、统计可以被最后一个数位整除的子字符串数目

题目思路：

• 由于最后一位数的取值为 $1$~$9$，我们可以分别统计以这些数为结尾的数字对答案的贡献

• 假设我们计算以 $x$ 为结尾的数字对答案的贡献

  • 对于前 $i$ 个字符组成的数字 $S_{i-1}$，加上当前数字 $s_i$，它的取模结果为 $(S_{i-1}\times 10+s_i)\%x=((S_{i-1}\times 10)\%x+s_i)\%x=((S_{i-1}\%x)\times 10+s_i)\%x$
  • 从式子中我们可以看出，我们其实并不需要关心数字 $S_{i-1}$ 具体是多少，我们只要知道 $S_{i-1}\%x$ 的结果即可
  • 设 $f[i][j]$ 表示数字 $S_i$ 模 $x$ 后结果为 $j$ 的所有数字个数
    • $f[i][(j\times 10+s_i)\%x]+$$=f[i-1][j]$，$j\in [0,x)$，$s_i$ 和前面的 $S_{i-1}$ 合起来作为一个数
    • $f[i][s_i\%x]+$$=1$，$s_i$ 单独作为一个数
  • 当 $s_i=x$ 时，将 $f[i][0]$ 加入答案

代码如下

// C++
class Solution {
using LL = long long;
public:long long countSubstrings(string s) {int n = s.size();LL ans = 0;for(int x = 1; x < 10; x++){vector f(n + 1, vector<LL>(x));for(int i = 0; i < n; i++){int y = s[i] - '0';for(int j = 0; j < x; j++){f[i+1][(j*10+y)%x] += f[i][j];}f[i+1][y%x]++;if(y == x) ans += f[i+1][0];}}return ans;}
};
// 空间优化
class Solution {
using LL = long long;
public:long long countSubstrings(string s) {int n = s.size();LL ans = 0;for(int x = 1; x < 10; x++){vector<LL> f(x);for(int i = 0; i < n; i++){vector<LL> t(x);int y = s[i] - '0';for(int j = 0; j < x; j++){t[(j*10+y)%x] += f[j];}t[y%x]++;f = t;if(y == x) ans += f[0];}}return ans;}
};

# Python
class Solution:def countSubstrings(self, s: str) -> int:n = len(s)ans = 0for x in range(1, 10):f = [0] * xfor y in map(int, s):t = [0] * xfor j in range(x):t[(j*10+y)%x] += f[j]t[y%x] += 1f = tif x == y: ans += f[0]return ans

四、最大化游戏分数的最小值

最大化最小值，显然用二分来做。

• 是否具有单调性？显然具备，因为 $gameScor{e}_{min}$ 越大，则每个下标位 $+$$=points[i]$ 的操作次数就会变多，则总操作数就会更容易超过 $m$，故可以用二分
• $check$ 函数如何写？这里有个结论：对于任意一种下标移动顺序，都能变成若干组左右来回横跳的形式。所以我们可以贪心的让左边的下标先满足条件，然后再考虑后面的位置，即我们先考虑通过 $0\to 1、1\to 0$ 让 $0$ 先满足条件，在用$1\to 2、2\to 1$ 让 $1$ 满足条件，同样的方式让 $2、3、...、n-1$ 依次满足条件，看总操作次数是否 $>m$

代码如下

// C++
class Solution {
using LL = long long;
public:long long maxScore(vector<int>& points, int m) {int n = points.size();auto check = [&](LL k)->bool{if(k == 0) return true;int s = m, pre = 0; // pre 表示为了解决 i - 1 位置，进行反复横跳之后，对 i 位置已经进行的 += points[i] 操作次数for(int i = 0; i < n; i++){int ops = (k - 1) / points[i] + 1 - pre; // 需要走 ops 次if(i == n - 1 && ops <= 0)break;ops = max(1, ops); // 从 i-1 移动到 i，需要至少 1 次操作s -= 2 * (ops - 1) + 1;if(s < 0) return false;pre = ops - 1;}return true;};// (m + 1)/2 表示只有两个数时，第一个数进行的操作次数，这里我们默认将最小值放在这一位，得到一个上限LL l = 0, r = 1LL * (m + 1) / 2 * ranges::min(points);while(l <= r){LL mid = l + (r - l)/2;if(check(mid)) l = mid + 1;else r = mid - 1;}return r;}
};

# Python
class Solution:def maxScore(self, points: List[int], m: int) -> int:n = len(points)def check(k:int)->int:if k == 0: return Trues = mpre = 0for i, x in enumerate(points):ops = (k - 1) // x + 1 - preif i == n - 1 and ops <= 0:return Trueops = max(ops, 1)s -= 2 * ops - 1if s < 0: return Falsepre = ops - 1return Truel , r = 0, (m + 1) // 2 * min(points)while l <= r:mid = l + (r - l) // 2if check(mid):l = mid + 1else:r = mid - 1return r