LeetCode 1042. 不邻接植花

字数 2152 2025-12-09 03:07:36

LeetCode 1042. 不邻接植花

题目描述

有 n 个花园，按从 1 到 n 编号。每个花园最多有 3 条双向路径与其他花园相连。你需要为每个花园选择一种花（共有 4 种花，用 1、2、3、4 表示），使得任意两个有路径直接相连的花园没有相同类型的花。题目保证至少存在一种可行方案。

给定整数 n（花园数量）和数组 paths（每个元素 [x, y] 表示花园 x 和花园 y 之间有一条路径），你需要返回任意一个满足条件的种花方案数组 answer，其中 answer[i] 表示第 i+1 号花园（因为数组索引从 0 开始）所种的花的类型。

解题思路分析

这个问题本质上是一个图的着色问题，但有两个关键简化条件：

每个花园最多只有 3 条路径（即图中每个节点的度数最多为 3）。
有 4 种颜色（花类型）可用。

由于每个节点最多有 3 个邻居，而可用颜色有 4 种，因此无论邻居如何选择，当前节点总能至少找到一种可用的颜色。这避免了回溯的需要，使得我们可以贪心地为每个花园依次选择一种不与邻居冲突的花。

核心步骤：

构建邻接表来表示花园之间的连接关系。
从 1 号花园开始，依次为每个花园选择一种花。
对于当前花园，检查其所有邻居已经使用的花色，然后从 4 种颜色中排除这些颜色，选择剩余的第一个可用颜色。
重复直到所有花园都完成着色。

详细解题步骤

步骤 1：理解输入与输出

输入：n = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
- 表示 4 个花园，它们之间路径形成了一个完全图（每个花园都与其他三个相连）。
输出：一个长度为 n 的数组，例如 [1,2,3,4]（有多种可能，输出一种即可）。

步骤 2：构建邻接表

由于花园编号从 1 开始，而数组索引从 0 开始，为了方便，我们在代码中通常会将花园编号 i 映射到索引 i-1。
邻接表 graph[i] 存储与花园 i 相邻的所有花园编号（存储编号或索引皆可，但要保持一致性）。

示例构建过程：

对于 paths 中的每条边 [u, v]：
- 将 v 添加到 graph[u] 的邻居列表中。
- 将 u 添加到 graph[v] 的邻居列表中。
这样我们就得到了每个花园的邻居集合。

步骤 3：贪心选择花色

初始化一个长度为 n 的数组 color，全部设为 0（表示未着色）。
遍历每个花园 i（从 1 到 n）：
1. 创建一个集合 used，用于记录当前花园所有邻居已经使用的花色。
2. 遍历花园 i 的所有邻居 j：
  - 如果邻居 j 已经着色（即 color[j-1] != 0），则将 color[j-1] 加入 used 集合。
3. 从 1 到 4 检查四种颜色，找到第一个不在 used 集合中的颜色 c。
4. 将 color[i-1] 设为 c。

为什么贪心是可行的？

因为每个花园最多有 3 个邻居，最多占用 3 种颜色，而我们有 4 种颜色，所以第 4 种颜色一定可用。
由于我们按顺序着色，当前花园只关心已经着色的邻居（后面的邻居还未着色，不会影响当前选择）。

步骤 4：输出结果

数组 color 即为所求，表示每个花园（索引 i 对应花园 i+1）的花色。

举例说明

以 n = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]] 为例：

构建邻接表：
- 花园 1 的邻居: [2, 4, 3]
- 花园 2 的邻居: [1, 3, 4]
- 花园 3 的邻居: [2, 4, 1]
- 花园 4 的邻居: [3, 1, 2]
开始着色（顺序从花园 1 到 4）：
- 花园 1：邻居都未着色，used = {}，选择颜色 1 → color[0] = 1
- 花园 2：邻居 1 已用颜色 1，used = {1}，选择颜色 2 → color[1] = 2
- 花园 3：邻居 1（颜色 1）、邻居 2（颜色 2），used = {1, 2}，选择颜色 3 → color[2] = 3
- 花园 4：邻居 1（颜色 1）、邻居 2（颜色 2）、邻居 3（颜色 3），used = {1, 2, 3}，选择颜色 4 → color[3] = 4
结果：[1, 2, 3, 4]。

算法复杂度

时间复杂度：O(n + m)，其中 n 是花园数，m 是路径数（即 paths 的长度）。我们遍历每个花园一次，并为每个花园检查其所有邻居（总邻居数为 2m，因为每条边算两个邻居关系）。
空间复杂度：O(n + m)，用于存储邻接表和颜色数组。

关键点总结

利用度数 ≤ 3 和颜色数 = 4 的条件，保证了贪心算法的正确性。
无需回溯，直接顺序选择即可。
注意花园编号从 1 开始，而数组索引从 0 开始的转换。
如果度数可能大于 3，则问题会变成经典的图着色问题（NP难），需要回溯或更复杂的算法。但本题条件保证了简单性。

