題目列表

3446. 按對(duì)角線進(jìn)行矩陣排序
3447. 將元素分配給有約束條件的組
3448. 統(tǒng)計(jì)可以被最后一個(gè)數(shù)位整除的子字符串?dāng)?shù)目
3449. 最大化游戲分?jǐn)?shù)的最小值

一、按對(duì)角線進(jìn)行矩陣排序

直接模擬，遍歷每一個(gè)斜對(duì)角線，獲取斜對(duì)角線上的數(shù)字，排序后重新賦值即可。

這里教大家一個(gè)從右上角往左下角依次遍歷斜對(duì)角線的方法，對(duì)于每一條對(duì)角線上的任意元素 $grid[i][j]$，我們會(huì)發(fā)現(xiàn) $i?j$ 為一個(gè)定值，以 $3\times 3$ 的矩陣為例，從右上角往左下角 $i?j$ 分別為 $?2,?1,0,1,2$，只要加上一個(gè)偏移量 $3$，就會(huì)變成 $1,2,3,4,5$

由此可以推導(dǎo)出一個(gè)公式，對(duì)于一個(gè) $n\times m$ 的矩陣，令 $k=m+i?j$，讓 $k=1,2,...,n+m?1$，可以依次遍歷每一條斜對(duì)角線，其中 $i\in [0,n?1]，j=m+i?k$

代碼如下

// C++
class Solution {
public:vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {int n = grid.size(), m = grid[0].size();// 令 k = m - j + i => j = m - k + i , i = k - m + j// 當(dāng) i = 0 時(shí)，j = m - k// 當(dāng) i = n - 1 時(shí)，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); // 注意越界vector<int> 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, n+m):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(reverse=min_j==0)for j, val in zip(range(min_j, max_j + 1), res):grid[k - m + j][j] = valreturn grid

二、將元素分配給有約束條件的組

我們可以優(yōu)先計(jì)算出 $elements$ 中數(shù)字的倍數(shù)情況，存放在 $f[x]$ 中，$f[x]=i$ 表示 $x$ 能被 $elements[i]$ 整除，如果有多個(gè) $i$ 符合條件，取最左邊的那個(gè)，然后根據(jù) $f[x]$ 中的結(jié)果給 $groups$ 中的數(shù)進(jìn)行賦值即可，具體操作見代碼，如下

// C++
class Solution {
public:vector<int> assignElements(vector<int>& groups, vector<int>& elements) {int n = groups.size(), m = elements.size();int mx = ranges::max(groups);vector<int> f(mx + 1, -1);// 時(shí)間復(fù)雜度分析// 當(dāng)elements=[1,2,3,...,x]時(shí)，達(dá)到最壞時(shí)間復(fù)雜度//  mx/1+mx/2+...+mx/x//= mx(1+1/2+1/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;}}}vector<int> 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, mx+1, x):if f[j] < 0:f[j] = ireturn [f[x] for x in groups]

三、統(tǒng)計(jì)可以被最后一個(gè)數(shù)位整除的子字符串?dāng)?shù)目

題目思路：

• 由于最后一位數(shù)的取值為 $1$~$9$，我們可以分別統(tǒng)計(jì)以這些數(shù)為結(jié)尾的數(shù)字對(duì)答案的貢獻(xiàn)

• 假設(shè)我們計(jì)算以 $x$ 為結(jié)尾的數(shù)字對(duì)答案的貢獻(xiàn)

  • 對(duì)于前 $i$ 個(gè)字符組成的數(shù)字 $S_{i?1}$，加上當(dāng)前數(shù)字 $s_i$，它的取模結(jié)果為 $(S_{i?1}\times 10+s_i)\%x=((S_{i?1}\times 10)\%x+s_i)\%x=((S_{i?1}\%x)\times 10+s_i)\%x$
  • 從式子中我們可以看出，我們其實(shí)并不需要關(guān)心數(shù)字 $S_{i?1}$ 具體是多少，我們只要知道 $S_{i?1}\%x$ 的結(jié)果即可
  • 設(shè) $f[i][j]$ 表示數(shù)字 $S_i$ 模 $x$ 后結(jié)果為 $j$ 的所有數(shù)字個(gè)數(shù)
    • $f[i][(j\times 10+s_i)\%x]+$$=f[i?1][j]$，$j\in [0,x)$，$s_i$ 和前面的 $S_{i?1}$ 合起來作為一個(gè)數(shù)
    • $f[i][s_i\%x]+$$=1$，$s_i$ 單獨(dú)作為一個(gè)數(shù)
  • 當(dāng) $s_i=x$ 時(shí)，將 $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, vector<LL>(x));for(int i = 0; i < n; i++){int y = s[i] - '0';for(int j = 0; j < x; j++){f[i+1][(j*10+y)%x] += f[i][j];}f[i+1][y%x]++;if(y == x) ans += f[i+1][0];}}return ans;}
};
// 空間優(yōu)化
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<LL> f(x);for(int i = 0; i < n; i++){vector<LL> t(x);int y = s[i] - '0';for(int j = 0; j < x; j++){t[(j*10+y)%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*10+y)%x] += f[j]t[y%x] += 1f = tif x == y: ans += f[0]return ans

四、最大化游戲分?jǐn)?shù)的最小值

最大化最小值，顯然用二分來做。

• 是否具有單調(diào)性？顯然具備，因?yàn)?$gameScor{e}_{min}$ 越大，則每個(gè)下標(biāo)位 $+$$=points[i]$ 的操作次數(shù)就會(huì)變多，則總操作數(shù)就會(huì)更容易超過 $m$，故可以用二分
• $check$ 函數(shù)如何寫？這里有個(gè)結(jié)論：對(duì)于任意一種下標(biāo)移動(dòng)順序，都能變成若干組左右來回橫跳的形式。所以我們可以貪心的讓左邊的下標(biāo)先滿足條件，然后再考慮后面的位置，即我們先考慮通過 $0\to 1、1\to 0$ 讓 $0$ 先滿足條件，在用 讓 $1$ 滿足條件，同樣的方式讓 依次滿足條件，看總操作次數(shù)是否 $>m$

代碼如下

// C++
class Solution {
using LL = long long;
public:long long maxScore(vector<int>& 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 位置，進(jìn)行反復(fù)橫跳之后，對(duì) i 位置已經(jīng)進(jìn)行的 += points[i] 操作次數(shù)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 移動(dòng)到 i，需要至少 1 次操作s -= 2 * (ops - 1) + 1;if(s < 0) return false;pre = ops - 1;}return true;};// (m + 1)/2 表示只有兩個(gè)數(shù)時(shí)，第一個(gè)數(shù)進(jìn)行的操作次數(shù)，這里我們默認(rèn)將最小值放在這一位，得到一個(gè)上限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