不邻接种花（贪心、哈希表、哈希表数组）

力扣链接：力扣

        有 n 个花园，按从 1 到 n 标记。另有数组 paths ，其中 paths[i] = [xi, yi] 描述了花园 xi 到花园 yi 的双向路径。在每个花园中，你打算种下四种花之一。

        另外，所有花园 最多 有 3 条路径可以进入或离开.

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

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

示例 1：

输入：n = 3, paths = [[1,2],[2,3],[3,1]]
输出：[1,2,3]
解释：
花园 1 和 2 花的种类不同。
花园 2 和 3 花的种类不同。
花园 3 和 1 花的种类不同。
因此，[1,2,3] 是一个满足题意的答案。其他满足题意的答案有 [1,2,4]、[1,4,2] 和 [3,2,1]

示例 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]

题目解析：

        这道题的一个核心思路是贪心。当我们要对某个花园i（1 <= i <= n）种花时，我们要考虑其相邻的花园的种花情况。我们只能从{1，2，3，4}中选出相邻花园没有种过的花进行使用。那我们就需要一个哈希表Map记录花园i相邻花园已经种的花，其中键是花园编号i，值是一个哈希集合Set记录花园i相邻花园种的花。我们依次从四个花种{1，2，3，4}选出一种花，只要这种花不在集合中，那么就要种花。
        花园i种f号花的时候，它相应的是它相邻花园的相邻花园。因此需要去更新其相邻花园的哈希集合，添加花园i种的花的种类。进行更新。

图解：

以示例3进行过程图解

示例代码：  【贪心+哈希表】

from typing import List


class Solution:
    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
        def add_neighbor(garden: int, neighbor: int):
            """
            添加一个花园garden的相邻花园neighbor到哈希表中
            :param garden:
            :param neighbor:
            :return:
            """
            # 从哈希表中获取garden的相邻花园列表；如果garden不存在，说明这是garden的首个相邻花园，新建一个列表
            neighbors = garden_neighbors.get(garden, [])
            # 将相邻花园neighbor添加到相邻花园列表
            neighbors.append(neighbor)
            #  更新键值对花园garden和相邻花园列表neighbors
            garden_neighbors[garden] = neighbors

        def add_neighbor_flower(garden: int, flower: int):
            """
            更新花园garden的相连花园的相邻花园种植花集合
            :param garden:
            :param flower:
            :return:
            """
            # 获取花园garden的相邻花园列表
            neighbors = garden_neighbors.get(garden)
            # 没有相邻花园列表 直接返回
            if neighbors is None:
                return
            for neighbor in neighbors:
                # 从哈希表中获取neighbor的相邻花园种植花集合；如果neighbor不存在，说明这是neighbor的首个相邻花园种植花，新建一个集合
                neighbor_flowers = graden_neighbor_flowers.get(neighbor, set())
                # 将种植花flower添加到相邻花园种植花集合
                neighbor_flowers.add(flower)
                # 更新键值对相邻花园neighbor和它相邻花园种植花集合
                graden_neighbor_flowers[neighbor] = neighbor_flowers

        garden_neighbors = {}  # 相邻花园哈希表，记录每个花园的相邻花园列表
        graden_neighbor_flowers = {}  # 相邻花园种植花哈希表，记录每个花园的相邻花园种的花的种类
        res = []
        for path in paths:
            # 双向路径，path[0]和path[1]互为相邻花园
            add_neighbor(path[0], path[1])
            add_neighbor(path[1], path[0])
        for i in range(1, n + 1):
            # 遍历每一个花园i，i从编号1开始到n
            for f in range(1, 5):
                # 枚举每一种种类的花f
                if i not in graden_neighbor_flowers or f not in graden_neighbor_flowers[i]:
                    # 如果相邻花园种植花哈希表不存在花园i+1，说明其相邻花园都还没种花的，直接种f
                    #  或者相邻花园种植花哈希表存在花园i+1，但是相邻花园种的花没有f，直接种f
                    res.append(f)  # 因为是依次遍历花园i，因此依次追加结果即可
                    add_neighbor_flower(i, f)  # 更新花园i的相邻花园的相邻花园种植花集合
                    break
        return res


obj = Solution()
n = 4
paths = [[1, 2], [2, 3], [3, 4], [4, 1], [1, 3], [2, 4]]
res = obj.gardenNoAdj(n, paths)
print(res)

示例代码2：  【哈希表数组实现】

from typing import List


class Solution:
    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
        g = [[] for _ in range(n)]
        for u, v in paths:
            g[u - 1].append(v - 1)
            g[v - 1].append(u - 1)
        color = [0] * n
        for i, nodes in enumerate(g):
            color[i] = (set(range(1, 5)) - {color[j] for j in nodes}).pop()

        return color


obj = Solution()
n = 4
paths = [[1, 2], [2, 3], [3, 4], [4, 1], [1, 3], [2, 4]]
n = 3
paths = [[1, 2], [2, 3], [3, 1]]
res = obj.gardenNoAdj(n, paths)
print(res)

思路解析：