leetcode weekly contes 370

本周的题目质量比较高，需要仔细花心思与时间来作对的题目。

100115. 找到冠军 I

一场比赛中共有 n 支队伍，按从 0 到 n - 1 编号。

给你一个下标从 0 开始、大小为 n * n 的二维布尔矩阵 grid 。对于满足 0 <= i, j <= n - 1 且 i != j 的所有 i, j ：如果 grid[i][j] == 1，那么 i 队比 j 队强；否则，j 队比 i 队强。

在这场比赛中，如果不存在某支强于 a 队的队伍，则认为 a 队将会是冠军。

返回这场比赛中将会成为冠军的队伍。

示例 1：

输入：grid = [[0,1],[0,0]]
输出：0
解释：比赛中有两支队伍。
grid[0][1] == 1 表示 0 队比 1 队强。所以 0 队是冠军。

示例 2：

输入：grid = [[0,0,1],[1,0,1],[0,0,0]]
输出：1
解释：比赛中有三支队伍。
grid[1][0] == 1 表示 1 队比 0 队强。
grid[1][2] == 1 表示 1 队比 2 队强。
所以 1 队是冠军。

提示：

n == grid.length
n == grid[i].length
2 <= n <= 100
grid[i][j] 的值为 0 或 1
对于满足 i != j 的所有 i, j ，grid[i][j] != grid[j][i] 均成立
生成的输出满足：如果 a 队比 b 队强，b 队比 c 队强，那么 a 队比 c 队强

地址

https://leetcode.cn/contest/weekly-contest-370/problems/find-champion-i/

题意

模拟

思路

直接检测每一行中是否全部都为 $n - 1$ 时，则表示第 $i$ 队比其他队都强。
复杂度分析：

时间复杂度：$O(n^2)$，其中 $n$ 表示给定的数组的长度。
空间复杂度：$O(1)$。

代码

class Solution:
    def findChampion(self, grid: List[List[int]]) -> int:
        for i in range(len(grid)):
            if sum(grid[i]) == len(grid) - 1:
                return i
        return -1

100116. 找到冠军 II

一场比赛中共有 n 支队伍，按从 0 到 n - 1 编号。每支队伍也是 有向无环图（DAG） 上的一个节点。

给你一个整数 n 和一个下标从 0 开始、长度为 m 的二维整数数组 edges 表示这个有向无环图，其中 edges[i] = [ui, vi] 表示图中存在一条从 ui 队到 vi 队的有向边。

从 a 队到 b 队的有向边意味着 a 队比 b 队强，也就是 b 队比 a 队弱。

在这场比赛中，如果不存在某支强于 a 队的队伍，则认为 a 队将会是冠军。

如果这场比赛存在唯一一个冠军，则返回将会成为冠军的队伍。否则，返回 -1 。

注意

环是形如 a1, a2, ..., an, an+1 的一个序列，且满足：节点 a1 与节点 an+1 是同一个节点；节点 a1, a2, ..., an 互不相同；对于范围 [1, n] 中的每个 i ，均存在一条从节点 ai 到节点 ai+1 的有向边。
有向无环图 是不存在任何环的有向图。

示例 1：

输入：n = 3, edges = [[0,1],[1,2]]
输出：0
解释：1 队比 0 队弱。2 队比 1 队弱。所以冠军是 0 队。

示例 2：

输入：n = 4, edges = [[0,2],[1,3],[1,2]]
输出：-1
解释：2 队比 0 队和 1 队弱。3 队比 1 队弱。但是 1 队和 0 队之间不存在强弱对比。所以答案是 -1 。

提示：

1 <= n <= 100
m == edges.length
0 <= m <= n * (n - 1) / 2
edges[i].length == 2
0 <= edge[i][j] <= n - 1
edges[i][0] != edges[i][1]
生成的输入满足：如果 a 队比 b 队强，就不存在 b 队比 a 队强
生成的输入满足：如果 a 队比 b 队强，b 队比 c 队强，那么 a 队比 c 队强

地址

https://leetcode.cn/contest/weekly-contest-370/problems/find-champion-ii/

题意

图论

思路

题目需要找是否存在一个队比其他队都强，实则找到入度为 $0$ 的节点即可，因为只有入度为 $0$ 的节点才不会有其他队比它强。
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 表示给定的节点的数目。
空间复杂度：$O(1)$。

代码

class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        degree = [0] * n
        for x, y in edges:
            degree[y] += 1
        arr = [i for i, x in enumerate(degree) if x == 0]
        if len(arr) == 1:
            return arr[0]
        return -1

100118. 在树上执行操作以后得到的最大分数

有一棵 n 个节点的无向树，节点编号为 0 到 n - 1 ，根节点编号为 0 。给你一个长度为 n - 1 的二维整数数组 edges 表示这棵树，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 有一条边。

同时给你一个长度为 n 下标从 0 开始的整数数组 values ，其中 values[i] 表示第 i 个节点的值。

一开始你的分数为 0 ，每次操作中，你将执行：

