共计 6325 个字符，预计需要花费 16 分钟才能阅读完成。
@TOC
一、本周周赛总结
- 再次感觉到本人的菜。
- 最初一题图论，是真的不会，打死都不会。
- 赛后看大佬解说，照着大佬代码复写，大略了解了，然而再给我一道新题，预计还是做不进去。
- 得练。
二、[Easy] 6101. 判断矩阵是否是一个 X 矩阵
链接: 6101. 判断矩阵是否是一个 X 矩阵
1. 题目形容
- 判断矩阵是否是一个 X 矩阵
难度：简略
如果一个正方形矩阵满足下述 全副 条件，则称之为一个 X 矩阵：
- 矩阵对角线上的所有元素都 不是 0
- 矩阵中所有其余元素都是 0
给你一个大小为 n x n 的二维整数数组 grid，示意一个正方形矩阵。如果 grid 是一个 X 矩阵 ，返回 true；否则，返回 false。
示例 1：
<img style=”width: 311px; height: 320px;” src=”https://assets.leetcode.com/uploads/2022/05/03/ex1.jpg” alt=””>
输出：grid = [[2,0,0,1],[0,3,1,0],[0,5,2,0],[4,0,0,2]]
输入：true
解释：矩阵如上图所示。X 矩阵应该满足：绿色元素（对角线上）都不是 0，红色元素都是 0。因而，grid 是一个 X 矩阵。示例 2：
<img style=”width: 238px; height: 246px;” src=”https://assets.leetcode.com/uploads/2022/05/03/ex2.jpg” alt=””>
输出：grid = [[5,7,0],[0,3,1],[0,5,0]]
输入：false
解释：矩阵如上图所示。X 矩阵应该满足：绿色元素（对角线上）都不是 0，红色元素都是 0。因而，grid 不是一个 X 矩阵。提醒：
n == grid.length == grid[i].length3 <= n <= 1000 <= gridi <= 105
2. 思路剖析
定级 Easy。
按题意模仿即可。
3. 代码实现
class Solution:
def checkXMatrix(self, grid: List[List[int]]) -> bool:
m,n = len(grid),len(grid[0])
for i in range(m):
for j in range(n):
if i == j and grid[i][j] == 0:
return False
if i+j == m-1 and grid[i][j] == 0:
return False
if not (i==j or i+j==m-1) and grid[i][j] != 0:
return False
return True三、[Medium] 6100. 统计搁置房子的形式数
链接: 6100. 统计搁置房子的形式数
1. 题目形容
- 统计搁置房子的形式数
难度：中等
一条街道上共有 n * 2 个 地块，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都能够搁置一所房子。
现要求街道同一侧不能存在两所房子相邻的状况，请你计算并返回搁置屋宇的形式数目。因为答案可能很大，须要对 109 + 7 取余后再返回。
留神，如果一所房子搁置在这条街某一侧上的第 i 个地块，不影响在另一侧的第 i 个地块搁置房子。
示例 1：
输出：n = 1
输入：4
解释：可能的搁置形式：1. 所有地块都不搁置房子。2. 一所房子放在街道的某一侧。3. 一所房子放在街道的另一侧。4. 搁置两所房子，街道两侧各搁置一所。示例 2：
<img style=”width: 500px; height: 500px;” src=”https://assets.leetcode.com/uploads/2022/05/12/arrangements.png” alt=””>
输出：n = 2
输入：9
解释：如上图所示，共有 9 种可能的搁置形式。提醒：
1 <= n <= 104
2. 思路剖析
定级 Medium。
- 理论是斐波那契数列，较量时没看进去，写了记忆化搜寻，反正也过了。
- 路线两边没有相互限度，而且两边状况理论雷同，因而算一边，而后平方即可。
- 第 0 块地，只有 1 种办法，就是不放。
- 第 i 块地，如果本人放，只能从上块地不放的状况转移过去；如果本人不放，上块地能够放或不放。
3. 代码实现
class Solution:
def countHousePlacements(self, n: int) -> int:
mod = 10**9+7
def q_pow(base, power):
res = 1
while power > 0:
if power & 1 == 1:
res = res * base % mod
power >>= 1
base = base * base % mod
return res % mod
@cache
def dfs(i,has):
if i == 0:
return 1
ans = dfs(i-1,False)
if not has:
ans += dfs(i-1,True)
return ans % mod
ret = (dfs(n-1,False) + dfs(n-1,True)) %mod
return ret*ret%mod四、[Hard] 5229. 拼接数组的最大分数
链接: 5229. 拼接数组的最大分数
1. 题目形容
- 拼接数组的最大分数
难度：艰难
给你两个下标从 0 开始的整数数组 nums1 和 nums2，长度都是 n。
你能够抉择两个整数 left 和 right，其中 0 <= left <= right < n，接着 替换 两个子数组 nums1[left...right] 和 nums2[left...right]。
- 例如，设
nums1 = [1,2,3,4,5]和nums2 = [11,12,13,14,15]，整数抉择left = 1和right = 2，那么nums1会变为[1,12,13,4,5]而nums2会变为[11,2,3,14,15]。
你能够抉择执行上述操作 一次 或不执行任何操作。
数组的 分数 取 sum(nums1) 和 sum(nums2) 中的最大值，其中 sum(arr) 是数组 arr 中所有元素之和。
返回 可能的最大分数。
子数组 是数组中间断的一个元素序列。arr[left...right] 示意子数组蕴含 nums 中下标 left 和 right 之间的元素（含 下标 left 和 right 对应元素）。
示例 1：
输出：nums1 = [60,60,60], nums2 = [10,90,10]
输入：210
解释：抉择 left = 1 和 right = 1，失去 nums1 = [60,90,60] 和 nums2 = [10,60,10]。分数为 max(sum(nums1), sum(nums2)) = max(210, 80) = 210。示例 2：
输出：nums1 = [20,40,20,70,30], nums2 = [50,20,50,40,20]
输入：220
解释：抉择 left = 3 和 right = 4，失去 nums1 = [20,40,20,40,20] 和 nums2 = [50,20,50,70,30]。分数为 max(sum(nums1), sum(nums2)) = max(140, 220) = 220。示例 3：
输出：nums1 = [7,11,13], nums2 = [1,1,1]
输入：31
解释：抉择不替换任何子数组。分数为 max(sum(nums1), sum(nums2)) = max(31, 3) = 31。提醒：
n == nums1.length == nums2.length1 <= n <= 1051 <= nums1[i], nums2[i] <= 104
2. 思路剖析
定级 Hard。
这题看起来唬人，理论能够转化成一个简略题。
- 咱们假如指标是从 nums1 中找一段给 nums2，使 s2=nums2 最大，设这一段为区间[l,r]。
- 那么 s2 将会变成 s2-nums[l,r]+nums1[l,r]。即 s2+diff[l,r],diff[i]=nums1[i]-nums2[i]
- diff 能够用 O(n) 解决进去，问题转化成，寻找 diff 中最大子串和。
- 这是一道简略的 dp 入门题，也是我的入坑题。
- 最初，咱们别离探讨从 nums1 给 nums2，和从 num2 给 num1 的状况，取 max 即可。
- 非凡的，这题能够不转化，那么加 max(diff)的时候, 正数置 0.
3. 代码实现
class Solution:
def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:
n = len(nums1)
def max_subarr(nums1,nums2):
s2 = sum(nums2)
diff = [nums1[i]-nums2[i] for i in range(n)]
for i in range(1,n):
if diff[i-1] >0 :
diff[i] += diff[i-1]
return s2 + max(0,max(diff))
return max(max_subarr(nums1,nums2),max_subarr(nums2,nums1))五、[Hard] 6103. 从树中删除边的最小分数
链接: 6103. 从树中删除边的最小分数
1. 题目形容
- 从树中删除边的最小分数
难度：艰难
存在一棵无向连通树，树中有编号从 0 到 n - 1 的 n 个节点，以及 n - 1 条边。
给你一个下标从 0 开始的整数数组 nums，长度为 n，其中 nums[i] 示意第 i 个节点的值。另给你一个二维整数数组 edges，长度为 n - 1，其中 edges[i] = [ai, bi] 示意树中存在一条位于节点 ai 和 bi 之间的边。
删除树中两条 不同 的边以造成三个连通组件。对于一种删除边计划，定义如下步骤以计算其分数：
- 别离获取三个组件 每个 组件中所有节点值的异或值。
- 最大 异或值和 最小 异或值的 差值 就是这一种删除边计划的分数。
- 例如，三个组件的节点值别离是：
[4,5,7]、[1,9]和[3,3,3]。三个异或值别离是4 ^ 5 ^ 7 = 6、1 ^ 9 = 8和3 ^ 3 ^ 3 = 3。最大异或值是8，最小异或值是3，分数是8 - 3 = 5。
返回在给定树上执行任意删除边计划可能的 最小 分数。
示例 1：
<img style=”width: 193px; height: 190px;” src=”https://assets.leetcode.com/uploads/2022/05/03/ex1drawio.png” alt=””>
输出：nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]]
输入：9
解释：上图展现了一种删除边计划。- 第 1 个组件的节点是 [1,3,4]，值是 [5,4,11]。异或值是 5 ^ 4 ^ 11 = 10。- 第 2 个组件的节点是 [0]，值是 [1]。异或值是 1 = 1。- 第 3 个组件的节点是 [2]，值是 [5]。异或值是 5 = 5。分数是最大异或值和最小异或值的差值，10 - 1 = 9。能够证实不存在分数比 9 小的删除边计划。示例 2：
<img style=”width: 287px; height: 150px;” src=”https://assets.leetcode.com/uploads/2022/05/03/ex2drawio.png” alt=””>
输出：nums = [5,5,2,4,4,2], edges = [[0,1],[1,2],[5,2],[4,3],[1,3]]
输入：0
解释：上图展现了一种删除边计划。- 第 1 个组件的节点是 [3,4]，值是 [4,4]。异或值是 4 ^ 4 = 0。- 第 2 个组件的节点是 [1,0]，值是 [5,5]。异或值是 5 ^ 5 = 0。- 第 3 个组件的节点是 [2,5]，值是 [2,2]。异或值是 2 ^ 2 = 0。分数是最大异或值和最小异或值的差值，0 - 0 = 0。无奈取得比 0 更小的分数 0。提醒：
n == nums.length3 <= n <= 10001 <= nums[i] <= 108edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != biedges示意一棵无效的树
2. 思路剖析
定级 Hard。
这题真的难啊！
不会做啊！
题解都看不懂啊！
最初照着大佬代码复写硬啃才过的。
- 因为异或的性质，咱们无奈剪枝，即：枚举两条边，只能用 O(n^2)来做，且列举所有删除后，三局部的异或和来更新答案。
- 题目数据范畴是 1000，枚举曾经 n^2 了，因而咱们须要一个 O(1)的办法计算删除两条边后，三局部的异或和。
- 较量时我有用的并查集，总体复杂度是 O(n^3)，不出预料 TLE 了，不过的确不会做，就这么交了也没方法，交着玩呗。
-
正确做法：
- 轻易选一个节点作为根节点(这里选 0)，把这无向图预处理成树，而后预处理每个子树的异或和，记在子树的根上。
- 那么删除两条边后，三局部的异或和都能够通过 O(1)计算出来了。
- 这 2 条边 i,j 别离探讨三种状况：
1) i 是 j 的前辈。
2) j 是 i 的前辈.
3) i,j 没有前辈关系。
4) 参考以下摘录 @灵茶山艾府 大佬的图。
5) 这三种状况下，三局部的异或和都是能够 O(1)计算出来的。
- 那么如何预处理子树异或和以及判断前辈关系呢。
- dfs 解决子树异或和，这个比较简单。
- 前辈关系，波及到一个工夫戳的概念，定义一个全局的计数器，其实就是先根遍历时，节点的拜访程序，用这个工夫戳来记录：
每个节点的进入工夫 in 和退出工夫 out。 - 那么如果 u 是 v 的前辈，则有 _in[u] <= _in[v] <= _out[u]，反之亦然，能够用这个判断。
- 最初还要调整一下边中，给出 u，v 的程序，让前辈在前边，等于给边方向，这样好写。
3. 代码实现
class Solution:
def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:
n,m = len(nums),len(edges)
graph = defaultdict(list)
for u,v in edges:
graph[u].append(v)
graph[v].append(u)
clock = 0
xor = [0] * n # 以 i 为根的子树异或和
_in = [0] * n
_out = [0] * n
# 返回以 u 为根的子树异或和，查问时，father 是 u 的父亲节点。# 同时计算 u 的出入工夫戳
def dfs(u, father):
nonlocal clock
clock += 1
_in[u] = clock
xor[u] = nums[u]
for v in graph[u]:
if v != father:
xor[u] ^= dfs(v,u)
_out[u] = clock
return xor[u]
dfs(0,-1)
# u 是 v 的前辈节点
def is_parent(u,v):
return _in[u] <= _in[v] <= _out[u]
# 对每条边给出节点的前后进行调整，让前辈在前边
# 等于给边方向
for e in edges:
if not is_parent(e[0],e[1]):
e[0],e[1] = e[1],e[0]
ans = inf
for (u1,v1),(u2,v2) in combinations(edges,2):
if is_parent(v2,u1): # j 边是 i 边的前辈，从下往上的三部分子树异或和别离为 v1,v2-v1, 根 -v2
a,b,c = xor[v1],xor[v2]^xor[v1],xor[0]^xor[v2]
elif is_parent(v1,u2): # i 边是 j 边的前辈，从下往上的三部分子树异或和别离为 v1,v1-v2, 根 -v1
a,b,c = xor[v2],xor[v1]^xor[v2],xor[0]^xor[v1]
else: # i,j 没有前辈关系(分属子树), 三局部别离为 v1,v2, 根 -v1-v2
a,b,c = xor[v1],xor[v2],xor[0]^xor[v1]^xor[v2]
ans = min(ans,max(a,b,c)-min(a,b,c))
if ans == 0:
return 0
return ans六、参考链接
- 灵神的题解：DFS 工夫戳——解决树上问题的无力工具（Python/Java/C++/Go）
人生苦短，我用 Python！