Q1、leetcode.cn/problems/sort-matrix-by-diagonals/description/" rel="nofollow">按对角线进行矩阵排序

1、题目描述

给你一个大小为 n x n 的整数方阵 grid。返回一个经过如下调整的矩阵：

• 左下角三角形（包括中间对角线）的对角线按 非递增顺序 排序。
• 右上角三角形 的对角线按 非递减顺序 排序。

2、解题思路

遍历所有对角线：

• 主对角线及以下的对角线：从 (i,0) 开始遍历 (i=0,1,...,n-1)，这些对角线需要降序排序。
• 主对角线右侧的对角线：从 (0,j) 开始遍历 (j=1,2,...,n-1)，这些对角线需要升序排序。

对每条对角线进行排序：

• 提取当前对角线的所有元素存入数组 v。
• 按照题目要求对 v 进行排序。
• 按照对角线的顺序，将排序后的 v 放回 grid。

3、代码实现

class Solution {
public:vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {int n = grid.size(); // 矩阵大小// 处理左下角三角形 (含主对角线) :非递增排序for (int i = 0; i < n; ++i) {sortDiagonal(grid, i, 0, false);}// 处理右上角三角形: 非递减排序for (int j = 1; j < n; ++j) {sortDiagonal(grid, 0, j, true);}return grid;}private:/*** @brief 对矩阵的某条对角线进行排序** @param grid 矩阵* @param row  当前对角线起点的行索引* @param col  当前对角线起点的列索引* @param increasing 是否升序排序（true: 升序, false: 降序）*/void sortDiagonal(vector<vector<int>>& grid, int row, int col, bool increasing) {int n = grid.size();vector<int> v; // 存储对角线元素int i = row, j = col;// 收集当前对角线上的所有元素while (i < n && j < n) {v.push_back(grid[i++][j++]);}// 按照要求排序if (increasing) {sort(v.begin(), v.end()); // 升序排序} else {sort(v.rbegin(), v.rend()); // 降序排序}// 将排序后的元素放回原来的对角线位置i = row, j = col;int idx = 0;while (i < n && j < n) {grid[i++][j++] = v[idx++];}}
};

4、复杂度分析

时间复杂度分析：

• 总共有 2n-1 条对角线，每条对角线至多 n 个元素。
• 每条对角线排序需要 O(n log n)，所以总的时间复杂度为 O(n² log n)。

Q2、leetcode.cn/problems/assign-elements-to-groups-with-constraints/description/" rel="nofollow">将元素分配给有约束条件的组

1、题目描述

给你一个整数数组 groups，其中 groups[i] 表示第 i 组的大小。另给你一个整数数组 elements。

请你根据以下规则为每个组分配 一个 元素：

• 如果 groups[i] 能被 elements[j] 整除，则元素 j 可以分配给组 i。
• 如果有多个元素满足条件，则分配下标最小的元素 j 。
• 如果没有元素满足条件，则分配 -1 。

返回一个整数数组 assigned，其中 assigned[i] 是分配给组 i 的元素的索引，若无合适的元素，则为 -1。

**注意：**一个元素可以分配给多个组。

2、解题思路

预处理 elements：

• 记录 元素值 val 的最小索引 j，使用 unordered_map<int, int> 存储 {元素值 -> 最小索引}。
• 用 set<int> 维护所有可用 elements。

遍历 groups，查找可整除元素的最小索引：

• 优化方式：只检查 groups[i] 的 所有因数（因数成对出现）。
• 在 set<int> 里查找因数 d 和 groups[i] / d，找到最小索引。

时间复杂度分析：

• 预处理 elements：O(m)。
• 遍历 groups：O(n * sqrt(groups[i]))，因数分解至多 sqrt(groups[i]) 次。
• 总复杂度：约 O(n log max(groups[i]) + m)，可接受。

3、代码实现

class Solution {
public:vector<int> assignElements(vector<int>& groups, vector<int>& elements) {int n = groups.size();int m = elements.size();vector<int> ret(n, -1); // 结果数组, 初始值为 -1unordered_map<int, int> elementIndex; // 记录元素值 -> 最小索引set<int> elementSet;                  // 记录所有可用的元素值// 预处理 elements, 记录每个元素的最小索引for (int j = 0; j < m; ++j) {if (elementIndex.find(elements[j]) == elementIndex.end()) {elementIndex[elements[j]] = j; // 只存最小索引}elementSet.insert(elements[j]); // 记录存在的元素}// 遍历 groups, 寻找最小可用元素索引for (int i = 0; i < n; ++i) {int minIndex = -1; // 记录当前 groups[i] 可选元素的最小索引// 枚举 groups[i] 的因数 dfor (int d = 1; d * d <= groups[i]; ++d) {if (groups[i] % d == 0) {// 可能的两个因数: d 和 groups[i] / dint factor1 = d, factor2 = groups[i] / d;// 检查因数 factor1 是否在元素集中, 更新最小索引if (elementSet.count(factor1) &&(minIndex == -1 || elementIndex[factor1] < minIndex)) {minIndex = elementIndex[factor1];}// 检查因数 factor2// 是否在元素集中, 更新最小索引 (避免重复检查相等因数)if (factor1 != factor2 && elementSet.count(factor2) &&(minIndex == -1 || elementIndex[factor2] < minIndex)) {minIndex = elementIndex[factor2];}}}ret[i] = minIndex; // 存储当前组的最优元素索引}return ret;}
};

4、复杂度分析

步骤	操作	时间复杂度
预处理 elements	存入 unordered_map & set	O(m)
遍历 groups	O(n)
计算 groups[i] 的所有因数	O(sqrt(groups[i]))
查找因数是否存在	O(1)
总复杂度	O(n log max(groups[i]) + m)

Q3、leetcode.cn/problems/count-substrings-divisible-by-last-digit/description/" rel="nofollow">统计可以被最后一个数位整除的子字符串数目

1、题目描述

给你一个只包含数字的字符串 s 。

请你返回 s 的最后一位 不是 0 的子字符串中，可以被子字符串最后一位整除的数目。

子字符串 是一个字符串里面一段连续 非空 的字符序列。

**注意：**子字符串可以有前导 0 。

2、解题思路

维护 remainderCount 结构

• remainderCount[mod][rem] 记录当前处理到的前缀中，对 mod 取模后余数为 rem 的子串个数。

遍历字符串 s

• 逐个处理字符 digit，它可以作为新子串的起点，也可以扩展已有子串。
• 对 mod = 1 到 9 进行遍历：
  • 计算 digit % mod，即 digit 本身作为单个子串的余数。
  • 对于已有的前缀余数 rem，计算新的 newRem = (rem * 10 + digit) % mod，并更新 remainderCount[mod]。
  • 统计 digit 作为子串结尾且余数 0 的情况，加到 totalCount。

时间复杂度

• 由于 mod 只有 1~9，每次更新 O(9)，整体复杂度 O(9 * n) ≈ O(n)，可以高效处理较长字符串。

3、代码实现

class Solution {
public:long long countSubstrings(string s) {long long totalCount = 0;array<int, 9> remainderCount[10]{}; // 记录模 1~9 下的余数分布// 遍历字符串中的每个数字for (char ch : s) {int digit = ch - '0'; // 当前数字// 计算所有 1~9 的模数for (int mod = 1; mod <= 9; mod++) {array<int, 9> newCount{};  // 存储新的余数分布newCount[digit % mod] = 1; // 单独当前字符作为子串// 遍历当前模数 mod 下所有可能的余数for (int rem = 0; rem < mod; rem++) {int newRem = (rem * 10 + digit) % mod; // 计算新的余数newCount[newRem] += remainderCount[mod][rem]; // 更新计数}// 更新模 mod 的余数统计remainderCount[mod] = newCount;}// 统计以当前 digit 结尾的符合条件的子串数量totalCount += remainderCount[digit][0];}return totalCount;}
};

4、复杂度分析

操作	复杂度
遍历字符串	O(n)
遍历 mod = 1~9	O(9)
遍历 rem = 0~mod	O(9)
总复杂度	O(9 * n) ≈ O(n)

Q4、leetcode.cn/problems/maximize-the-minimum-game-score/description/" rel="nofollow">最大化游戏分数的最小值

1、题目描述

给你一个长度为 n 的数组 points 和一个整数 m 。同时有另外一个长度为 n 的数组 gameScore ，其中 gameScore[i] 表示第 i 个游戏得到的分数。一开始对于所有的 i 都有 gameScore[i] == 0 。

你开始于下标 -1 处，该下标在数组以外（在下标 0 前面一个位置）。你可以执行 至多 m 次操作，每一次操作中，你可以执行以下两个操作之一：

• 将下标增加 1 ，同时将 points[i] 添加到 gameScore[i] 。
• 将下标减少 1 ，同时将 points[i] 添加到 gameScore[i] 。

注意，在第一次移动以后，下标必须始终保持在数组范围以内。

请你返回 至多 m 次操作以后，gameScore 里面最小值 最大 为多少。

2、解题思路

(1) 采用二分查找

我们要找到最大的 minScore，使得 gameScore 的最小值至少是 minScore。由于 minScore 取值范围较大，我们可以 二分查找 这个值。

为什么可以用二分查找？

• minScore 设定得越高，满足条件的难度就越大。
• 我们可以通过一个 canAchieve(minScore) 函数来验证是否能在 m 次操作内实现 gameScore[i] >= minScore。

(2) 设计 canAchieve(minScore) 检查函数

对于 canAchieve(minScore)，我们的目标是检查 是否可以通过最多 m 次操作，使得所有 gameScore[i] 至少为 minScore。

核心逻辑

1. 遍历数组 points，计算需要的步数 stepsNeeded：