LeetCode 1042. 不邻接植花题目描述有 n 个花园，按从 1 到 n 编号。每个花园最多有 3 条双向路径与其他花园相连。你需要为每个花园选择一种花（共有 4 种花，用 1、2、3、4 表示），使得任意两个有路径直接相连的花园没有相同类型的花。题目保证至少存在一种可行方案。给定整数 n （花园数量）和数组 paths （每个元素 [x, y] 表示花园 x 和花园 y 之间有一条路径），你需要返回任意一个满足条件的种花方案数组 answer ，其中 answer[i] 表示第 i+1 号花园（因为数组索引从 0 开始）所种的花的类型。解题思路分析这个问题本质上是一个图的着色问题，但有两个关键简化条件：每个花园最多只有 3 条路径（即图中每个节点的度数最多为 3）。有 4 种颜色（花类型）可用。由于每个节点最多有 3 个邻居，而可用颜色有 4 种，因此无论邻居如何选择，当前节点总能至少找到一种可用的颜色。这避免了回溯的需要，使得我们可以贪心地为每个花园依次选择一种不与邻居冲突的花。核心步骤：构建邻接表来表示花园之间的连接关系。从 1 号花园开始，依次为每个花园选择一种花。对于当前花园，检查其所有邻居已经使用的花色，然后从 4 种颜色中排除这些颜色，选择剩余的第一个可用颜色。重复直到所有花园都完成着色。详细解题步骤步骤 1：理解输入与输出输入： n = 4 , paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]] 表示 4 个花园，它们之间路径形成了一个完全图（每个花园都与其他三个相连）。输出：一个长度为 n 的数组，例如 [1,2,3,4] （有多种可能，输出一种即可）。步骤 2：构建邻接表由于花园编号从 1 开始，而数组索引从 0 开始，为了方便，我们在代码中通常会将花园编号 i 映射到索引 i-1 。邻接表 graph[i] 存储与花园 i 相邻的所有花园编号（存储编号或索引皆可，但要保持一致性）。示例构建过程：对于 paths 中的每条边 [u, v] ：将 v 添加到 graph[u] 的邻居列表中。将 u 添加到 graph[v] 的邻居列表中。这样我们就得到了每个花园的邻居集合。步骤 3：贪心选择花色初始化一个长度为 n 的数组 color ，全部设为 0（表示未着色）。遍历每个花园 i （从 1 到 n ）：创建一个集合 used ，用于记录当前花园所有邻居已经使用的花色。遍历花园 i 的所有邻居 j ：如果邻居 j 已经着色（即 color[j-1] != 0 ），则将 color[j-1] 加入 used 集合。从 1 到 4 检查四种颜色，找到第一个不在 used 集合中的颜色 c 。将 color[i-1] 设为 c 。为什么贪心是可行的？因为每个花园最多有 3 个邻居，最多占用 3 种颜色，而我们有 4 种颜色，所以第 4 种颜色一定可用。由于我们按顺序着色，当前花园只关心已经着色的邻居（后面的邻居还未着色，不会影响当前选择）。步骤 4：输出结果数组 color 即为所求，表示每个花园（索引 i 对应花园 i+1 ）的花色。举例说明以 n = 4 , paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]] 为例：构建邻接表：花园 1 的邻居: [ 2, 4, 3 ] 花园 2 的邻居: [ 1, 3, 4 ] 花园 3 的邻居: [ 2, 4, 1 ] 花园 4 的邻居: [ 3, 1, 2 ] 开始着色（顺序从花园 1 到 4）：花园 1：邻居都未着色， used = {} ，选择颜色 1 → color[0] = 1 花园 2：邻居 1 已用颜色 1， used = {1} ，选择颜色 2 → color[1] = 2 花园 3：邻居 1（颜色 1）、邻居 2（颜色 2）， used = {1, 2} ，选择颜色 3 → color[2] = 3 花园 4：邻居 1（颜色 1）、邻居 2（颜色 2）、邻居 3（颜色 3）， used = {1, 2, 3} ，选择颜色 4 → color[3] = 4 结果： [1, 2, 3, 4] 。算法复杂度时间复杂度：O(n + m)，其中 n 是花园数，m 是路径数（即 paths 的长度）。我们遍历每个花园一次，并为每个花园检查其所有邻居（总邻居数为 2m，因为每条边算两个邻居关系）。空间复杂度：O(n + m)，用于存储邻接表和颜色数组。关键点总结利用度数 ≤ 3 和颜色数 = 4 的条件，保证了贪心算法的正确性。无需回溯，直接顺序选择即可。注意花园编号从 1 开始，而数组索引从 0 开始的转换。如果度数可能大于 3，则问题会变成经典的图着色问题（NP难），需要回溯或更复杂的算法。但本题条件保证了简单性。