讨论/题目交流/🐱 第 12 场夜喵双周赛/
🐱 第 12 场夜喵双周赛

欢迎在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 数组变换
4 分 - 力扣排行榜
5 分 - 树的直径
7 分 - 删除回文子数组

展开讨论

第三题 一次 BFSBFS

不断去掉叶子,每去掉一层叶子,最长路径 +2+2,最后剩余一个节点的话,说明共有偶数条边,即是最长路径,如果最后剩余两个节点,这两个节点之间一定有一条边相边,此时最长路径 +1+1(参考 310 最小高度树

class Solution:
    def treeDiameter(self, edges: List[List[int]]) -> int:
        from collections import defaultdict
        if not edges:
            return 0
        graph = defaultdict(list)
        for x, y in edges:
            graph[x].append(y)
            graph[y].append(x)
        n = len(graph)
        ans = 0
        # 叶子节点
        leaves = [i for i in graph if len(graph[i]) == 1]
        while n > 2:
            ans +=2
            n -= len(leaves)
            nxt_leaves = []
            for leave in leaves:
                # 与叶子节点相连的点找到
                tmp = graph[leave].pop()
                # 相连的点删去这个叶子节点
                graph[tmp].remove(leave)
                if len(graph[tmp]) == 1:
                    nxt_leaves.append(tmp)
            leaves = nxt_leaves
        if len(leaves) == 2:
            ans += 1
        return ans
3
展开全部 12 讨论