选择节点 i 。
将 values[i] 加入你的分数。
将 values[i] 变为 0 。

如果从根节点出发，到任意叶子节点经过的路径上的节点值之和都不等于 0 ，那么我们称这棵树是 健康的 。

你可以对这棵树执行任意次操作，但要求执行完所有操作以后树是 健康的 ，请你返回你可以获得的 最大分数 。

示例 1：

输入：edges = [[0,1],[0,2],[0,3],[2,4],[4,5]], values = [5,2,5,2,1,1]
输出：11
解释：我们可以选择节点 1 ，2 ，3 ，4 和 5 。根节点的值是非 0 的。所以从根出发到任意叶子节点路径上节点值之和都不为 0 。所以树是健康的。你的得分之和为 values[1] + values[2] + values[3] + values[4] + values[5] = 11 。
11 是你对树执行任意次操作以后可以获得的最大得分之和。

示例 2：

输入：edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], values = [20,10,9,7,4,3,5]
输出：40
解释：我们选择节点 0 ，2 ，3 和 4 。
- 从 0 到 4 的节点值之和为 10 。
- 从 0 到 3 的节点值之和为 10 。
- 从 0 到 5 的节点值之和为 3 。
- 从 0 到 6 的节点值之和为 5 。
所以树是健康的。你的得分之和为 values[0] + values[2] + values[3] + values[4] = 40 。
40 是你对树执行任意次操作以后可以获得的最大得分之和。

提示：

2 <= n <= 2 * 104
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
values.length == n
1 <= values[i] <= 109
输入保证 edges 构成一棵合法的树。

地址

https://leetcode.cn/problems/maximum-score-after-applying-operations-on-a-tree/description/

题意

动态规划

思路

题目有点绕，但实际比较简单，我们知道仔细分析一下两种情况，假设当前遍历的节点为 $x$, 则可以看到：
- 假设 $x$ 的祖先存在某些节点未操作，即保存在树中，由于节点的每个值都大于 $0$，此时以 $x$ 为根节点的子树中的所有节点均可以操作，此时直接返回该子树下所有节点的和 $sum(x)$ 即可;
- 假设 $x$ 的祖先节点全部都被操作，此时以 $x$ 为根节点的子树中必须有节点需要保存，分为两种情况：
  - 如果 $x$ 为叶子节点，则该节点一定需要保存，一定不能操作；
  - 如果 $x$ 为非叶子节点，则我们返回 $x$ 被操作后的子树的最大值与 $x$ 不被操作的最大值即可；
- 实际我们需要两个 $DFS$ 接口，第一遍 $DFS$ 求出以 $x$ 为根节点的子树的元素和，第二遍我们求出以 $0$ 为节点的树中两种不同操作情况下的最大值即可。

时间复杂度：$O(n)$，其中$n$ 表示数组的长度；
空间复杂度：$O(1)$；

代码

class Solution:
    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:
        n = len(values)
        graph = [[] for _ in range(n)]
        for x, y in edges:
            graph[x].append(y)
            graph[y].append(x)
        tot = [0] * n
        
        def dfs1(root, parent):
            res = values[root]
            for v in graph[root]:
                if v == parent:
                    continue
                res += dfs1(v, root)
            tot[root] = res
            return res
        
        def dfs2(root, parent):
            if root != 0 and len(graph[root]) == 1:
                return 0
            res1, res2 = 0, values[root]
            for v in graph[root]:
                if v == parent:
                    continue
                res1 += tot[v]
                res2 += dfs2(v, root)  
            return max(res1, res2)

        dfs1(0, -1)
        return dfs2(0, -1)

100112. 平衡子序列的最大和

给你一个下标从 0 开始的整数数组 nums 。

nums 一个长度为 k 的 子序列 指的是选出 k 个下标 i0 < i1 < ... < ik-1 ，如果这个子序列满足以下条件，我们说它是 平衡的 ：

对于范围 [1, k - 1] 内的所有 j ，nums[ij] - nums[ij-1] >= ij - ij-1 都成立。

nums 长度为 1 的 子序列 是平衡的。

请你返回一个整数，表示 nums 平衡子序列里面的 最大元素和 。

一个数组的 子序列 指的是从原数组中删除一些元素（也可能一个元素也不删除）后，剩余元素保持相对顺序得到的非空新数组。

示例 1：

输入：nums = [3,3,5,6]
输出：14
解释：这个例子中，选择子序列 [3,5,6] ，下标为 0 ，2 和 3 的元素被选中。
nums[2] - nums[0] >= 2 - 0 。
nums[3] - nums[2] >= 3 - 2 。
所以，这是一个平衡子序列，且它的和是所有平衡子序列里最大的。
包含下标 1 ，2 和 3 的子序列也是一个平衡的子序列。
最大平衡子序列和为 14 。

示例 2：

