本文介绍: 去参加CCF软件大会,好多天没做每日一题了。

在这里插入图片描述
参加CCF软件大会,好多天没做每日一题了
我的思路

  1. 看到题目一个叶子节点向根节点汇聚的过程,就想到拓扑排序
  2. 每次移动都只将叶子节点向前移动一格,并删除它,此时移动目标点数加一,并根据该叶子节点此时的数量增加油耗,同时将新的叶子节点加入队列中知道队列中只剩下根节点
  3. 但是上面的做法没有考虑官方题解的思路,当dfs时,每次递归包含了所有子节点的信息直接统计数量计算油耗即可
  4. 下面是我的代码官方题解
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进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注