美文网首页
『图』不邻接植花1042

『图』不邻接植花1042

作者: iamlightsmile | 来源:发表于2020-04-18 20:54 被阅读0次

    题目相关

    题目解读

    由题意知,和题目相关的数据结构是无向图。其中图中的每个节点的度最多为3。为了求解具体花色,我们可以模拟这个植花过程。即对于花园i,我们得到其所有邻接花园的花的种类的集合,然后在其它花色中选择一个,并重复该过程。

    Python相关

    我们可以用邻接表来表示该图结构,具体的为Python中的collections.defaultdict(list)结构。
    同时用大小为N+1的数组存储对应花色表示,之所以是N+1是为了和给定的数据表示一致,不然还得来回+-1。
    为了方便,我们可以将数组元素全部初始化为0。

    具体实现

    class Solution:
        def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]:
            # 根据相邻花园确定本花园种类
            def get_flower(exits):
                for i in range(1, 5):
                    if i not in exits:
                        return i
                return -1
            # 创建邻接表
            dic = collections.defaultdict(list)
            for i, j in paths:
                dic[i].append(j)
                dic[j].append(i)
            # 初始化为0配合获取花种类函数,同时列表长度设为N+1简化表示
            res = [0] * (N + 1)
            for i in range(1, N + 1):
                exits = [res[x] for x in dic[i]]
                res[i] = get_flower(exits)
            return res[1:]
    

    相关文章

      网友评论

          本文标题:『图』不邻接植花1042

          本文链接:https://www.haomeiwen.com/subject/eqxavhtx.html