题目相关
- 原题链接：1042. 不邻接植花 - 力扣（LeetCode）
- 涉及知识：图
- 题目难度：★
题目解读
由题意知，和题目相关的数据结构是无向图。其中图中的每个节点的度最多为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:]
