Leetcode-周赛436

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

一、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; } }