@TOC1.本周周赛总结，感觉自己又回来了。最后一道题，图论，真的不会，就算打死。赛后看了大佬的解说，抄了大佬的代码。我大概明白了，但如果给我一个新问题，我可能无法解决。你必须练习。2.【易】6101.判断一个矩阵是否为X矩阵链接：6101.判断一个矩阵是否为X矩阵1.题目描述判断一个矩阵是否为X矩阵难度：Easy如果a方阵满足以下所有条件，则称它为X矩阵：矩阵对角线上的所有元素都不为0，矩阵中的所有其他元素都为0。这将得到一个大小为nxn的二维整数数组网格，表示一个方阵。如果网格是X矩阵，则为真；否则，假的。示例1：输入：grid=[[2,0,0,1],[0,3,1,0],[0,5,2,0],[4,0,0,2]]输出：true解释：矩阵如上所示。X矩阵应该是绿色元素（对角线上）都不是0，所有红色元素都是0。因此，grid是一个X矩阵。示例2：输入：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<=1052。易于分析和评分想法。可以根据题目的意思来模拟一下。3.代码实现类解决方案：defcheckXMatrix(self,grid:List[List[int]])->bool:m,n=len(grid),len(grid[0])foriinrange(m):对于jinrange(n)：如果i==j且grid[i][j]==0：返回False如果i+j==m-1且grid[i][j]==0：返回Falseifnot(i==jori+j==m-1)andgrid[i][j]!=0:returnFalsereturnTrue3.[Medium]6100.链接统计放置房屋的方式数:6100.统计放置房屋的方式数1.题目描述统计放置房屋方式的难度：一条中等街道上有n*2个地块，街道两边有n个地块。每边的地块从1到n编号。每个地块上都可以放置一座房子。现在要求街道的同一侧不能有两栋房子相邻。请计算并返回放置房屋的方式数。由于答案可能很大，因此在返回之前需要对109+7取模。请注意，如果将房屋放置在街道一侧的第i个地块上，则不会影响房屋在街道另一侧的第i个地块上的放置。示例1：输入：n=1输出：4解释：可能的布局：1.并非所有地块上都有房屋。2.房子放在街道的一侧。3.房子放在街道的另一边。4.放置两栋房子，街道两边各一栋。示例2：输入：n=2输出：9解释：如上图所示，有9个可能的展示位置。提示：1<=n<=1042。思考分析和评分中等。其实是个斐波那契数列，游戏的时候没看到，写了个记忆搜索，反正也过了。道路两边没有相互制约，两边的条件其实是一样的，算作一边再平方。第0块地只有一个方法，就是不放手。如果第i块地是自己放出来的，只能从前一块地没有放出来的情况下转让；如果不是自己释放，前一块地可以释放也可以不释放。3.代码实现类解决方案：defcountHousePlacements(self,n:int)->int:mod=10**9+7defq_pow(base,power):res=1whilepower>0:ifpower&1==1:res=res*base%modpower>>=1base=base*base%modreturnres%mod@cachedefdfs(i,has):如果i==0:return1ans=dfs(i-1,False)如果没有:ans+=dfs(i-1,True)returnans%modret=(dfs(n-1,False)+dfs(n-1,True))%modreturnret*ret%mod4,[Hard]5229.拼接数组最高分链接：5229.拼接数组最高分1.题目描述拼接数组最高分难度：难度给你两个整数下标从0开始的数组nums1和nums2，长度均为n。您可以选择两个整数left和right，其中0<=left<=rightint:n=len(nums1)defmax_subarr(nums1,nums2):s2=sum(nums2)diff=[nums1[i]-nums2[i]foriinrange(n)]foriinrange(1,n):ifdiff[i-1]>0:diff[i]+=diff[i-1]returns2+max(0,max(diff))returnmax(max_subarr(nums1,nums2),max_subarr(nums2,nums1))V.[难]6103。从树链接中删除边的最低分数：6103。最低分数forRemovingEdgesfromaTree1.题目描述MinimumScoreforRemovingEdgesfromaTree难度：难度有一棵无向连通树，树有n个节点，编号从0到n-1，n-1条边。给定一个从0开始的整数数组nums，长度为n，其中nums[i]表示第i个节点的值。您还将获得长度为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：输入：nums=[1,5,5,4,11],edges=[[0,1],[1,2],[1,3],[3,4]]输出：9解释：上图显示了一种边删除方案。-第一个组件的节点是[1,3,4]并且值为[5,4,11]。XOR值为5^4^11=10。-第二个组件的节点是[0]并且值为[1]。XOR值为1=1。-第3个组件的节点是[2]，值为[5]。XOR值为5=5。分数是最大XOR值和最小XOR值之间的差，即10-1=9。可以看出，没有得分小于9的边缘去除方案。示例2：输入：nums=[5,5,2,4,4,2],edges=[[0,1],[1,2],[5,2],[4,3],[1,3]]输出：0解释：上图显示了一种边删除方案。-第一个组件的节点是[3,4]并且值为[4,4]。XOR值为4^4=0。-第二个组件的节点是[1,0]并且值为[5,5]。XOR值为5^5=0。-第3个分量的节点是[2,5]，值为[2,2]。XOR值为2^2=0。分数是最大异或值和最小异或值之差，0-0=0。无法得到小于0的小数0。提示：n==nums.length3<=n<=10001<=nums[i]<=108edges.length==n-1edges[i].length==20<=ai,biint:n,m=len(nums),len(edges)graph=defaultdict(list)foru,vinedges:graph[u].append(v)graph[v].append(u)clock=0xor=[0]*n#以i=[0为根的子树的XOR和_in]*n_out=[0]*n#返回以u为根的子树的异或和。查询时，father为u的父节点。#同时计算u的进出时间戳defdfs(u,father):nonlocalclockclock+=1_in[u]=clockxor[u]=nums[u]forvingraph[u]:ifv!=father:xor[u]^=dfs(v,u)_out[u]=clockreturnxor[u]dfs(0,-1)#u是v的老节点defis_parent(u,v):return_in[u]<=_in[v]<=_out[u]#给定节点调整每条边的前后，让长辈在前#等于边方向foreinedges:ifnotis_parent(e[0],e[1]):e[0],e[1]=e[1],e[0]ans=inffor(u1,v1),(u2,v2)incombinations(edges,2):ifis_parent(v2,u1):#边j是边i的长辈，从下到上三个子树的异或和分别为v1,v2-v1,root-v2a,b,c=xor[v1],xor[v2]^xor[v1],xor[0]^xor[v2]elifis_parent(v1,u2):#i边是j边的长辈，三个子树的异或和从下到上是v1,v1-v2,root-v1a,b,c=xor[v2],xor[v1]^xor[v2],xor[0]^xor[v1]else:#i,jhave无长辈关系（属于子树），三部分分别是v1,v2,root-v1-v2a,b,c=xor[v1],xor[v2],xor[0]^xor[v1]^xor[v2]ans=min(ans,max(a,b,c)-min(a,b,c))ifans==0:return0returnans6.参考链接灵题解法：DFS时间戳-处理树的强大工具以上问题（Python/Java/C++/Go）人生苦短，我用Python！
