|
精品推荐：
《征服数据结构》专栏：50多种数据结构彻底征服 《经典图论算法》专栏：50多种经典图论算法全部掌握 最近在网上看到一个悲伤的事，一位24届毕业生，在毕业当天收到华为的终止入职通知，原因是体检不合格，真的是毕业即失业。面试能通过说明能力肯定是没问题的，体检一般来说如果不是特别严重的话，不会轻易终止的。 如果是入职体检被拒一般来说病情可能比较严重，因为入职体检可查的项目不是很多，很多属于个人隐私，是不能查的。入职体检一般来说费用都不高，查的也不多，感觉就是走个形势。真的是麻绳专挑细处断，厄运专找苦命人，只能默默祝福该网友早日康复。 --------------下面是今天的算法题-------------- 来看下今天的算法题，这题是LeetCode的第1443题：收集树上所有苹果的最少时间，难度是中等。 给你一棵有 n 个节点的无向树，节点编号为 0 到 n-1 ，它们中有一些节点有苹果。通过树上的一条边，需要花费 1 秒钟。你从 节点 0 出发，请你返回最少需要多少秒，可以收集到所有苹果，并回到节点 0 。无向树的边由 edges 给出，其中 edges[i] = [fromi, toi] ，表示有一条边连接 from 和 toi 。除此以外，还有一个布尔数组 hasApple ，其中 hasApple[i] = true 代表节点 i 有一个苹果，否则，节点 i 没有苹果。输入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false] 输出：8 解释：上图展示了给定的树，其中红色节点表示有苹果。一个能收集到所有苹果的最优方案由绿色箭头表示。
输入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false] 输出：6 解释：上图展示了给定的树，其中红色节点表示有苹果。一个能收集到所有苹果的最优方案由绿色箭头表示。
1 <= n <= 10^5 edges.length == n - 1 edges[i].length == 2 0 <= ai < bi <= n - 1 hasApple.length == n
这题说的是有 n 个节点的无向树，没说是二叉树，其实这个不影响，我们直接从根节点 0 开始搜索，计算的时候采用自下往上的方式使用dfs计算花费的时间。如果子节点没有苹果，则到子节点不需要花费时间，只需要判断当前节点有没有苹果即可，如果当前节点有苹果，我们就累加 2 ，因为到当前节点一来一回需要花费 2 秒时间。如果当前节点没有苹果，也不需要到当前节点，到当前节点花费的时间为 0 。如果子节点有苹果，无论当前节点有没有苹果，都会经过当前节点，所以到当前节点的时候，花费的时间要累加 2 。如果当前节点是根节点，无论根节点有没有苹果，都不需要花费时间，因为起始点就是从根节点开始的。public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
List<Integer>[] g = new List[n];
for (int i = 0; i < n; i++)
g[i] = new ArrayList<>();
for (int[] edge : edges) {
g[edge[0]].add(edge[1]);
g[edge[1]].add(edge[0]);
}
return dfs(0, -1, g, hasApple);
}
private int dfs(int start, int parent, List<Integer>[] g, List<Boolean> hasApple) {
// 如果是叶子节点。
if (g[start].size() == 1 && g[start].get(0) == parent)
return hasApple.get(start) ? 2 : 0;
int total = 0;// 计算到子节点的苹果中花费的时间
for (int child : g[start]) {
if (child == parent)
continue;
total += dfs(child, start, g, hasApple);
}
if (parent == -1)// start是根节点。
return total;
elseif (total == 0) // start不是根节点，且子节点都没有苹果，返回当前节点有没有苹果。
return hasApple.get(start) ? 2 : 0;
elsereturn total + 2;// 子节点有苹果。
}
public:
int minTime(int n, vector<vector<int>> &edges, vector<bool> &hasApple) {
vector<vector<int>> g(n);
for (constauto &edge: edges) {
g[edge[0]].push_back(edge[1]);
g[edge[1]].push_back(edge[0]);
}
return dfs(0, -1, g, hasApple);
}
int dfs(int start, int parent, const vector<vector<int>> &g, const vector<bool> &hasApple) {
// 如果是叶子节点。
if (g[start].size() == 1 && g[start][0] == parent)
return hasApple[start] ? 2 : 0;
int total = 0; // 计算到子节点的苹果中花费的时间
for (int child: g[start]) {
if (child == parent)
continue;
total += dfs(child, start, g, hasApple);
}
if (parent == -1) // start是根节点。
return total;
elseif (total == 0) // start不是根节点，且子节点都没有苹果，返回当前节点有没有苹果。
return hasApple[start] ? 2 : 0;
elsereturn total + 2; // 子节点有苹果。
}
博哥，真名：王一博，毕业十多年，《算法秘籍》作者，专注于数据结构和算法的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧
|
