不邻接植花

Posted on In

1042. 不邻接植花

不邻接植花

链接

思路

  1. 路径关系是一种无向图
  2. 一个节点最多三条路径，却有四种花．也就是说一定有解
  3. 将图的关系存储起来，每一个节点随机选择种类就可以，不必考虑回溯

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from typing import List


class Solution:

	def gardenNoAdj(self, n: int, paths: List[List[int]]):  # type: ignore
		res = [0] * n
		# 建立矩阵
		G = [[] for _ in range(n)]
		for e in paths:
			G[e[0] - 1].append(e[1] - 1)
			G[e[1] - 1].append(e[0] - 1)
		# pop随机弹出结果
		for i in range(n):
			res[i] = ({1, 2, 3, 4} - {res[j] for j in G[i]}).pop()
		return res

注意

  • 花园从１开始排序，注意数组索引的变化
  • python中集合可以pop()