题目描述
思路解析动画文字版
记住这条主线:建图,按编号逐个花园,挑第一个邻居没用过的花色。最多 3 个邻居占不满 4 种花,所以一定挑得到。
总览 · 5 个花园和它们的小路：先把这张图看明白。五个圆圈是五个花园,编号 1 到 5,圈和圈之间的连线是小路,小路两头的花园算相邻。题目要我们给每个花园种一种花,花一共 4 种,用 1 到 4 表示,要求是:有小路直接相连的两个花园,花色必须不一样。提前把答案说出来,最后这五个花园会依次种上花色 1、2、3、1、3,下面一步一步把它选出来。
关键 · 每个花园最多 3 条小路：动手之前先想清楚一件事,这件事决定了为什么可以放心地贪心。题目保证每个花园最多只有 3 条小路,也就是最多 3 个相邻花园。轮到给某个花园选花时,这最多 3 个邻居,撑死了也只能占用 3 种花色。可我们手里有 4 种花。3 比 4 小,所以不管邻居怎么占,4 种花色里永远至少剩一种是空的。既然总有得选,我们就按花园编号一个个来,每个花园挑一种邻居没用过的花就行,绝不会卡住。
轮到 1 号花园：从 1 号花园开始。先看看它的邻居有没有已经种花的,有的话那些花色就不能用了。1 号的邻居是 2 号和 3 号。
看邻居 2 号：先看邻居 2 号。2 号现在还没轮到,是空地,不会限制 1 号的选择,跳过。
看邻居 3 号：再看邻居 3 号。3 号也还没种花,同样不影响。1 号的两个邻居都看完了,都是空的。
1 号种花色 1：它的两个邻居都还没种花,没有任何花色被占用。那就直接从最小的花色 1 开始挑,花色 1 空着,1 号花园就种花色 1。这是种下的第一朵花。
轮到 2 号花园：轮到 2 号花园。它的小路最多,邻居有三个:1 号、3 号和 5 号,正好卡在最多 3 条的上限。挨个看它们种了什么。
看邻居 1 号：先看邻居 1 号。1 号刚才种的是花色 1,所以花色 1 这会儿对 2 号来说不能用了,把它记下来。
看邻居 3 号：再看邻居 3 号。3 号还没种花,是空地,先跳过。
看邻居 5 号：最后看邻居 5 号。5 号也还没种,同样跳过。三个邻居看完,被占用的只有花色 1。
2 号种花色 2：统计下来,只有花色 1 被邻居占用了。现在从花色 1 往上找第一个没被占的:花色 1 被 1 号占了不能用,花色 2 还空着,2 号花园就种花色 2。
轮到 3 号花园：轮到 3 号花园。它也有三个邻居:1 号、2 号和 4 号。继续一个个看它们用了哪些花色。
看邻居 1 号：先看邻居 1 号,它种的是花色 1,把花色 1 记成被占用。
看邻居 2 号：再看邻居 2 号,它种的是花色 2,花色 2 也被占用了。现在 3 号身边已经有两种花色不能用。
看邻居 4 号：最后看邻居 4 号,它还没种花,跳过。这一轮被占用的是花色 1 和花色 2。
3 号种花色 3：邻居一共占用了花色 1 和花色 2。从 1 往上找:花色 1 被占,花色 2 也被占,花色 3 终于空着,3 号花园就种花色 3。你看,贪心会自动跳过被占的花色,挑到第一个能用的。
轮到 4 号花园：轮到 4 号花园,邻居是 3 号和 5 号。看它们的花色。
看邻居 3 号：先看邻居 3 号,它刚种的是花色 3,把花色 3 记成被占用。
看邻居 5 号：再看邻居 5 号,它还没种花,跳过。这一轮只有花色 3 被占。
4 号种花色 1：只有花色 3 被占用。从花色 1 开始找,花色 1 空着就能用,4 号花园种花色 1。这里有个重点:4 号和 1 号都种了花色 1,但它们之间没有小路相连,不相邻的花园花色完全可以重复,这正是只用 4 种花就够的原因。
轮到 5 号花园：最后轮到 5 号花园,它的邻居是 4 号和 2 号。看完这两个就大功告成了。
看邻居 4 号：先看邻居 4 号,它种的是花色 1,记下花色 1 被占。
看邻居 2 号：再看邻居 2 号,它种的是花色 2,花色 2 也被占。5 号身边有两种花色不能用。
5 号种花色 3：邻居占用了花色 1 和花色 2。从 1 往上找,花色 1 被占,花色 2 被占,花色 3 空着,5 号花园种花色 3。五个花园全部种好。
完成 · 对照答案：五个花园全部种好,花色依次是 1、2、3、1、3。回头沿着每条小路验一遍:1 号花色 1 和 2 号花色 2 不同,1 号和 3 号花色 3 不同,2 号和 3 号不同,3 号和 4 号花色 1 不同,4 号和 5 号花色 3 不同,2 号和 5 号也不同,全部小路两头都不一样,符合要求。整道题就一句话:因为每个花园最多 3 个邻居、却有 4 种花,所以按编号一个个贪心地避开邻居用过的花色,一定能种满,永远不会卡住。
边界想清:没有小路时人人种花色 1;三个花园围成三角时被迫用三种花色,贪心都能正确给出。
面试重点:4 种花比最大度数 3 多一,这个余量让贪心免回溯;若花色减到 3 就可能卡住,退回到一般图着色。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]: g = defaultdict(list) for x, y in paths: x, y = x - 1, y - 1 g[x].append(y) g[y].append(x) ans = [0] * n for x in range(n): used = {ans[y] for y in g[x]} for c in range(1, 5): if c not in used: ans[x] = c break return ans复杂度
- 时间：O(n + m)，n 是花园数,m 是小路条数。建邻接表遍历所有小路是 O(m);主循环对每个花园看它的全部邻居,所有花园的邻居总数等于边数的两倍,加上每园固定挑 4 种花色,合起来是 O(n + m)
- 空间：O(n + m)，邻接表存下全部边,占 O(n + m);答案数组 O(n);标记花色用的布尔数组只有 5 个位置,是常数,可忽略
易错点
面试追问把动画讲成自己的话
追问这道题为什么不需要回溯或者更复杂的图着色算法?
追问如果把花的种类从 4 改成 3,这套贪心还成立吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
按字典序排列最小的等效字符串
LeetCode 1061 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题