LeetCode-第370场周赛

Author： yfx
发布时间：November 5, 2023
436 views
No comments
5955 words
Categories：算法 Python

<div class="tip share">请注意，本文编写于 567 天前，最后修改于 560 天前，其中某些信息可能已经过时。</div>

# Problem A - [找到冠军 I](https://leetcode.cn/problems/find-champion-i/description/)

## 方法一：思维

> 题意理解：
>
> $grid[i][j]=1$ 表示 $i$ 队比 $j$ 队强。
>
> 分析：
>
> 根据题意可知，第 $j$ 列如果没有1那么就没有队伍比 $j$ 队强，符合题意直接返回即可

### 比赛中代码：

<div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-04648b36f38f672ff8d4ac89dcf2a69d26" aria-expanded="true"><div class="accordion-toggle"><span style="">**Python3**</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-04648b36f38f672ff8d4ac89dcf2a69d26" class="collapse collapse-content"><p></p>

```python
class Solution:
    def findChampion(self, grid: List[List[int]]) -> int:
        n = len(grid)
        for i in range(n):
            cnt = 0
            for j in range(n):
                if i == j:
                    continue
                if grid[i][j] == 1:
                    cnt += 1
            if cnt + 1 == n:
                return i
        return 0
```

### 赛后优化代码：

<div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-ad1ca9c5256164ab7026e87543e471e6560' role="tab" data-target='#tabs-ad1ca9c5256164ab7026e87543e471e6560'>**Python3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-ad1ca9c5256164ab7026e87543e471e6560' class="tab-pane fade active in">

```python
class Solution:
    def findChampion(self, grid: List[List[int]]) -> int:
        for j, col in enumerate(zip(*grid)):
            if 1 not in col[:j] + col[j + 1:]:
                return j
```

ps:*grid表示把第第一维去掉，把第二维变成一个可迭代对象。
</div>
</div>
</div>

## 复杂度分析

* 时间复杂度：$O(n^2)$，其中$n$为$grid$的长度。
* 空间复杂度：$O(1)$。

# Problem B - [找到冠军 II](https://leetcode.cn/problems/find-champion-ii/)

## 方法一：思维

> 题意理解：
>
> $edges[i]=[u,v]$：表示 $u$ 队比 $v$ 队强，需要找到没有对手的队伍，如果不存在，那么返回 $-1$。
>
> 分析：
>
> 只要枚举哪个队伍没有出现在 $v$ 的位置则表明没有队伍比它强。

### 比赛中代码：

<div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-c4437668c71009fcdaba91239fa2265d87" aria-expanded="true"><div class="accordion-toggle"><span style="">**Python3**</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-c4437668c71009fcdaba91239fa2265d87" class="collapse collapse-content"><p></p>

```python
class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        g = [[] for i in range(n)]
        for u, v in edges:
            g[u].append(v)
  
        def dfs(node):
            nonlocal ans
            vis[node] = True
            ans += 1
            for son in g[node]:
                if not vis[son]:
                    dfs(son)
  
        for i in range(n):
            vis = [False] * n
            ans = 0
            dfs(i)
            if ans == n:
                return i
        return -1
```

### 赛后优化代码：

<div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-f73b6e360c5223befd94eecfaa573910570' role="tab" data-target='#tabs-f73b6e360c5223befd94eecfaa573910570'>**Python3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-f73b6e360c5223befd94eecfaa573910570' class="tab-pane fade active in">

```python
class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        weak = [False] * n
        for _, y in edges:
            weak[y] = True
        ans = -1
        for i, w in enumerate(weak):
            if not w:
                if ans != -1:
                    return -1
                ans = i
        return ans
```

~~ps：比赛中想的复杂了，着急了。思路>代码~~

</div>
</div>
</div>

### 复杂度分析

* 时间复杂度：$O(n + m)$，其中 $n$ 为队伍数量，$m$ 为边的数量。
* 空间复杂度：$O(1)$。

# Problem C - [在树上执行操作以后得到的最大分数](https://leetcode.cn/problems/maximum-score-after-applying-operations-on-a-tree/description/)

## 方法一：树形DP

