Leetcode - 周赛436

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

题目链接

本题可以暴力枚举，在确定了每一个对角线的第一个元素下标 $(i,j)$ 后，下一个元素的下标就是 $(i+1,j+1)$，即只要同时 $i$++，$j$++就可以枚举该对角线上的元素了。

这里再介绍一种更加简单的做法，我们可以定义 $k=m-(j-i)$，画个图理解一下：

此时，如果我们枚举 $j$，那么更据上述公式 $i=j+k-m，j=m+i-k$，又因为 $i\in [0,n-1]，j\in [0,m-1]$，所有 $j\in [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 - mfor(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. 将元素分配给有约束条件的组

题目链接

本题就是一个调和级数的问题，直接枚举数组 $elements$ 中的元素 $elements[j]$，再枚举每个元素及其倍数 $y$，记录 $y$ 对应的下标 $j$（由于枚举数组的时候从前往后遍历，所以这里的小标已经是最小的了）。如果 $y$ 被枚举过，直接 $continue$。最后枚举 $assigned$ 数组，给其中的每个元素分配对应的 $j$，没有赋值为 $-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\ast 10+b)\%m=(a\%m\ast 10+b)\%m$，对于 $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\in [1,9]$）。这样就大大降低它的时间复杂度，可以使用数组 $f[n+1][i][j]$ 统计以 $s[n]$ 结尾的数中，$\%i=j$ 的元素个数。

代码如下：

class Solution {//(a * 10 + b) % m//(a % m * 10 + b) % mpublic 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. 最大化游戏分数的最小值

题目链接

本题求最小值最大，可以判断是二分，再看是否存在单调性，对于本题来说，如果最小值越小，它需要的操作次数越少，就更可能 $\le m$；最小值越大，它需要的操作次数越多，就更可能 $>m$。具有单调性，可以用二分来做。

接下来就是写 $check()$ 方法，即判断二分的答案 $mid$，能否在 $m$ 次操作之内使得最小值 $⩾mid$。这里有一个结论：对于任何一种左右横跳的移动路径，都可以将其转换成相邻两个数之间的移动路径。对于每一个 $p=points[i]$ 来说，至少需要移动到 $i$ 点 $k=(mid-1)/p$ 次才能 $⩾mid$，由于它每移动 2 次才能再次回到 $i$ 点，所以需要操作 $1+(k-1)\ast 2$ 次（$从i-1到i需要1次，剩下在i和i+1之间左右横跳$），对于 $i+1$ 点来说，在计算 $i$ 点时就已经操作了 $pre=k-1$ 次，所以需要额外减去 $pre$。最终判断 m $\ge 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 移动到 im -= 2 * k - 1;if(m < 0) return false;pre = k - 1;}return true;}
}