LeetCode 1042.不邻接植花 python实现

有 N 个花园,按从 1 到 N 标记。在每个花园中,你打算种下四种花之一。

paths[i] = [x, y] 描述了花园 x 到花园 y 的双向路径。

另外,没有花园有 3 条以上的路径可以进入或者离开。

你需要为每个花园选择一种花,使得通过路径相连的任何两个花园中的花的种类互不相同。

以数组形式返回选择的方案作为答案 answer,其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用 1, 2, 3, 4 表示。保证存在答案。

示例 1:

输入:N = 3, paths = [[1,2],[2,3],[3,1]]
输出:[1,2,3]

示例 2:

输入:N = 4, paths = [[1,2],[3,4]]
输出:[1,2,1,2]

示例 3:

输入:N = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
输出:[1,2,3,4]

提示:

1 <= N <= 10000
0 <= paths.size <= 20000
不存在花园有 4 条或者更多路径可以进入或离开。
保证存在答案。

知识准备

  • 在python中可以使用列表作为队列,list用append添加元素

  • 可以用字典来存储邻接节点nei = {}

  • 在集合中使用for循环

    {res[j] for j in G[i]}
  • 集合的pop函数

    flowers = {1,2,3,4}  #集合直接相减即可
    flowers.pop()
    # 集合不能获取某个元素这样子的操作
    print(flowers)
    
    out: {2,3,4}集合中的pop是从左边开始取
  • 集合的相减

    flowers = {1,2,3,4}
    h = {0}
    flowers-h
    
    out:{1,2,3,4}

我的题解

  • 题解1

    class Solution:
          # 整体思路采用BFS方法,还需考虑不连通图的问题,然后着手结果唯一
          def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]:
              #构建一个answer数组
              answer = [0 for _ in range(N)]
              #构建所有节点
              all_nodes = []
              [all_nodes.append(i) for i in range(1,N+1)]
              #构建visted列表
              visted = dict.fromkeys(all_nodes, 0)
              #初始化nei字典元素为空列表
              nei = [[] for _ in range(N)]
              # 构建无向邻接表,无邻居则不构建
              for path in paths:
                  nei[path[0]-1].append(path[1])
                  nei[path[1]-1].append(path[0])
              #遍历每一个点,每个点保证自己邻接点不是和自己相同就行
              answer[0] = 1 
              for node in range(1,N+1):    #遍历所有节点
                  visted[node] = 1
                  fix = set()
                  if(answer[node-1]==0):  #如果为0,说明不是连通图
                      answer[node-1] = 1  
                  flowers=[1,2,3,4]
                  nei[node-1]  = sorted(nei[node-1]) #排序邻居节点
                  flowers.pop(answer[node-1]-1) #弹出父节点的flowers
                  for sinode in nei[node-1]: #遍历邻居
                      if(visted[sinode] == 0): #如果邻居未被访问过
                          answer[sinode-1] = flowers[0] #使用1,弹出1
                          flowers.pop(0)
                      else: #如果邻居被访问过
                          if(answer[sinode-1]==answer[node-1]):
                              answer[node-1] = flowers[0] 
                              flowers.pop(0) 
                          fix.add(answer[sinode-1])
                  if not fix:
                      continue
                  else:
                      flowers=[1,2,3,4]
                      for a_val in list(fix):
                          flowers.remove(a_val)
                      answer[node-1] = flowers[0]
                              
              return answer
  • 简化方法:利用集合快速搞定

    class Solution:
        def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]:
          #构建一个answer数组
            answer = [0]*N
            #初始化nei字典元素为空列表
            nei = [[] for _ in range(N)]
            # 构建无向邻接表,无邻居则不构建
            for path in paths:
                nei[path[0]-1].append(path[1])
                nei[path[1]-1].append(path[0])
            for node in range(1,N+1):    #遍历所有节点
                flowers={1,2,3,4}
                #临时存储邻居含有的花类型
                a = set()
                for sinode in nei[node-1]: #遍历邻居
                    a.add(answer[sinode-1])
                flowers = flowers - a 
                answer[node-1] = flowers.pop()
                                   
            return answer

相关推荐