一题选手，后三题大概都知道用什么方法，但是都不熟（好吧，题库那么多标签，熟练掌握的其实没几个），这场周赛就是催我赶紧 查缺补漏 的~ 😂
第二题 一开始抱着侥幸的心理用暴力，果不其然超时了，然后想着应该用 二维前缀和/差分 进行优化，我熟悉一维的，但是二维的不熟；😂
第三题 应该是 滑窗，可惜我没滑出来；😂
第四题 应该是 树形 DP/记忆化搜索，可惜我不会写 DFS（DP 写不出来，暂时就算了），怪我排斥 递归，平时做题能用 BFS/并查集 的，绝不写 DFS ~ 😂
总结，这是一场很好的 查缺补漏周赛，下周把 滑窗 和 DFS 的漏洞修复了吧~ 🤣
评论区有同学说，第二题的三重暴力循环用 Java 可以过，试了一下确实可以过。不过我又试了一下 n = 500，queries.length = 10_000 的极端用例，Java……它也超时了~ 😂
生成测试用例：
Python
Python
queries = []
for i in range(400, 500):
for j in range(400, 500):
queries.append([0, 0, i, j])
print(ques)
希望官方把这个测试用例加上~ 🤣
附代码
Python
class Solution:
def differenceOfSum(self, nums: List[int]) -> int:
sum1, sum2 = sum(nums), 0
for num in nums:
for d in str(num):
sum2 += int(d)
return abs(sum1 - sum2)
T2. 2536. 子矩阵元素加 1
好吧，第二题 用 一维差分 也可以做，怪自己当时没多想~ 😂
执行用时：2464 ms, 在所有 Python3 提交中击败了 5.01% 的用户
内存消耗：39.1 MB, 在所有 Python3 提交中击败了 17.91% 的用户Python
class DiffArray(object):
def __init__(self, nums: List[int]) -> None:
# 预处理计算差分数组
self.n = len(nums)
self.diff = [0] * self.n
self.diff[0] = nums[0]
for i in range(1, self.n):
self.diff[i] = nums[i] - nums[i - 1]
# 闭区间 [left, right] 所有元素 + val (可负)
def increment_range(self, left: int, right: int, val: int):
self.diff[left] += val
if right + 1 < self.n:
self.diff[right + 1] -= val
def result(self) -> List[int]:
# 根据差分数组构造结果数组
res = [0] * self.n
res[0] = self.diff[0]
for i in range(1, self.n):
res[i] = res[i - 1] + self.diff[i]
return res
class Solution:
def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:
diffs = {r: DiffArray([0] * n) for r in range(n)}
for r1, c1, r2, c2 in queries:
for r in range(r1, r2 + 1):
diffs[r].increment_range(c1, c2, 1)
return [diffs[r].result() for r in range(n)]
T3. 2537. 统计好子数组的数目
Python
# 暂无Python
# 暂无评论 (72)
