Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2023-01-11 11:18:39
1443. Minimum Time to Collect All Apples in a Tree
给你一个n表示节点数量、一个edges[]表示树之间的关系,和一个hasApple[i]表示
node i 是否有苹果,我们要从节点0出发(root)并且拿到所有苹果后走回原点,求出
共要走几步。
Example:
https://assets.leetcode.com/uploads/2020/04/23/min_time_collect_apple_1.png
Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple =
[false,false,true,false,true,true,false]
Output: 8
https://assets.leetcode.com/uploads/2020/04/23/min_time_collect_apple_2.png
Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple =
[false,false,true,false,false,true,false]
Output: 6
Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple =
[false,false,false,false,false,false,false]
Output: 0
思路:
1.用list建立边的关系,并统计苹果的数量,如果苹果数量为0直接返回0。
2.大致上的想法是拿所有必要的成本,拜访每个点的成本为2(来回)
有两种情况当前节点的成本必拿:
(1)子节点有苹果
(2)当前点有苹果
其他情况的成本都舍弃
3.用dfs取出所有必要的节点之后减去2(走到节点0不需要成本)
Java Code:
作者: SecondRun (雨夜琴声)   2023-01-11 11:35:00
大师
作者: NTHUlagka (拉卡)   2023-01-11 13:06:00
大师
作者: Wardyal (Wardyal)   2023-01-11 13:29:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com