Leetcode周赛370补题（3 / 3）
目录
1、找到冠军 Ⅰ- 暴力
2、找到冠军 Ⅱ - 寻找入度为0的点
3、在树上执行操作以后得到的最大分数 - dfs树 + 逆向思考
1、找到冠军 Ⅰ- 暴力
100115. 找到冠军 I
class Solution {public int findChampion(int[][] g) {int n=g.length;for(int i=0;i<n;i++){int cnt=0;for(int j=0;j<n;j++)if(g[i][j]==1) cnt++;if(cnt==n-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[] st=new int[n];for(int[] e:edges)st[e[1]]=1; //将入度不为0的点标记int res=-1;for(int i=0;i<n;i++){if(st[i]==0){if(res!=-1) return -1; //如果入度为0且有多个则无法判断冠军res=i;}}return res;}
}3、在树上执行操作以后得到的最大分数 - dfs树 + 逆向思考
100118. 在树上执行操作以后得到的最大分数
思路：
要保证这棵树是健康的，且要保证得分最大，即保证每条分支至少保留一个节点不操作（保证该路径和不为0）
所以问题转换为找出每个分支满足健康情况下的【代价和最小】的不操作点
则操作点最大代价和 = 总代价 - 不操作点最小代价和
如下图，选2，5，6为不操作点，则能保证每条分支代价和均不为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,List<Integer>[] g,int[] st ){long cnt=0;for(int x:g[cur]) if(st[x]==0){st[x]=1;cnt+=dfs(x,v,g,st);}//cnt=0表示该节点为叶子节点//说白了就是看：是选某子树的根节点值or根节点下子树代价和最小值return cnt==0? v[cur]:Math.min((long)v[cur],cnt);} public long maximumScoreAfterOperations(int[][] edges, int[] values) {int n=values.length;List<Integer>[] g=new ArrayList[n+1];for(int i=0;i<n;i++) g[i]=new ArrayList<>();int[] st=new int[n+1];long res=0;for(int x:values) res+=x;//建树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为根节点的健康子树中不操作节点的最小代价//最大代价 = 总代价 - 不操作节点的最小代价和}
}