第 436 场周赛-20250209
中国时间：2025-02-09 10:30，1 小时 30 分
https://leetcode.cn/contest/weekly-contest-436/
3446.按对角线进行矩阵排序
implementation, https://leetcode.cn/problems/sort-matrix-by-diagonals/
给你一个大小为 n x n 的整数方阵 grid。返回一个经过如下调整的矩阵：
- 左下角三角形（包括中间对角线）的对角线按 非递增顺序 排序。
- 右上角三角形 的对角线按 非递减顺序 排序。
示例 1：
输入： 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]保持不变。
示例 2：
输入： grid = [[0,1],[1,2]]
输出： [[2,1],[1,0]]
解释：
标有黑色箭头的对角线必须按非递增顺序排序，因此 [0, 2] 变为 [2, 0]。其他对角线已经符合要求。
示例 3：
输入： grid = [[1]]
输出： [[1]]
解释：
只有一个元素的对角线已经符合要求，因此无需修改。
提示：
grid.length == grid[i].length == n1 <= n <= 10-10^5 <= grid[i][j] <= 10^5
from typing import List
from collections import defaultdict
class Solution:
def sortMatrix(self, grid: List[List[int]]) -> List[List[int]]:
n = len(grid)
dia_mx = defaultdict(list)
for i in range(n):
for j in range(n):
dia_mx[i - j].append(grid[i][j])
for key, _ in dia_mx.items():
if key < 0:
dia_mx[key].sort()
else:
dia_mx[key].sort(reverse=True)
for i in range(n):
for j in range(n):
grid[i][j] = dia_mx[i - j].pop(0)
return grid
if __name__ == "__main__":
sol = Solution()
grid = [[1,7,3],[9,8,2],[4,5,6]]
print(sol.sortMatrix(grid))3447.将元素分配给有约束条件的组
https://leetcode.cn/problems/assign-elements-to-groups-with-constraints/
给你一个整数数组 groups，其中 groups[i] 表示第 i 组的大小。另给你一个整数数组 elements。
请你根据以下规则为每个组分配 一个 元素：
- 如果
groups[i]能被elements[j]整除，则元素j可以分配给组i。 - 如果有多个元素满足条件，则分配下标最小的元素
j。 - 如果没有元素满足条件，则分配 -1 。
返回一个整数数组 assigned，其中 assigned[i] 是分配给组 i 的元素的索引，若无合适的元素，则为 -1。
注意：一个元素可以分配给多个组。
示例 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 。
示例 2：
输入： groups = [2,3,5,7], elements = [5,3,3]
输出： [-1,1,0,-1]
解释：
elements[1] = 3被分配给组 1。elements[0] = 5被分配给组 2。- 无法为组 0 和组 3 分配任何元素，分配 -1 。
示例 3：
输入： groups = [10,21,30,41], elements = [2,1]
输出： [0,1,0,1]
解释：
elements[0] = 2 被分配给所有偶数值的组，而 elements[1] = 1 被分配给所有奇数值的组。
提示：
1 <= groups.length <= 10^51 <= elements.length <= 10^51 <= groups[i] <= 10^51 <= elements[i] <= 10^5
如果 max_group 非常大（例如接近 10^5），预处理部分可能会成为性能瓶颈。此时可以考虑以下优化：
- 限制预处理范围:
- 只预处理
groups中实际出现的数，而不是所有数到max_group。 - 使用一个哈希表记录
groups中出现的数，然后只对这些数进行预处理。
- 只预处理
- 分解因数:
- 对于每个
groups[i]，分解其因数，然后检查这些因数是否在elements中。 - 这种方法适合
groups[i]较小的情况。
- 对于每个
from typing import List
import math
class Solution:
def assignElements(self, groups: List[int], elements: List[int]) -> List[int]:
# 将 elements 转换为集合，方便快速查找
element_set = set(elements)
# 记录每个 elements[j] 的最小索引
element_index = {}
for j, elem in enumerate(elements):
if elem not in element_index:
element_index[elem] = j
assigned = []
for group in groups:
# 找到 group 的所有因数
factors = set()
for i in range(1, int(math.sqrt(group)) + 1):
if group % i == 0:
factors.add(i)
factors.add(group // i)
# 找到满足条件的最小 j
min_j = -1
for factor in sorted(factors):
if factor in element_index:
if min_j == -1 or element_index[factor] < min_j:
min_j = element_index[factor]
assigned.append(min_j)
return assigned
# 测试代码
if __name__ == "__main__":
sol = Solution()
print(sol.assignElements([10, 21, 30, 41], [2, 1])) # [0, 1, 0, 1]
print(sol.assignElements([8, 4, 3, 2, 4], [4, 2])) # [0, 0, -1, 1, 0]
print(sol.assignElements([2, 3, 5, 7], [5, 3, 3])) # [-1, 1, 0, -1]复杂度分析
- 时间复杂度:
- 分解因数的时间复杂度为
O(sqrt(group))。- 总体时间复杂度为
O(n * sqrt(group))，其中n是groups的长度。- 空间复杂度:
- 使用了一个哈希表记录
elements的索引，空间复杂度为O(m)，其中m是elements的长度。总结
- 如果
groups的最大值较小，推荐使用预处理倍数的方法。- 如果
groups的最大值较大，推荐使用分解因数的方法。- 两种方法都可以有效避免超时问题。
预处理倍数方法超时了。超出时间限制 ，564/ 572 个通过的测试用例。
from typing import List
class Solution:
def assignElements(self, groups: List[int], elements: List[int]) -> List[int]:
max_val = max(groups) # 只需计算到 `groups` 里的最大值
multiple_map = [-1] * (max_val + 1) # 用数组代替哈希表，初始化为 -1
group_set = set(groups) # 仅处理出现在 `groups` 里的数
# 预处理 elements 的所有倍数
for idx, elem in enumerate(elements):
for mul in range(elem, max_val + 1, elem):
if mul in group_set and multiple_map[mul] == -1: # 只记录最小索引
multiple_map[mul] = idx
# 查询 groups[i] 是否有可整除的元素
return [multiple_map[num] for num in groups]
# 测试代码
if __name__ == "__main__":
sol = Solution()
print(sol.assignElements([10, 21, 30, 41], [2, 1])) # [0, 1, 0, 1]
print(sol.assignElements([8, 4, 3, 2, 4], [4, 2])) # [0, 0, -1, 1, 0]
print(sol.assignElements([2, 3, 5, 7], [5, 3, 3])) # [-1, 1, 0, -1]3448.统计可以被最后一个数位整除的子字符串数目
dp, https://leetcode.cn/problems/count-substrings-divisible-by-last-digit/
给你一个只包含数字的字符串 s 。
请你返回 s 的最后一位 不是 0 的子字符串中，可以被子字符串最后一位整除的数目。
子字符串 是一个字符串里面一段连续 非空 的字符序列。
注意：子字符串可以有前导 0 。
示例 1：
输入：s = "12936"
输出：11
解释：
子字符串 "29" ，"129" ，"293" 和 "2936" 不能被它们的最后一位整除，总共有 15 个子字符串，所以答案是 15 - 4 = 11 。
示例 2：
输入：s = "5701283"
输出：18
解释：
子字符串 "01" ，"12" ，"701" ，"012" ，"128" ，"5701" ，"7012" ，"0128" ，"57012" ，"70128" ，"570128" 和 "701283" 都可以被它们最后一位数字整除。除此以外，所有长度为 1 且不为 0 的子字符串也可以被它们的最后一位整除。有 6 个这样的子字符串，所以答案为 12 + 6 = 18 。
示例 3：
输入：s = "1010101010"
输出：25
解释：
只有最后一位数字为 '1' 的子字符串可以被它们的最后一位整除，总共有 25 个这样的字符串。
提示：
1 <= s.length <= 10^5s只包含数字。
主要思想：
优化： 由于直接遍历所有子字符串会导致时间复杂度过高，使用余数来优化，只需要关注每个子字符串的余数是否能被它的最后一位整除，从而避免了计算整个数的整除问题。
class Solution:
def countSubstrings(self, s: str) -> int:
ans = 0
f = [[0] * 9 for _ in range(10)]
for d in map(int, s):
for m in range(1, 10): # 枚举模数 m
# 滚动数组计算 f
nf = [0] * m
nf[d % m] = 1
for rem in range(m): # 枚举模 m 的余数 rem
nf[(rem * 10 + d) % m] += f[m][rem] # 刷表法
f[m] = nf
# 以 s[i] 结尾的，模 s[i] 余数为 0 的子串个数
ans += f[d][0]
return ans超出时间限制683 / 699 个通过的测试用例
class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
count = 0
# 遍历所有可能的最后一位
for j in range(n):
last_digit = int(s[j])
if last_digit == 0:
continue
# 遍历所有可能的起点
num = 0
for i in range(j, -1, -1):
num += int(s[i]) * (10 ** (j - i))
if num % last_digit == 0:
count += 1
return count
# 测试代码
if __name__ == '__main__':
s = Solution()
print(s.countSubstrings("12936")) # 输出: 11
print(s.countSubstrings("5701283")) # 输出: 18
print(s.countSubstrings("1010101010")) # 输出: 253449.最大化游戏分数的最小值
binary search + greedy, https://leetcode.cn/problems/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 里面最小值 最大 为多少。
示例 1：
输入：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 。
示例 2：
输入：points = [1,2,3], m = 5
输出：2
解释：
一开始，下标 i = -1 且 gameScore = [0, 0, 0] 。
| 移动 | 下标 | gameScore |
|---|---|---|
增加 i | 0 | [1, 0, 0] |
增加 i | 1 | [1, 2, 0] |
减少 i | 0 | [2, 2, 0] |
增加 i | 1 | [2, 4, 0] |
增加 i | 2 | [2, 4, 3] |
gameScore 中的最小值为 2 ，这是所有方案中可以得到的最大值，所以返回 2 。
提示：
2 <= n == points.length <= 5 * 10^41 <= points[i] <= 10^61 <= m <= 10^9
问题解读
题目要求我们在最多 m 次操作内，通过移动下标并累加 points 数组中的值到 gameScore 数组中，使得最终 gameScore 数组中的最小值最大化。
代码作者：灵茶山艾府 链接：https://leetcode.cn/problems/maximize-the-minimum-game-score/solutions/3068672/er-fen-da-an-cong-zuo-dao-you-tan-xin-py-3bhl/
class Solution:
def maxScore(self, points: List[int], m: int) -> int:
def check(low: int) -> bool:
n = len(points)
rem = m
pre = 0
for i, p in enumerate(points):
k = (low - 1) // p + 1 - pre # 还需要操作的次数
if i == n - 1 and k <= 0: # 最后一个数已经满足要求
break
if k < 1:
k = 1 # 至少要走 1 步
rem -= k * 2 - 1 # 左右横跳
if rem < 0:
return False
pre = k - 1 # 右边那个数顺带操作了 k-1 次
return True
left = 0
right = (m + 1) // 2 * min(points) + 1
while left + 1 < right:
mid = (left + right) // 2
if check(mid):
left = mid
else:
right = mid
return left时间复杂度分析
- 二分查找部分
left和right的范围是O(m * min(points))，但二分查找让搜索减少为O(log(m * min(points)))。check(low)的执行
- 需要遍历
points一遍，复杂度O(n)。总复杂度：
O(nlog(m⋅min(points)))
这比暴力枚举所有可能的
low值 快很多，特别是当m很大时。总结
- 该算法使用 二分查找 + 贪心 。
- 二分查找 用于寻找最大可能的
maxScore。- 贪心策略 (
check) 用于判断在m步内是否能让points中的最小值达到low。- 优化点：
check(low)通过左右横跳方式减少不必要的操作，保证m步内的最大化。- 避免暴力搜索，将问题缩小到
O(n log m)的范围，提高效率。