酷站网素材,一级消防工程师,网站推广优化方案模板,购物网站支付页面制作100115. 找到冠军 I
一场比赛中共有 n 支队伍#xff0c;按从 0 到 n - 1 编号。
给你一个下标从 0 开始、大小为 n * n 的二维布尔矩阵 grid 。对于满足 0 i, j n - 1 且 i ! j 的所有 i, j #xff1a;如果 grid[i][j] 1#xff0c;那么 i 队比 j 队 强 按从 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 队将会是 冠军 。
返回这场比赛中将会成为冠军的队伍。 复杂度ON*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 i0; in; i) {int c 0;for(int j0; jn; j) {if(grid[i][j] 1) {c ;}if(ccnt) {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, an1 的一个序列且满足节点 a1 与节点 an1 是同一个节点节点 a1, a2, …, an 互不相同对于范围 [1, n] 中的每个 i 均存在一条从节点 ai 到节点 ai1 的有向边。 有向无环图 是不存在任何环的有向图。 复杂度ON 思路统计入度更优化的。统计每个节点的前继节点没有记为-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 i0; im; i) {pre[edges[i][1]] edges[i][0];}int cnt 0;for(int i0; in; 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 那么我们称这棵树是 健康的 。
你可以对这棵树执行任意次操作但要求执行完所有操作以后树是 健康的 请你返回你可以获得的 最大分数 。 复杂度ON 思路DFS。原问题可以更换为sum-每条路径上删去一个点。自底向上统计删除子节点和删除根节点哪个成本更少。
class Solution {ListInteger[] 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(ListInteger list, int idx, int[] values, boolean[] visibled, int l) {long ans values[idx];int n list.size();if(n 1l!0) return ans;l ;long sum 0;visibled[idx] true;for(int i0; in; 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]。ji且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(itree.length) {tree[i] Math.max(tree[i], val);i i-i;}}public long preMax(int i) {long res minN;while(i0) {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 i0; in; i) {b[i] nums[i] - i;}long ans minN;Arrays.sort(b);BIT tree new BIT(n1);for(int i0; in; 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;}
}