输入：nums = [5,-1,-3,8]
输出：13
解释：这个例子中，选择子序列 [5,8] ，下标为 0 和 3 的元素被选中。
nums[3] - nums[0] >= 3 - 0 。
所以，这是一个平衡子序列，且它的和是所有平衡子序列里最大的。
最大平衡子序列和为 13 。

示例 3：

输入：nums = [-2,-1]
输出：-1
解释：这个例子中，选择子序列 [-1] 。
这是一个平衡子序列，而且它的和是 nums 所有平衡子序列里最大的。

提示：

1 <= nums.length <= 105
-109 <= nums[i] <= 109

地址

https://leetcode.cn/contest/weekly-contest-370/problems/maximum-balanced-subsequence-sum/

题意

线段树

思路

题目还是比较不错的题目，主要是自己想复杂了，想到了 $LIS$ 问题了，实际要简单不少。题目要求: $nums[i_j] - nums[i_{j-1}] \ge i_j - i_{j-1}$, 将上述变形即为 $nums[i_j] - i_j \ge nums[i_{j-1}]- i_{j-1}$, 本质上我们需要在满足 $f[i] = nums[i] - i$ 递增的序列中找到 $nums[i]$ 的和的最大值。我们令 $dp[i]$ 表示第 $i$ 个元素为 $f[i]$ 为递增的子序列中的元素的最大和，此时我们可以知道递推公式可以知道 :

$$dp[i+1] = \max(dp[j])_{j=0}^{i} + nums[i+1] \quad if \quad nums[i+1] - (i + 1) \ge nums[j] -j $$

刚开始想到了线段树，由于 $nums[i] - i$ 的值是固定的，最多只有 $n$ 个，此时我们进行离散化，假设当前 $b[i] = nums[i] - i$，此时找到 $0,k$ 范围的更新值进行更新，此时当前 $dp[i+1] = max(dp[0,\cdots k]) + nums[i+1]$，此时更新即可，不用范围更新就比较简单了，详细可以参考代码。
复杂度分析：

时间复杂度：$O(n \log n)$，其中 $n$ 表示数组的长度，线段树的查询和更新的复杂度均为 $n \log n$;
空间复杂度：$O(n)$，其中 $n$ 表示数组的长度；

代码

#define CHL(x) (x * 2)
#define CHR(x) (x * 2 + 1)
const int MAXN = 4e5 + 7;

struct SegTreeNode {
    int l, r;
    long long maxVal;
};

SegTreeNode tree[MAXN];

void pushUpTree(int idx) {
    tree[idx].maxVal = max(tree[CHL(idx)].maxVal, tree[CHR(idx)].maxVal);
}

void buildTree(int idx, int l, int r) {
    if (l > r) {
        return;
    }
    if (l == r) {
        tree[idx].l = tree[idx].r = l;
        tree[idx].maxVal = 0;
        return;
    }
    tree[idx].l = l;
    tree[idx].r = r;
    
    int mid = (l + r) / 2;
    buildTree(CHL(idx), l, mid);
    buildTree(CHR(idx), mid + 1, r);
    pushUpTree(idx);
}

void updateTree(int x, long long val, int idx) {
    if (x < tree[idx].l || x > tree[idx].r) {
        return;
    }
    if (x == tree[idx].l && x == tree[idx].r) {
        tree[idx].maxVal = val;
        return;
    }
    int mid = (tree[idx].l + tree[idx].r) / 2;
    if (x <= mid) {
        updateTree(x, val, CHL(idx));
    } else {
        updateTree(x, val, CHR(idx));
    }
    pushUpTree(idx);
}

long long queryTree(int l, int r, int idx) {
    if (r < tree[idx].l || l > tree[idx].r) {
        return 0;
    }
    if (l <= tree[idx].l && r >= tree[idx].r) {
        return tree[idx].maxVal;
    }
    int mid = (tree[idx].l + tree[idx].r) / 2;
    if (r <= mid) {
        return queryTree(l, r, CHL(idx));
    } else if (l > mid) {
        return queryTree(l, r, CHR(idx));
    } else {
        return max(queryTree(l, mid, CHL(idx)), queryTree(mid + 1, r, CHR(idx)));
    }
}

class Solution {
public:
    long long maxBalancedSubsequenceSum(vector<int>& nums) {
        unordered_set<int> cnt;
        for (int i = 0; i < nums.size(); i++) {
            cnt.emplace(nums[i] - i);
        }
        vector<int> arr(cnt.begin(), cnt.end());
        sort(arr.begin(), arr.end());
        int n = arr.size();
        buildTree(1, 0, n - 1);
        
        long long res = *max_element(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            auto it = upper_bound(arr.begin(), arr.end(), nums[i] - i);
            int x = it - arr.begin();
            if (nums[i] > 0) {
                long long val = queryTree(0, x - 1, 1) + nums[i];
                updateTree(x - 1, val, 1);
                res = max(res, val);
            }
        }
        return res;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://whistle-wind.com/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 题解力扣周赛赛

← leetcode weekly contes 371 leetcode weekly contes 372 →

扫描二维码，分享此文章