   • 如果 gameScore[i] 需要至少达到 minScore，那么 stepsNeeded 至少为：

     ​ $$\text{stepsNeeded}=\frac{\text{minScore}+\text{points}[i]-1}{\text{points}[i]}$$

   • 这里是 (minScore + points[i] - 1) / points[i]，是为了确保 上取整 计算 stepsNeeded。

2. 考虑 m 次操作是否足够

   • 每次向前移动 1 次后可以返回，因此每个 stepsNeeded 会消耗 $2\times \text{stepsNeeded}-1$ 次操作。
   • 如果 remainingMoves < 0，说明 m 次操作不够，返回 false。

(3) 二分查找 minScore 的最大值

• left = 0，right = (m + 1) / 2 * *min_element(points.begin(), points.end()) + 1：
  • right 设定为 points 数组中最小元素乘 (m+1)/2，这是最极端情况下 minScore 可能达到的最大值。
• 通过二分查找找到最大的 minScore 使 canAchieve(minScore) == true。

3、代码实现

class Solution {
public:long long maxScore(vector<int>& points, int m) {// 二分查找检查函数, 判断是否能达到 minScoreauto canAchieve = [&](long long minScore) -> bool {int n = points.size(), remainingMoves = m, prevSteps = 0;for (int i = 0; i < n; i++) {// 计算需要多少次操作, 使 gameScore[i] >= minScoreint stepsNeeded =(minScore + points[i] - 1) / points[i] - prevSteps;// 最后一个元素已经满足if (i == n - 1 && stepsNeeded <= 0) {break;}stepsNeeded = max(stepsNeeded, 1); // 至少要前进 1 步// 计算所需的操作次数remainingMoves -= 2 * stepsNeeded - 1; // 左右横跳操作if (remainingMoves < 0) {return false; // 操作次数不够}prevSteps = stepsNeeded - 1; // 预留下一次操作}return true;};// 设定二分查找的搜索范围long long left = 0;long long right = 1LL * (m + 1) / 2 * *min_element(points.begin(), points.end()) + 1;while (left + 1 < right) {long long mid = left + (right - left) / 2;if (canAchieve(mid)) {left = mid; // 尝试更大的 minScore} else {right = mid; // 降低 minScore}}return left;}
};

4、复杂度分析

• 二分查找部分：O(log V)，其中 V 是 right 的初始值，大约是 O(log(m))。
• canAchieve() 计算：O(n)，因为我们需要遍历 points 数组。
• 整体复杂度：O(n log m)，对于 n = 10^5，m = 10^9 级别的数据，依然可以接受。