[LeetCode周赛复盘] 第 299 场周赛20220626

@[TOC]([LeetCode周赛复盘] 第 299 场周赛20220626 )

一、本周周赛总结

  • 再次感觉到自己的菜。
  • 最后一题图论,是真的不会,打死都不会。
  • 赛后看大佬讲解,照着大佬代码复写,大概理解了,但是再给我一道新题,估计还是做不出来。
  • 得练。


    在这里插入图片描述

二、 [Easy] 6101. 判断矩阵是否是一个 X 矩阵

链接: 6101. 判断矩阵是否是一个 X 矩阵

1. 题目描述

  1. 判断矩阵是否是一个 X 矩阵

难度:简单

如果一个正方形矩阵满足下述 全部 条件,则称之为一个 X 矩阵

  1. 矩阵对角线上的所有元素都 不是 0
  2. 矩阵中所有其他元素都是 0

给你一个大小为 <code>n x n</code> 的二维整数数组 <code>grid</code> ,表示一个正方形矩阵。如果<em> </em><code>grid</code><em> </em>是一个 **X 矩阵 **,返回 <code>true</code> ;否则,返回 <code>false</code> 。

示例 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 矩阵。

提示:

  • <code>n == grid.length == grid[i].length</code>
  • <code>3 <= n <= 100</code>
  • <code>0 <= grid[i][j] <= 105</code>

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. 题目描述

  1. 统计放置房子的方式数

难度:中等

一条街道上共有 <code>n * 2</code> 个 地块 ,街道的两侧各有 <code>n</code> 个地块。每一边的地块都按从 <code>1</code> 到 <code>n</code> 编号。每个地块上都可以放置一所房子。

现要求街道同一侧不能存在两所房子相邻的情况,请你计算并返回放置房屋的方式数目。由于答案可能很大,需要对 <code>109 + 7</code> 取余后再返回。

注意,如果一所房子放置在这条街某一侧上的第 <code>i</code> 个地块,不影响在另一侧的第 <code>i</code> 个地块放置房子。

示例 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 种可能的放置方式。

提示:

  • <code>1 <= n <= 104</code>

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. 题目描述

  1. 拼接数组的最大分数

难度:困难

给你两个下标从 0 开始的整数数组 <code>nums1</code> 和 <code>nums2</code> ,长度都是 <code>n</code> 。

你可以选择两个整数 <code>left</code> 和 <code>right</code> ,其中 <code>0 <= left <= right < n</code> ,接着 交换 两个子数组 <code>nums1[left...right]</code> 和 <code>nums2[left...right]</code> 。

  • 例如,设 <code>nums1 = [1,2,3,4,5]</code> 和 <code>nums2 = [11,12,13,14,15]</code> ,整数选择 <code>left = 1</code> 和 <code>right = 2</code>,那么 <code>nums1</code> 会变为 <code>[1,<em>12</em>,<em>13</em>,4,5]</code> 而 <code>nums2</code> 会变为 <code>[11,<em>2,3</em>,14,15]</code> 。

你可以选择执行上述操作 一次 或不执行任何操作。

数组的 分数 取 <code>sum(nums1)</code> 和 <code>sum(nums2)</code> 中的最大值,其中 <code>sum(arr)</code> 是数组 <code>arr</code> 中所有元素之和。

返回 可能的最大分数

子数组 是数组中连续的一个元素序列。<code>arr[left...right]</code> 表示子数组包含 <code>nums</code> 中下标 <code>left</code> 和 <code>right</code> 之间的元素(含 下标 <code>left</code> 和 <code>right</code> 对应元素

示例 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 。

提示:

  • <code>n == nums1.length == nums2.length</code>
  • <code>1 <= n <= 105</code>
  • <code>1 <= nums1[i], nums2[i] <= 104</code>

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. 题目描述

  1. 从树中删除边的最小分数

难度:困难

存在一棵无向连通树,树中有编号从 <code>0</code> 到 <code>n - 1</code> 的 <code>n</code> 个节点, 以及 <code>n - 1</code> 条边。

给你一个下标从 0 开始的整数数组 <code>nums</code> ,长度为 <code>n</code> ,其中 <code>nums[i]</code> 表示第 <code>i</code> 个节点的值。另给你一个二维整数数组 <code>edges</code> ,长度为 <code>n - 1</code> ,其中 <code>edges[i] = [ai, bi]</code> 表示树中存在一条位于节点 <code>ai</code> 和 <code>bi</code> 之间的边。

删除树中两条 不同 的边以形成三个连通组件。对于一种删除边方案,定义如下步骤以计算其分数:

  1. 分别获取三个组件 每个 组件中所有节点值的异或值。
  2. 最大 异或值和 最小 异或值的 差值 就是这一种删除边方案的分数。
  • 例如,三个组件的节点值分别是:<code>[4,5,7]</code>、<code>[1,9]</code> 和 <code>[3,3,3]</code> 。三个异或值分别是 <code>4 ^ 5 ^ 7 = <em>6</em></code>、<code>1 ^ 9 = <em>8</em></code> 和 <code>3 ^ 3 ^ 3 = <em>3</em></code> 。最大异或值是 <code>8</code> ,最小异或值是 <code>3</code> ,分数是 <code>8 - 3 = 5</code> 。

返回在给定树上执行任意删除边方案可能的 最小 分数。

示例 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 。

提示:

  • <code>n == nums.length</code>
  • <code>3 <= n <= 1000</code>
  • <code>1 <= nums[i] <= 108</code>
  • <code>edges.length == n - 1</code>
  • <code>edges[i].length == 2</code>
  • <code>0 <= ai, bi < n</code>
  • <code>ai != bi</code>
  • <code>edges</code> 表示一棵有效的树

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

六、参考链接

人生苦短,我用Python!

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 202,406评论 5 475
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 84,976评论 2 379
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 149,302评论 0 335
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,366评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,372评论 5 363
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,457评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,872评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,521评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,717评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,523评论 2 319
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,590评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,299评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,859评论 3 306
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,883评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,127评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,760评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,290评论 2 342

推荐阅读更多精彩内容