深圳做手机网站多少钱,移动互联网 商业模式,装饰网站方案,设计师专业目录 一、3446. 按对角线进行矩阵排序二、3447. 将元素分配给有约束条件的组三、3448. 统计可以被最后一个数位整除的子字符串数目四、3449. 最大化游戏分数的最小值 一、3446. 按对角线进行矩阵排序
题目链接 本题可以暴力枚举#xff0c;在确定了每一个对角线的第一个元素… 目录 一、3446. 按对角线进行矩阵排序二、3447. 将元素分配给有约束条件的组三、3448. 统计可以被最后一个数位整除的子字符串数目四、3449. 最大化游戏分数的最小值 一、3446. 按对角线进行矩阵排序
题目链接 本题可以暴力枚举在确定了每一个对角线的第一个元素下标 ( i , j ) (i,j) (i,j) 后下一个元素的下标就是 ( i 1 , j 1 ) (i1,j1) (i1,j1)即只要同时 i i i j j j就可以枚举该对角线上的元素了。
这里再介绍一种更加简单的做法我们可以定义 k m − ( j − i ) km-(j-i) km−(j−i)画个图理解一下
此时如果我们枚举 j j j那么更据上述公式 i j k − m j m i − k i j k - mjmi-k ijk−mjmi−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-k0)min(mn-1-km-1)] j∈[max(m−k0)min(mn−1−km−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 k1; knm; k){int minJ Math.max(m - k, 0);int maxJ Math.min(m - k n - 1, m - 1);ListInteger res new ArrayList();for(int jminJ; jmaxJ; j){res.add(g[kj-m][j]);}if(n-k0) Collections.sort(res);else Collections.sort(res, (x,y)-y-x);for(int jminJ, i0; jmaxJ; j){ans[kj-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[mx1];Arrays.fill(cnt, -1);//O(nlogn)for(int i0; ie.length; i){int x e[i];if(x mx || cnt[x] ! -1) continue;for(int yx; ymx; yx){if(cnt[y] ! -1) continue;cnt[y] i;}}int[] ans new int[n];for(int i0; in; i){ans[i] cnt[g[i]];}return ans;}
}三、3448. 统计可以被最后一个数位整除的子字符串数目
题目链接 本题主要涉及到取模运算的一个知识点 ( a ∗ 10 b ) % m ( a % m ∗ 10 b ) % m (a*10b)\%m(a\%m*10b)\%m (a∗10b)%m(a%m∗10b)%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[n1][i][j] f[n1][i][j] 统计以 s [ n ] s[n] s[n] 结尾的数中 % i j \%ij %ij 的元素个数。
代码如下
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 i0; in; i){int x s.charAt(i) - 0;long[][] t new long[10][9];for(int j1; j10; j){t[j][x%j] 1;for(int k0; kj; 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] ppoints[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和i1之间左右横跳 从i−1到i需要1次剩下在i和i1之间左右横跳对于 i 1 i1 i1 点来说在计算 i i i 点时就已经操作了 p r e k − 1 prek-1 prek−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)(m1) / 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 i0; in; 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;}
}
