欢迎大家加QQ群：623375442，可以方便群里面交流。第四题不会做，下午看看怎么更新一下。
Q1. Sort Matrix by Diagonals
给你一个大小为 n x n 的整数方阵 grid。返回一个经过如下调整的矩阵：
- 左下角三角形（包括中间对角线）的对角线按 非递增顺序 排序。
- 右上角三角形 的对角线按 非递减顺序 排序。
测试样例：
输入：grid = [[1,7,3],[9,8,2],[4,5,6]]
输出：[[8,2,3],[9,6,7],[4,5,1]]
解释：标有黑色箭头的对角线（左下角三角形）应按非递增顺序排序：
- [1, 8, 6] 变为 [8, 6, 1]。
- [9, 5] 和 [4] 保持不变。
- [7, 2] 变为 [2, 7]。
- [3] 保持不变。
解答：暴力计算。
class Solution {
public int[][] sortMatrix(int[][] grid) {
int x = grid.length - 1, y = 0;
while (y != grid[0].length) {
List<Integer> buffer = new ArrayList<>();
{
int xt = x, yt = y;
while (xt >= 0 && xt < grid.length && yt >= 0 && yt < grid[0].length) {
buffer.add(grid[xt][yt]);
xt += 1;
yt += 1;
}
}
if (y <= 0) {
Collections.sort(buffer, (a, b) -> (b.compareTo(a)));
} else {
Collections.sort(buffer);
}
{
int xt = x, yt = y, p = 0;
while (xt >= 0 && xt < grid.length && yt >= 0 && yt < grid[0].length) {
grid[xt][yt] = buffer.get(p++);
xt += 1;
yt += 1;
}
}
--x;
if (x == -1) {
x = 0;
y += 1;
}
}
return grid;
}
}Q2. Assign Elements to Groups with Constraints
给你一个整数数组 groups，其中 groups[i] 表示第 i 组的大小。另给你一个整数数组 elements。
请你根据以下规则为每个组分配 一个 元素：
- 如果 groups[i] 能被 elements[j] 整除，则元素 j 可以分配给组 i。
- 如果有多个元素满足条件，则分配下标最小的元素 j 。
- 如果没有元素满足条件，则分配 -1 。
返回一个整数数组 assigned，其中 assigned[i] 是分配给组 i 的元素的索引，若无合适的元素，则为 -1。
注意：一个元素可以分配给多个组。
测试样例：
输入：groups = [8,4,3,2,4], elements = [4,2]
输出：[0,0,-1,1,0]
解释：
- elements[0] = 4 被分配给组 0、1 和 4。
- elements[1] = 2 被分配给组 3。
- 无法为组 2 分配任何元素，分配 -1 。
解答：数据范围不大，所以对每个数字开根暴力检索。
class Solution {
public int[] assignElements(int[] groups, int[] elements) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < elements.length; ++i) {
if (!map.containsKey(elements[i])) map.put(elements[i], i);
}
int[] res = new int[groups.length];
for (int i = 0; i < groups.length; ++i) {
res[i] = Integer.MAX_VALUE;
for (int j = 1; j * j <= groups[i]; ++j) {
if (groups[i] % j == 0) {
res[i] = Math.min(res[i], map.getOrDefault(j, Integer.MAX_VALUE));
res[i] = Math.min(res[i], map.getOrDefault(groups[i] / j, Integer.MAX_VALUE));
}
}
res[i] = res[i] == Integer.MAX_VALUE ? -1 : res[i];
}
return res;
}
}Q3. Count Substrings Divisible By Last Digit
给你一个只包含数字的字符串 s 。
请你返回 s 的最后一位 不是 0 的子字符串中，可以被子字符串最后一位整除的数目。
子字符串 是一个字符串里面一段连续 非空 的字符序列。
注意：子字符串可以有前导 0 。
测试样例：
输入：s = "12936"
输出：11
解释：子字符串 "29" ，"129" ，"293" 和 "2936" 不能被它们的最后一位整除，总共有 15 个子字符串，所以答案是 15 - 4 = 11 。
解答：利用前缀快速检索可以整除的数字。
class Solution {
public long countSubstrings(String s) {
int[] mods = new int[10];
int[][] counts = new int[10][10];
for (int i = 1; i <= 9; ++i) {
counts[i][0] = 1;
}
long res = 0;
for (int i = 0; i < s.length(); ++i) {
int t = s.charAt(i) - '0';
int[][] nextCounts = new int[10][10];
for (int j = 1; j <= 9; ++j) {
for (int k = 0; k < j; ++k) {
nextCounts[j][(k * 10) % j] += counts[j][k];
}
}
counts = nextCounts;
for (int j = 1; j <= 9; ++j) {
mods[j] = (mods[j] * 10 + t) % j;
if (j == t) {
res += counts[j][mods[j]];
}
counts[j][mods[j]] += 1;
}
}
return res;
}
}补充一个Rust版本。
impl Solution {
pub fn count_substrings(s: String) -> i64 {
let mut res: i64 = 0;
let s_arr = s.as_bytes();
let mut mod_results = [0 as usize;10];
let mut counts = [[0 as i64;10];10];
for i in 1..=9 {
counts[i][0] = 1;
}
for c in s_arr {
let n = *c as usize - 48;
let mut next_counts = [[0 as i64;10];10];
for i in 1..=9 {
for j in 0..i {
next_counts[i][j * 10 % i] += counts[i][j];
}
}
counts = next_counts;
for i in 1..=9 {
mod_results[i] = (mod_results[i] * 10 + n) % i;
if i == n {
res += counts[i][mod_results[i]];
}
counts[i][mod_results[i]] += 1;
}
}
res
}
}Q4. Maximize the Minimum Game Score
给你一个长度为 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 里面最小值 最大 为多少。
测试样例：
输入：points = [2,4], m = 3
输出：4
解释：一开始，下标 i = -1 且 gameScore = [0, 0].
移动 下标 gameScore 增加 i 0 [2, 0] 增加 i 1 [2, 4] 减少 i 0 [4, 4] gameScore 中的最小值为 4 ，这是所有方案中可以得到的最大值，所以返回 4 。
解答：能猜到是二分，但是没想到怎么迭代计算。先抄个答案，下午看看。
class Solution {
boolean judge(int[] points, long m, long tgt) {
long cur = 0L;
long nxt = 0L;
int n = points.length;
for (int i = 0; i < n; i++) {
if (i == n - 1 && nxt >= tgt) {
return true;
}
m--;
cur = nxt + points[i];
nxt = 0;
if (cur < tgt) {
long req = (tgt - cur - 1) / points[i] + 1;
if (i < n - 1) {
nxt = points[i + 1] * req;
}
m = m - req * 2;
}
if (m < 0) {
return false;
}
}
return true;
}
public long maxScore(int[] points, int m) {
long x = 0L;
long y = 10000000L * m;
while (x < y - 1) {
long mid = (x + y) / 2;
if (judge(points, m, mid)) {
x = mid;
} else {
y = mid - 1;
}
}
while (judge(points, m, x + 1)) {
x++;
}
return x;
}
}补充一个Rust版本
impl Solution {
pub fn max_score(points: Vec<i32>, m: i32) -> i64 {
let m = m as i64;
let mut st: i64 = 0;
let mut ed: i64 = *points.iter().min().unwrap() as i64 * m + 1;
while st + 1 < ed {
let mid = (st + ed) / 2;
if Self::is_valid(&points, mid, m) {
st = mid;
} else {
ed = mid;
}
}
st
}
fn is_valid(points: &Vec<i32>, tgt: i64, m: i64) -> bool {
let mut left: i64 = m;
let mut pre: i64 = 0;
for i in 0..points.len() {
let p = points[i] as i64;
let mut k = (tgt - 1) / p + 1 - pre;
if i == points.len() - 1 && k <= 0 {
break;
}
k = k.max(1);
left -= k * 2 - 1;
if left < 0 {
return false;
}
pre = k - 1;
}
true
}
}