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 队将会是 冠军 。

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

---

复杂度：O（N*N）
思路：用cnt记录每个人获胜的次数，哪名玩家的cnt更大，就将答案更新为那名玩家。

class Solution {public int findChampion(int[][] grid) {int ans = 0;int cnt = 0;int n = grid.length;int m = grid[0].length;for(int i=0; i<n; i++) {int c = 0;for(int j=0; j<n; j++) {if(grid[i][j] == 1) {c ++;}if(c>cnt) {cnt = c;ans = i;}}}return ans;}
}

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 的有向边。
有向无环图 是不存在任何环的有向图。

---

复杂度：O（N）
思路：统计入度，更优化的。统计每个节点的前继节点，没有记为-1。若有多个-1，则将返回-1。

class Solution {public int findChampion(int n, int[][] edges) {int ans = -1;// 保存前继节点int[] pre = new int[n];Arrays.fill(pre, -1);int m = edges.length;for(int i=0; i<m; i++) {pre[edges[i][1]] = edges[i][0];}int cnt = 0;for(int i=0; i<n; i++) {if(pre[i] == -1) {cnt ++;if(cnt == 2) {return -1;}ans = i;}}return ans;}
}

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 ，那么我们称这棵树是 健康的 。

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

---

复杂度：O（N）
思路：DFS。原问题可以更换为：sum-每条路径上删去一个点。自底向上，统计删除子节点和删除根节点哪个成本更少。

class Solution {List<Integer>[] g;public long maximumScoreAfterOperations(int[][] edges, int[] values) {long ans = 0;for(int v:values) {ans += v;}int n = values.length;if(n == 2) {return Math.max(values[0], values[1]);}g = new ArrayList[n];// 存储后继节点Arrays.setAll(g, e-> new ArrayList());// 是否为根节点int[] cnt = new int[n];int m = edges.length;for(int[] e:edges) {int x = Math.min(e[0], e[1]);int y = Math.max(e[0], e[1]);g[x].add(y);g[y].add(x);     }     boolean[] visibled = new boolean[n]; // System.out.println(ans);return ans-dfs(g[0], 0, values, visibled, 0);}private long dfs(List<Integer> list, int idx, int[] values, boolean[] visibled, int l) {long ans = values[idx];int n = list.size();if(n == 1&&l!=0) return ans;l ++;long sum = 0;visibled[idx] = true;for(int i=0; i<n; i++) {// 获取后继索引int t = list.get(i);if(visibled[t] == false) {// System.out.println(idx+"-"+t);sum = sum + dfs(g[t], t, values, visibled, l);}            }return Math.min(sum, ans);}
}

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 平衡 子序列里面的 最大元素和 。

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

---

复杂度：O(NlogN)
思路：
 ①将题目要求的条件改为num[i]-i为递增的。那么可以将num[i]-i按照从小到大的顺序离散到1-n。将nums[i]-i按照大小离散化到1-n。
 ②DP。dp[i]表示前i个元素的子序列和的最大值。
dp[i] = Math.max(dp[j])+nums[i]。j<i且nums[j]<=nums[i]
 ③使用树状数组实现dp[i]。由于nums[i]-i被按照大小离散化到1-j-n。所以只要搜寻j之前的元素即可。这部分使用preMax函数实现。
更新树状数组时，由于记录的已经是前缀和，直接按照大小更新。

class Solution {long minN = Long.MIN_VALUE;// 树状数组class BIT{// 数组private long[] tree;public BIT(int n) {tree = new long[n];Arrays.fill(tree, minN);}public void update(int i, long val) {while(i<tree.length) {tree[i] = Math.max(tree[i], val);i += i&-i;}}public long preMax(int i) {long res = minN;while(i>0) {res = Math.max(res, tree[i]);i -= i&-i;}return res;}}public long maxBalancedSubsequenceSum(int[] nums) {int n = nums.length;int[] b = new int[n];for(int i=0; i<n; i++) {b[i] = nums[i] - i;}long ans = minN;Arrays.sort(b);BIT tree = new BIT(n+1);for(int i=0; i<n; i++) {// 离散区间int j = Arrays.binarySearch(b, nums[i]-i)+1;long f = Math.max(tree.preMax(j), 0) + nums[i];ans = Math.max(ans, f);tree.update(j, f);}return ans;}
}