- 看到题目是一个由叶子节点向根节点汇聚的过程,就想到拓扑排序
- 每次移动都只将叶子节点向前移动一格,并删除它,此时移动的目标节点数量加一,并根据该叶子节点此时的数量增加油耗,同时将新的叶子节点加入队列中,知道队列中只剩下根节点
- 但是上面的做法没有考虑到官方题解的思路,当dfs时,每次递归就包含了所有子节点的信息,直接统计数量计算油耗即可
- 下面是我的代码和官方题解
class Solution:
def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
edges = defaultdict(list)
deg = [0] * (len(roads) + 1)
for r in roads:
edges[r[0]].append(r[1])
edges[r[1]].append(r[0])
deg[r[0]] += 1
deg[r[1]] += 1
fa = {}
leaf = []
def dfs(node, last):
if len(edges[node]) == 1 and node != 0:
leaf.append(node)
for i in edges[node]:
if i == last:
continue
fa[i] = node
dfs(i, node)
dfs(0, -1)
ans = 0
nums = [1] * (len(roads) + 1)
while len(leaf) > 0:
t = []
for i in range(len(leaf)):
if leaf[i] == 0:
continue
deg[fa[leaf[i]]] -= 1
if deg[fa[leaf[i]]] == 1:
t.append(fa[leaf[i]])
ans += ceil(nums[leaf[i]] / seats)
nums[fa[leaf[i]]] += nums[leaf[i]]
leaf = t
return ans
class Solution:
def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
g = [[] for i in range(len(roads) + 1)]
for e in roads:
g[e[0]].append(e[1])
g[e[1]].append(e[0])
res = 0
def dfs(cur, fa):
nonlocal res
peopleSum = 1
for ne in g[cur]:
if ne != fa:
peopleCnt = dfs(ne, cur)
peopleSum += peopleCnt
res += (peopleCnt + seats - 1) // seats
return peopleSum
dfs(0, -1)
return res
作者:力扣官方题解
链接:https://leetcode.cn/problems/minimum-fuel-cost-to-report-to-the-capital/solutions/2553190/dao-da-shou-du-de-zui-shao-you-hao-by-le-v013/
来源:力扣(LeetCode)
原文地址:https://blog.csdn.net/qq_46636391/article/details/134807273
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_44314.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。