> 题意理解：
>
> 可从树上选取部分点，使得取出的点对应值的和最大，且取出的点其树上对应的值变为0。但需保证取点后，根节点到任一叶节点的路径和大于0。
>
> 分析：
>
> 正难则反，一颗树的总值是固定的，题目要求最大获得值即求最少损失值。
>
> 设当前节点为 $x$，计算以 $x$ 为根的子树是健康时，失去的最小分数。那么本题的答案就是 $values$ 的元素和，减去「以 $0$ 为根的子树是健康时，失去的最小分数」。
>
> 用「选或不选」分类讨论：
>
> 不选 $values[x]$，那么它的所有子孙节点都可以选，失去的最小分数就是 $values[x]$。
> 选 $values[x]$，问题变成「以 $y$ 为根的子树是健康时，失去的最小分数」，这里 $y$ 是 $x 的儿子。如果有多个儿子，累加失去的最小分数。
> 这两种情况取最小值。
>
> 特别地，如果 $x$ 是叶子节点，如果以叶子节点为根节点的树要健康，那么只能不选，直接返回 $values[x]$。
>
> 代码实现时，为了方便判断 $x$ 是否为叶子节点，可以假设还有一条 $0$ 到 $-1$ 的边，这样不会误把根节点 $0$ 当作叶子。

### 赛后优化代码：

<div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-29a7128d0de0059f74fad878775a850490' role="tab" data-target='#tabs-29a7128d0de0059f74fad878775a850490'>**Python 3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-29a7128d0de0059f74fad878775a850490' class="tab-pane fade active in">

```python
class Solution:
    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:
        n = len(edges) + 1
        g = [[] for _ in range(n)]
        # g[0].append(-1)  # 避免误把根节点当作叶子
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)

# dfs(node, father) 计算以 node 为根的子树是健康时，失去的最小分数
        @cache
        def dfs(node=0, father=-1) -> int:
            if node != 0 and len(g[node]) == 1: # node不是根节点是叶子节点
                return values[node]
            loss = 0 # 不选values[node]
            for son in g[node]:
                if son != father:
                    loss += dfs(son, node) # 计算以 son 为根的子树是健康时，失去的最小分数
            return min(values[node], loss) # 选/不选 values[node]，取最小损失
        return sum(values) - dfs() # 总和去掉以0为根的树的最小损失值
```

~~ps：正难则反！！！！~~

</div>
</div>
</div>

# Problem D - [平衡子序列的最大和](https://leetcode.cn/problems/maximum-balanced-subsequence-sum/)

## 方法一：思维+树状数组

> 题意理解：
>
> 给定一个数组 $nums$，找到一组子序列 $nums[i_1], nums[i_2] ... nums[i_n]$ 使得任意 $i,j(i_1\leqslant i<j\leqslant i_n)$ 满足 $nums[j] - nums[i] \geqslant j - i$。求所有满足条件的子序列和的最大值。
>
> 分析：
>
> 上述条件可以转化成 $nums[j] - i \geqslant nums[i] - i$，我们令$b[i] = nums[i] - i$，则原问题即转化成在数组 $b$ 中找到非降子序列对应 $nums[i]$ 的和的最大值。
> 如果 $nums[i]$ 为序列中最后一个元素，那么如果有 $b[j]\leqslant b[i]$，那么就找到了子问题：序列中的最后一个元素为 $nums[j]$时，对应序列和的最大值。
> 我们可定义 $f[i]$ 表示以 $nums[i]$ 为最后一个元素时，可获得的最大序列和。那么本题的答案即为 $max(f)$。
> 状态转移方程为：$f[i] = \max\limits_j(max(f[j], 0)) + nums[i], (0\leqslant j<i,b[j]\leqslant b[i])$
> 其中如果 $f[j]$ 为负数那么不选，因为我们选了 $nums[i]$，所以前面所有元素可全不选。
> 对于 $f[i]$ 需要最大的 $f[j]$ 进行状态转移且 $j\leqslant i$，则相当于求 $f[i]$ 的前缀最大值，这里可用树状数组优化，使得 $f[j]$ 的获取时间复杂度优化为 $log n$
> 需要对数组 $b$ 进行离散化。

### 参考代码：

<div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-3cdeaeb18dac1520bd4f1c725b4ec2b9260' role="tab" data-target='#tabs-3cdeaeb18dac1520bd4f1c725b4ec2b9260'>**Python3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-3cdeaeb18dac1520bd4f1c725b4ec2b9260' class="tab-pane fade active in">

