苏州市建设中心网站首页,0元做网站,信息网站的建设,营销推广48个方法1. 题目
给你一棵有 n 个节点的无向树#xff0c;节点编号为 0 到 n-1 #xff0c;它们中有一些节点有苹果。 通过树上的一条边#xff0c;需要花费 1 秒钟。 你从 节点 0 出发#xff0c;请你返回最少需要多少秒#xff0c;可以收集到所有苹果#xff0c;并回到节点 0 …1. 题目
给你一棵有 n 个节点的无向树节点编号为 0 到 n-1 它们中有一些节点有苹果。 通过树上的一条边需要花费 1 秒钟。 你从 节点 0 出发请你返回最少需要多少秒可以收集到所有苹果并回到节点 0 。
无向树的边由 edges 给出其中 edges[i] [fromi, toi] 表示有一条边连接 from 和 toi 。 除此以外还有一个布尔数组 hasApple 其中 hasApple[i] true 代表节点 i 有一个苹果否则节点 i 没有苹果。
示例 1
输入n 7, edges [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]],
hasApple [false,false,true,false,true,true,false]
输出8
解释上图展示了给定的树其中红色节点表示有苹果。
一个能收集到所有苹果的最优方案由绿色箭头表示。示例 2
输入n 7, edges [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]],
hasApple [false,false,true,false,false,true,false]
输出6
解释上图展示了给定的树其中红色节点表示有苹果。
一个能收集到所有苹果的最优方案由绿色箭头表示。示例 3
输入n 7, edges [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]],
hasApple [false,false,false,false,false,false,false]
输出0提示
1 n 10^5
edges.length n-1
edges[i].length 2
0 fromi, toi n-1
fromi toi
hasApple.length n来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-time-to-collect-all-apples-in-a-tree 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
由题目条件可知向上走的路径只有1个分支把反向的路径存在哈希map里遍历hasApple数组对有苹果的序号进行dfs往上找找到一条边就在哈希表里删除一条最后返回边的个数乘以2
class Solution {
public:int minTime(int n, vectorvectorint edges, vectorbool hasApple) {unordered_mapint,int up;//向上走的路径for(vectorint e : edges)up[e[1]] e[0];int s 0;for(int i 0; i hasApple.size(); i){if(hasApple[i])dfs(i, up, s);}return 2*s;}void dfs(int i, unordered_mapint,int up, int s){if(up.count(i)){s;int to up[i];//上层节点up.erase(i);//删除边dfs(to,up,s);}}
};360 ms 56.3 MB
