一、3446. 按对角线进行矩阵排序
题目链接
本题可以暴力枚举，在确定了每一个对角线的第一个元素下标 ( i , j ) (i,j) (i,j) 后，下一个元素的下标就是 ( i + 1 , j + 1 ) (i+1,j+1) (i+1,j+1)，即只要同时 i i i++， j j j++就可以枚举该对角线上的元素了。
这里再介绍一种更加简单的做法，我们可以定义 k = m − ( j − i ) k=m-(j-i) k=m−(j−i)，画个图理解一下：
此时，如果我们枚举 j j j，那么更据上述公式 i = j + k − m ， j = m + i − k i = j + k - m，j=m+i-k i=j+k−m，j=m+i−k，又因为 i ∈ [ 0 , n − 1 ] ， j ∈ [ 0 , m − 1 ] i\in [0,n-1]，j\in [0, m-1] i∈[0,n−1]，j∈[0,m−1]，所有 j ∈ [ m a x ( m − k ， 0 ) ， m i n ( m + n − 1 − k ， m − 1 ) ] j\in [max(m-k，0)，min(m+n-1-k，m-1)] j∈[max(m−k，0)，min(m+n−1−k，m−1)]。
代码如下：
class Solution {
public int[][] sortMatrix(int[][] g) {
int n = g.length, m = g[0].length;
int[][] ans = new int[n][m];
// k = m - (j - i)
// j = m - k + i (i=[0,n-1],j=[0,m-1])
// i = k + j - m
for(int k=1; k<n+m; k++){
int minJ = Math.max(m - k, 0);
int maxJ = Math.min(m - k + n - 1, m - 1);
List<Integer> res = new ArrayList<>();
for(int j=minJ; j<=maxJ; j++){
res.add(g[k+j-m][j]);
}
if(n-k>0) Collections.sort(res);
else Collections.sort(res, (x,y)->y-x);
for(int j=minJ, i=0; j<=maxJ; j++){
ans[k+j-m][j] = res.get(i++);
}
}
return ans;
}
}
二、3447. 将元素分配给有约束条件的组
题目链接
本题就是一个调和级数的问题，直接枚举数组 e l e m e n t s elements elements 中的元素 e l e m e n t s [ j ] elements[j] elements[j]，再枚举每个元素及其倍数 y y y，记录 y y y 对应的下标 j j j（由于枚举数组的时候从前往后遍历，所以这里的小标已经是最小的了）。如果 y y y 被枚举过，直接 c o n t i n u e continue continue。最后枚举 a s s i g n e d assigned assigned 数组，给其中的每个元素分配对应的 j j j，没有赋值为 − 1 -1 −1.
代码如下：
class Solution {
public int[] assignElements(int[] g, int[] e) {
int n = g.length;
int mx = 0;
for(int x : g){
mx = Math.max(x, mx);
}
int[] cnt = new int[mx+1];
Arrays.fill(cnt, -1);
//O(nlogn)
for(int i=0; i<e.length; i++){
int x = e[i];
if(x > mx || cnt[x] != -1) continue;
for(int y=x; y<=mx; y+=x){
if(cnt[y] != -1) continue;
cnt[y] = i;
}
}
int[] ans = new int[n];
for(int i=0; i<n; i++){
ans[i] = cnt[g[i]];
}
return ans;
}
}
三、3448. 统计可以被最后一个数位整除的子字符串数目
题目链接
本题主要涉及到取模运算的一个知识点： ( a ∗ 10 + b ) % m = ( a % m ∗ 10 + b ) % m (a*10+b)\%m=(a\%m*10+b)\%m (a∗10+b)%m=(a%m∗10+b)%m，对于 s [ i ] s[i] s[i] 来说，不需要知道 { s [ 0 : i ] , s [ 1 : i ] , s [ 2 : i ] ， . . . } \{s[0:i],s[1:i],s[2:i]，...\} {s[0:i],s[1:i],s[2:i]，...} 这些数的具体数值，只需要知道它们 % j \%j %j 的值就行（ j ∈ [ 1 , 9 ] j\in[1,9] j∈[1,9]）。这样就大大降低它的时间复杂度，可以使用数组 f [ n + 1 ] [ i ] [ j ] f[n+1][i][j] f[n+1][i][j] 统计以 s [ n ] s[n] s[n] 结尾的数中， % i = j \%i=j %i=j 的元素个数。
代码如下：
class Solution {
//(a * 10 + b) % m
//(a % m * 10 + b) % m
public long countSubstrings(String s) {
long ans = 0;
int n = s.length();
long[][] f = new long[10][9];//f[i][j]: %i 且 %i 的值为 j 的元素个数
for(int i=0; i<n; i++){
int x = s.charAt(i) - '0';
long[][] t = new long[10][9];
for(int j=1; j<10; j++){
t[j][x%j] = 1;
for(int k=0; k<j; k++){
int y = k * 10 + x;
t[j][y%j] += f[j][k];
}
}
f = t;
if(x == 0) continue;
ans += f[x][0];
}
return ans;
}
}
四、3449. 最大化游戏分数的最小值
题目链接
本题求最小值最大，可以判断是二分，再看是否存在单调性，对于本题来说，如果最小值越小，它需要的操作次数越少，就更可能 ≤ m \leq m ≤m；最小值越大，它需要的操作次数越多，就更可能 > m > m >m。具有单调性，可以用二分来做。
接下来就是写 c h e c k ( ) check() check() 方法，即判断二分的答案 m i d mid mid，能否在 m m m 次操作之内使得最小值 ⩾ m i d \geqslant mid ⩾mid。这里有一个结论：对于任何一种左右横跳的移动路径，都可以将其转换成相邻两个数之间的移动路径。对于每一个 p = p o i n t s [ i ] p = points[i] p=points[i] 来说，至少需要移动到 i i i 点 k = ( m i d − 1 ) / p k=(mid-1)/p k=(mid−1)/p 次才能 ⩾ m i d \geqslant mid ⩾mid，由于它每移动 2 次才能再次回到 i i i 点，所以需要操作 1 + ( k − 1 ) ∗ 2 1+(k-1)*2 1+(k−1)∗2 次（ 从 i − 1 到 i 需要 1 次，剩下在 i 和 i + 1 之间左右横跳 从i-1到i需要1次，剩下在i和i+1之间左右横跳 从i−1到i需要1次，剩下在i和i+1之间左右横跳），对于 i + 1 i+1 i+1 点来说，在计算 i i i 点时就已经操作了 p r e = k − 1 pre=k-1 pre=k−1 次，所以需要额外减去 p r e pre pre。最终判断 m ≥ 0 \geq 0 ≥0
代码如下：
class Solution {
public long maxScore(int[] points, int m) {
int n = points.length;
int mn = points[0];
for(int x : points){
mn = Math.min(x, mn);
}
long l = 1, r = (long)(m+1) / 2 * mn;
while(l <= r){
long mid = (l + r) >>> 1;
if(check(mid, points, m)){
l = mid + 1;
}else{
r = mid - 1;
}
}
return l - 1;
}
boolean check(long low, int[] p, int m){
int n = p.length;
int pre = 0;
for(int i=0; i<n; i++){
int k = (int)((low - 1) / p[i]) + 1 - pre;
if(i == n - 1 && k <= 0) break;
if(k < 1) k = 1;//此时已经满足条件，但仍需使用一个操作从 i-1 移动到 i
m -= 2 * k - 1;
if(m < 0) return false;
pre = k - 1;
}
return true;
}
}