重庆城市管理学院网站,网站必须要实名认证么,如何申请ip地址和域名,代理赚钱2024.2.29 题目来源我的题解方法一 深度搜索#xff08;暴力#xff09; 超时方法二 树形动态规划 题目来源
力扣每日一题#xff1b;题序#xff1a;2581
我的题解
方法一 深度搜索#xff08;暴力#xff09; 超时 以每个节点node为跟进行深度搜索#xff0c;并在搜… 2024.2.29 题目来源我的题解方法一 深度搜索暴力 超时方法二 树形动态规划 题目来源
力扣每日一题题序2581
我的题解
方法一 深度搜索暴力 超时 以每个节点node为跟进行深度搜索并在搜索过程中记录前驱节点然后判断[前驱节点当前节点]是否在guesses中出现。若出现则表示Bob猜测对一次并记录在count数组中。最后遍历count数组看有多少满足count[i]k。该值就是可能成为树根的 节点数目 时间复杂度O( n ( n e ) n(ne) n(ne))。n表示树的节点数e表示树的边数 空间复杂度O(n) class Solution {//为了快速判断[u,v]对是否存在连接成字符串ListListString guessnew ArrayList();//记录以节点i为根用户猜对的次数当然由于在过程中进行了截断所以最大值为kint[] count;public int rootCount(int[][] edges, int[][] guesses, int k) {int nedges.length1;countnew int[n];ListInteger[] gcreateGraph(n,edges);for(int[] t:guesses){int u t[0];int v t[1];guess.add(u-v);}for(int i0;in;i){dfs(i,i,g,-1,k);}int res0;for(int i0;in;i){if(count[i]k)res;}return res;}//深度优先搜索public void dfs(int root,int cur,ListInteger[] g,int pre,int k){//根节点没有父节点if(pre!-1){String tpre-cur;//Bob猜测正确if(guess.contains(t))count[root];//截断当已经正确的次数达到k表明以root为根一定满足if(count[root]k)return;}for(int next:g[cur]){//防止循环遍历if(next!pre){dfs(root,next,g,cur,k);}}}//构建树public ListInteger[] createGraph(int n,int[][] edges){ListInteger[] gnew ArrayList[n];for(int i0;in;i){g[i]new ArrayList();}for(int[] t:edges){int fromt[0];int to t[1];g[from].add(to);g[to].add(from);}return g;}
}//优化版本但是还是超时
// 利用了如下的结论进行优化。
//基于已经计算出以 x 为树根时猜对的次数很容易就可以计算出以 y 为树根时猜对的次数
//如果 (x,y) 存在于 guesses猜对次数减一
//如果 (y,x) 存在于 guesses猜对次数加一。class Solution {ListString guessnew ArrayList();int cnt0;int res0;public int rootCount(int[][] edges, int[][] guesses, int k) {int nedges.length1;// countnew int[n];ListInteger[] gcreateGraph(n,edges);for(int[] t:guesses){int u t[0];int v t[1];guess.add(u-v);}dfs(0,0,g,-1,k);rdfs(g,0,-1,k,cnt);return res;}public void rdfs(ListInteger[] g,int x,int t,int k,int cnt){if(cntk){res;}for(int y:g[x]){if(ty)continue;rdfs(g,y,x,k,cnt-(guess.contains(x-y)?1:0)(guess.contains(y-x)?1:0));}}public void dfs(int root,int cur,ListInteger[] g,int pre,int k){if(pre!-1){String tpre-cur;if(guess.contains(t))cnt;}for(int next:g[cur]){if(next!pre){dfs(root,next,g,cur,k);}}}public ListInteger[] createGraph(int n,int[][] edges){ListInteger[] gnew ArrayList[n];for(int i0;in;i){g[i]new ArrayList();}for(int[] t:edges){int fromt[0];int to t[1];g[from].add(to);g[to].add(from);}return g;}
}
方法二 树形动态规划 看官方题解吧弄不明白 终于补完2月的每日一题了。
有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
