leetcode：1042. 不邻接植花【随机填入符合要求的 + 后面不会形成矛盾 + set.pop】

分析

记录一下邻接表信息
然后从1到n
每个点看，先从1234中去掉它邻居的颜色，然后这个点就在这里选一个即可
用到的set pop就是随机从set中拿一个

ac code

class Solution:
    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
        # 四色问题(三条路径)
        g = defaultdict(list)
        for x, y in paths:
            g[x].append(y)
            g[y].append(x)
        
        ans = [0] * n
        # set的pop随机弹出一个
        # 贪心选当前的即可，后面不会有矛盾点（最多三个路径）
        for i in range(1, n + 1):
            # 去掉和i相邻的j的颜色即可
            colors = set(range(1, 5)) - set([ans[j - 1] for j in g[i]])
            ans[i - 1] = colors.pop()
        
        return ans
    

总结

按顺序每个点填色
只需要不与其相邻的点重复即可