查看: 198|回复: 4
收起左侧

[树/链表/图] 难题"Count Subtrees With Max Distance Between Cities"结果不对

|只看干货
ATPtennis | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (28)
 
 
6% (2)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
EXAMPLE 1的结果是[3, 4, 0],我这个代码运行完了是[0, 1, 0]。这题真是相当强悍了,融合了找全部子数组,subsets这题,和tree diameter找最大边数两大知识点,我代码也是按照这思路写的,可是不知道为什么运行结果错误,妄解惑!谢谢!
from collections import defaultdictclass Solution:
    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:

        def dfs(root, prev):
            d1 = d2 = 0
            for nex in graph[root]:
                if nex != prev and nex in subtree:
                    d = dfs(nex, root)
                    if d > d1:
                        d1, d2 = d, d1
                    elif d > d2:
                        d2 = d
            self.max = max(self.max, d1+d2)
            return d1 + 1

        # build graph
        graph = defaultdict(set)
        for i, j in edges:
            graph.add(j)
            graph[j].add(i)

        # Get all subtrees
        for i in range(1 << n):
            subtree = []
            for j in range(n):
                if i & 1 << j:
                    subtree.append(j+1)

            # we have got a subtree, then we need to verify if it is valid
            number = 0
            for p, q in edges:
                if p in subtree and q in subtree:
                    number += 1
            if number < 1 or len(subtree) != number + 1:
                continue

            # we get the valid tree. we need to get the maximal diameter
            self.max = 0
            result = [0 for i in range(n-1)]
            dfs(subtree[0], None)
            result[self.max - 1] += 1
        return result






补充内容 (2021-09-15 16:04 +8:00):
找到了问题所在,把result = [0 for i in range(n-1)] 这行移出for循环,写到外面即可。

这道题是一道大综合,考察了树如何找最大直径,还有如何找一个数组的所有集合。然后判断这个集合是否是你想要的。综合起来去解决这道问题即可。

评分

参与人数 1大米 +5 收起 理由
14417335 + 5

查看全部评分


上一篇:Leetcode 282 简化版的一个问题
下一篇:刷题很卷,是不是应该考些别的
 楼主| ATPtennis 2021-9-14 17:48:59 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (28)
 
 
6% (2)    👎
求助,查了很久不知道哪有问题,!!!!!
回复

使用道具 举报

 楼主| ATPtennis 2021-9-15 03:11:48 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (28)
 
 
6% (2)    👎
看来这道题的难度是相当难度大了,等一个人解惑!!
回复

使用道具 举报

 楼主| ATPtennis 2021-9-15 05:17:59 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (28)
 
 
6% (2)    👎
等一个牛人解惑,卡了很久了
回复

使用道具 举报

 楼主| ATPtennis 2021-9-15 15:55:58 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (28)
 
 
6% (2)    👎
昨天又检查了一天,还是没发现哪有问题啊。求助!!!!!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表