```python
# 树状数组模板（维护前缀最大值）
class BIT:
    def __init__(self, n):
        self.tree = [-inf] * n
  
    def update(self, i: int, val: int) -> None:
        while i < len(self.tree):
            self.tree[i] = max(self.tree[i], val)
            i += i & -i
  
    def pre_max(self, i: int) -> int:
        mx = -inf
        while i > 0:
            mx = max(mx, self.tree[i])
            i &= i - 1
        return mx

class Solution:
    def maxBalancedSubsequenceSum(self, nums: List[int]) -> int:
        b = sorted(set(num - i for i, num in enumerate(nums))) # 离散化 nums[i]-i，方便使用树状数组
        t = BIT(len(b) + 1)
        ans = -inf
        for i, x in enumerate(nums):
            j = bisect_left(b, x - i) + 1 # 树状数组下标需要从1开始
            f = max(t.pre_max(j), 0) + nums[i]
            ans = max(ans, f)
            t.update(j, f)
        return ans
```

</div>
</div>
</div>

### 复杂度分析

* 时间复杂度：$O(n\log n)$，其中 $n$ 为数组 $nums$ 的长度。
* 空间复杂度：$O(n)$

Last modification：November 12, 2023

看着给点？(●'◡'●)？

LeetCode-第370场周赛

yfx • 2023 年 11 月 05 日

<div class="tip share">请注意，本文编写于 567 天前，最后修改于 560 天前，其中某些信息可能已经过时。</div>

# Problem A - [找到冠军 I](https://leetcode.cn/problems/find-champion-i/description/)

## 方法一：思维

### 比赛中代码：

### 赛后优化代码：

ps:*grid表示把第第一维去掉，把第二维变成一个可迭代对象。
</div>
</div>
</div>

## 复杂度分析

* 时间复杂度：$O(n^2)$，其中$n$为$grid$的长度。
* 空间复杂度：$O(1)$。

# Problem B - [找到冠军 II](https://leetcode.cn/problems/find-champion-ii/)

## 方法一：思维

### 比赛中代码：

### 赛后优化代码：

<div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-f73b6e360c5223befd94eecfaa573910570' role="tab" data-target='#tabs-f73b6e360c5223befd94eecfaa573910570'>**Python3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-f73b6e360c5223befd94eecfaa573910570' class="tab-pane fade active in">

~~ps：比赛中想的复杂了，着急了。思路>代码~~

</div>
</div>
</div>

### 复杂度分析

* 时间复杂度：$O(n + m)$，其中 $n$ 为队伍数量，$m$ 为边的数量。
* 空间复杂度：$O(1)$。

# Problem C - [在树上执行操作以后得到的最大分数](https://leetcode.cn/problems/maximum-score-after-applying-operations-on-a-tree/description/)

## 方法一：树形DP

### 赛后优化代码：

<div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-29a7128d0de0059f74fad878775a850490' role="tab" data-target='#tabs-29a7128d0de0059f74fad878775a850490'>**Python 3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-29a7128d0de0059f74fad878775a850490' class="tab-pane fade active in">

~~ps：正难则反！！！！~~

</div>
</div>
</div>

# Problem D - [平衡子序列的最大和](https://leetcode.cn/problems/maximum-balanced-subsequence-sum/)

## 方法一：思维+树状数组

### 参考代码：

<div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-3cdeaeb18dac1520bd4f1c725b4ec2b9260' role="tab" data-target='#tabs-3cdeaeb18dac1520bd4f1c725b4ec2b9260'>**Python3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-3cdeaeb18dac1520bd4f1c725b4ec2b9260' class="tab-pane fade active in">

</div>
</div>
</div>

### 复杂度分析

* 时间复杂度：$O(n\log n)$，其中 $n$ 为数组 $nums$ 的长度。
* 空间复杂度：$O(n)$

LeetCode-第370场周赛

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

本站Handsoem主题的美化教程

宝塔网站nginx反向代理避坑

纪元1800.DLC完全解锁补丁【正版适用】-2023.11.14

LeetCode-高效制胜-两数之和

LeetCode-高效制胜-两数之和 II - 输入有序数组

LeetCode-最短无序连续子数组

LeetCode-第253场周赛

Windows配置pip国内镜像——加速下载速度

LeetCode-第372场周赛

PyCharm设置Python文件头部模板信息

LeetCode-第370场周赛

Leave a Comment Cancel reply 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

LeetCode-第370场周赛

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款