淘宝客网站搭建教程,网页设计导航栏素材,新乡seo,网站项目遇到的问题题目列表
3446. 按对角线进行矩阵排序 3447. 将元素分配给有约束条件的组 3448. 统计可以被最后一个数位整除的子字符串数目 3449. 最大化游戏分数的最小值
一、按对角线进行矩阵排序 直接模拟#xff0c;遍历每一个斜对角线#xff0c;获取斜对角线上的数字#xff0c;排…题目列表
3446. 按对角线进行矩阵排序 3447. 将元素分配给有约束条件的组 3448. 统计可以被最后一个数位整除的子字符串数目 3449. 最大化游戏分数的最小值
一、按对角线进行矩阵排序 直接模拟遍历每一个斜对角线获取斜对角线上的数字排序后重新赋值即可。
这里教大家一个从右上角往左下角依次遍历斜对角线的方法对于每一条对角线上的任意元素 g r i d [ i ] [ j ] grid[i][j] grid[i][j]我们会发现 i − j i-j i−j 为一个定值以 3 × 3 3\times 3 3×3 的矩阵为例从右上角往左下角 i − j i-j i−j 分别为 − 2 , − 1 , 0 , 1 , 2 -2,-1,0,1,2 −2,−1,0,1,2只要加上一个偏移量 3 3 3就会变成 1 , 2 , 3 , 4 , 5 1,2,3,4,5 1,2,3,4,5
由此可以推导出一个公式对于一个 n × m n\times m n×m 的矩阵令 k m i − j kmi-j kmi−j让 k 1 , 2 , . . . , n m − 1 k1,2,...,nm-1 k1,2,...,nm−1可以依次遍历每一条斜对角线其中 i ∈ [ 0 , n − 1 ] j m i − k i\in [0,n-1]jmi-k i∈[0,n−1]jmi−k
代码如下
// C
class Solution {
public:vectorvectorint sortMatrix(vectorvectorint 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); // 注意越界vectorint 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, nm):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(reversemin_j0)for j, val in zip(range(min_j, max_j 1), res):grid[k - m j][j] valreturn grid二、将元素分配给有约束条件的组 我们可以优先计算出 e l e m e n t s elements elements 中数字的倍数情况存放在 f [ x ] f[x] f[x] 中 f [ x ] i f[x]i f[x]i 表示 x x x 能被 e l e m e n t s [ i ] elements[i] elements[i] 整除如果有多个 i i i 符合条件取最左边的那个然后根据 f [ x ] f[x] f[x] 中的结果给 g r o u p s groups groups 中的数进行赋值即可具体操作见代码如下
// C
class Solution {
public:vectorint assignElements(vectorint groups, vectorint elements) {int n groups.size(), m elements.size();int mx ranges::max(groups);vectorint f(mx 1, -1);// 时间复杂度分析// 当elements[1,2,3,...,x]时达到最坏时间复杂度// mx/1mx/2...mx/x// mx(11/21/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;}}}vectorint 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, mx1, x):if f[j] 0:f[j] ireturn [f[x] for x in groups]三、统计可以被最后一个数位整除的子字符串数目 题目思路 由于最后一位数的取值为 1 1 1~ 9 9 9我们可以分别统计以这些数为结尾的数字对答案的贡献 假设我们计算以 x x x 为结尾的数字对答案的贡献 对于前 i i i 个字符组成的数字 S i − 1 S_{i-1} Si−1加上当前数字 s i s_i si它的取模结果为 ( S i − 1 × 10 s i ) % x ( ( S i − 1 × 10 ) % x s i ) % x ( ( S i − 1 % x ) × 10 s i ) % x (S_{i-1} \times 10 s_i)\%x((S_{i-1} \times 10)\%xs_i)\%x((S_{i-1}\%x) \times 10s_i)\%x (Si−1×10si)%x((Si−1×10)%xsi)%x((Si−1%x)×10si)%x从式子中我们可以看出我们其实并不需要关心数字 S i − 1 S_{i-1} Si−1 具体是多少我们只要知道 S i − 1 % x S_{i-1}\%x Si−1%x 的结果即可设 f [ i ] [ j ] f[i][j] f[i][j] 表示数字 S i S_i Si 模 x x x 后结果为 j j j 的所有数字个数 f [ i ] [ ( j × 10 s i ) % x ] f[i][(j\times10s_i)\%x]\ f[i][(j×10si)%x] f [ i − 1 ] [ j ] f[i-1][j] f[i−1][j] j ∈ [ 0 , x ) j\in[0,x) j∈[0,x) s i s_i si 和前面的 S i − 1 S_{i-1} Si−1 合起来作为一个数 f [ i ] [ s i % x ] f[i][s_i\%x]\ f[i][si%x] 1 1 1 s i s_i si 单独作为一个数 当 s i x s_ix six 时将 f [ i ] [ 0 ] f[i][0] 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, vectorLL(x));for(int i 0; i n; i){int y s[i] - 0;for(int j 0; j x; j){f[i1][(j*10y)%x] f[i][j];}f[i1][y%x];if(y x) ans f[i1][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){vectorLL f(x);for(int i 0; i n; i){vectorLL t(x);int y s[i] - 0;for(int j 0; j x; j){t[(j*10y)%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*10y)%x] f[j]t[y%x] 1f tif x y: ans f[0]return ans四、最大化游戏分数的最小值 最大化最小值显然用二分来做。
是否具有单调性显然具备因为 g a m e S c o r e m i n gameScore_{min} gameScoremin 越大则每个下标位 p o i n t s [ i ] points[i] points[i] 的操作次数就会变多则总操作数就会更容易超过 m m m故可以用二分 c h e c k check check 函数如何写这里有个结论对于任意一种下标移动顺序都能变成若干组左右来回横跳的形式。所以我们可以贪心的让左边的下标先满足条件然后再考虑后面的位置即我们先考虑通过 0 → 1 、 1 → 0 0 \rightarrow 1、1 \rightarrow 0 0→1、1→0 让 0 0 0 先满足条件在用 1 → 2 、 2 → 1 1 \rightarrow 2、2 \rightarrow 1 1→2、2→1 让 1 1 1 满足条件同样的方式让 2 、 3 、 . . . 、 n − 1 2、3、...、n-1 2、3、...、n−1 依次满足条件看总操作次数是否 m m m
代码如下
// C
class Solution {
using LL long long;
public:long long maxScore(vectorint 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
