公司网站制作定制,wordpress 首页不更新,食品网站建设策划书,网站建设明薇通网络目录
1、找到冠军 Ⅰ- 暴力
2、找到冠军 Ⅱ - 寻找入度为0的点
3、在树上执行操作以后得到的最大分数 - dfs树 逆向思考 1、找到冠军 Ⅰ- 暴力
100115. 找到冠军 I class Solution {public int findChampion(int[][] g) {int ng.length;for(int i0;in;i){int cnt0;for…目录
1、找到冠军 Ⅰ- 暴力
2、找到冠军 Ⅱ - 寻找入度为0的点
3、在树上执行操作以后得到的最大分数 - dfs树 逆向思考 1、找到冠军 Ⅰ- 暴力
100115. 找到冠军 I class Solution {public int findChampion(int[][] g) {int ng.length;for(int i0;in;i){int cnt0;for(int j0;jn;j)if(g[i][j]1) cnt;if(cntn-1) return i;}return 1;}
} 2、找到冠军 Ⅱ - 寻找入度为0的点
100116. 找到冠军 II 思路 我们通过样例发现冠军点的入度肯定为0假设有多个入度为0的点是否能判断出谁是冠军我们画几种情况看看 我们发现如果有多个入度为0的点则无法判断出冠军因为冠军并不是由战胜队伍的数量来衡量的因此我们只需要找入度为0的点如果有多个则返回-1 简化代码可以标记入度为0的点然后遍历找出入度为0的点如果出现多个则返回-1 class Solution {public int findChampion(int n, int[][] edges) {int[] stnew int[n];for(int[] e:edges)st[e[1]]1; //将入度不为0的点标记int res-1;for(int i0;in;i){if(st[i]0){if(res!-1) return -1; //如果入度为0且有多个则无法判断冠军resi;}}return res;}
} 3、在树上执行操作以后得到的最大分数 - dfs树 逆向思考
100118. 在树上执行操作以后得到的最大分数 思路 要保证这棵树是健康的且要保证得分最大即保证每条分支至少保留一个节点不操作保证该路径和不为0 所以问题转换为找出每个分支满足健康情况下的【代价和最小】的不操作点 则操作点最大代价和 总代价 - 不操作点最小代价和 如下图选256为不操作点则能保证每条分支代价和均不为0且价值最大 我们设dfs(x)为以x为根节点的健康子树中不操作节点的最小代价 其中cnt为以cur为根节点的子树的最小代价和 则答案总value - dfs(0) 【整棵健康数中不操作节点的最小代价】 在dfs函数中遍历cur节点的子节点求出子节点的最小代价和cnt返回 min(cur的价值以cur为根节点的子树的最小代价cnt)如果cur为叶子节点则dfs值为val[cur] 为什么需要st[ ]数组标记建双向边 因为题目声明根节点为0从0开始且为无向树因此需要双向建边 如果单向建边就会出现下面的这种错误样例 class Solution {public long dfs(int cur,int[] v,ListInteger[] g,int[] st ){long cnt0;for(int x:g[cur]) if(st[x]0){st[x]1;cntdfs(x,v,g,st);}//cnt0表示该节点为叶子节点//说白了就是看是选某子树的根节点值or根节点下子树代价和最小值return cnt0? v[cur]:Math.min((long)v[cur],cnt);} public long maximumScoreAfterOperations(int[][] edges, int[] values) {int nvalues.length;ListInteger[] gnew ArrayList[n1];for(int i0;in;i) g[i]new ArrayList();int[] stnew int[n1];long res0;for(int x:values) resx;//建树for(int[] e:edges){g[e[0]].add(e[1]);g[e[1]].add(e[0]);}st[0]1;return res-dfs(0,values,g,st); //dfs(x)表示以x为根节点的健康子树中不操作节点的最小代价//最大代价 总代价 - 不操作节点的最小代价和}
}
