不邻接植花

标签: 深度优先搜索 广度优先搜索 图

难度: Medium

有 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]

提示：

  • 1 <= n <= 104
  • 0 <= paths.length <= 2 * 104
  • paths[i].length == 2
  • 1 <= xi, yi <= n
  • xi != yi
  • 每个花园 最多 有 3 条路径可以进入或离开

Submission

运行时间: 66 ms

内存: 20.9 MB

class Solution:
    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
        if n <= 4:
            return([i + 1 for i in range(n)])
        res = [1] * n
        dic = {}
        for x, y in paths:
            if x > y:
                if x in dic:
                    dic[x].append(y)
                else:
                    dic[x] = [y]
            else:
                if y in dic:
                    dic[y].append(x)
                else:
                    dic[y] = [x]

        for i in range(2, n + 1):
            if i in dic:
                s = set([res[v - 1] for v in dic[i]])
                for v in range(1, 5):
                    if v not in s:
                        res[i - 1] = v
                        break
        return(res)

Explain

此题解通过首先为每个花园分配默认的花的种类1，然后根据花园之间的路径调整花的种类以满足题目要求。首先，题解构建了一个字典来存储每个花园与其相连的其他花园。字典的键是花园编号，值是与该花园连接的其他花园的列表。接着，从第二个花园开始检查（因为第一个花园默认种植第一种花），若当前花园已经记录在字典中，则获取与之相连的所有花园已种植的花的种类，然后从四种花中选择一个未被相邻花园使用的花种植在当前花园中。这样遍历所有花园后，可以得到一个符合条件的花园种花方案。

时间复杂度: O(N + P)

空间复杂度: O(N + P)

class Solution:
    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
        # 基本情况，当花园数量不超过4个时，直接分配1到n的花种
        if n <= 4:
            return([i + 1 for i in range(n)])
        # 初始化种花结果，所有花园先默认种第一种花
        res = [1] * n
        # 构建字典，用于记录每个花园的相连花园
        dic = {}
        for x, y in paths:
            if x > y:
                if x in dic:
                    dic[x].append(y)
                else:
                    dic[x] = [y]
            else:
                if y in dic:
                    dic[y].append(x)
                else:
                    dic[y] = [x]

        # 从第二个花园开始，调整花园的花的种类以符合题目要求
        for i in range(2, n + 1):
            if i in dic:
                # 获取当前花园相连的所有花园已种植的花的种类
                s = set([res[v - 1] for v in dic[i]])
                # 从四种花中选择一个未使用的花种植在当前花园
                for v in range(1, 5):
                    if v not in s:
                        res[i - 1] = v
                        break
        return(res)

Explore

并不是这样。题解中当花园数量不超过4个时直接分配1到n的花种，是基于最多每个花园可以种植4种花的规则。即使存在路径连接，由于每个花园可以选择的花的种类数量等于或多于花园的总数，我们总是能为每个花园找到一个合适的花种，保证相邻花园种植的花不相同。这一处理简化了逻辑，不需要考虑具体的路径连接情况。

这种处理方式是为了确保花园编号较小的花园总是作为字典的键，而与之相连的较大编号的花园作为值中的元素。这样的处理保证了无论路径如何给出（x与y的大小关系），花园之间的连接信息都能被统一且正确地记录。这种方式不影响最终结果，只是一种确保字典构建一致性和查询效率的方法。

题解中没有明确提到每个花园最多有3条路径的限制，因此该算法适用于任何数量的路径。若确实存在这样的限制，算法仍然可以正常工作，因为它不依赖于路径的数量来进行逻辑处理，而是依赖于能够为每个花园选择一个未被相邻花园使用的花。如果路径多于3条，只要保证选择的花不与相邻花园重复，算法仍然有效。

使用for循环查找1到4中未被相邻花园使用的花是一种简单直观的方法，可以快速遍历所有可能的花种并选择一个合适的。考虑到每个花园最多只需考虑4种花，这种方法在时间复杂度上是有效的（O(1)复杂度）。虽然存在更优化的数据结构如位运算来进一步减少时间复杂度，但在只有4种花的情况下，这种简单的方法已经足够高效，并且代码的可读性更好。