不邻接植花 图解题解

这道题到底在问什么

输入

n = 3, paths = [[1,2],[2,3],[3,1]]

输出

[1,2,3]（三个花园两两相连,围成一个三角,所以三种花色全不同）

先想最直接的笨办法

轮到 2 号花园。它的小路最多,邻居有三个:1 号、3 号和 5 号,正好卡在最多 3 条的上限。挨个看它们种了什么。（动画第 10 步）

最优解：一步一步想明白

1. 3记住这条主线:建图,按编号逐个花园,挑第一个邻居没用过的花色。最多 3 个邻居占不满 4 种花,所以一定挑得到。
2. 4目标:相邻花园花色不同,每园从 4 种花里选一种先把这张图看明白。五个圆圈是五个花园,编号 1 到 5,圈和圈之间的连线是小路,小路两头的花园算相邻。题目要我们给每个花园种一种花,花一共 4 种,用 1 到 4 表示,要求是:有小路直接相连的两个花园,花色必须不一样。提前把答案说出来,最后这五个花园会依次种上花色 1、2、3、1、3,下面一步一步把它选出来。
3. 5最多 3 个邻居 → 最多占 3 种花色 → 4 种里必有空位动手之前先想清楚一件事,这件事决定了为什么可以放心地贪心。题目保证每个花园最多只有 3 条小路,也就是最多 3 个相邻花园。轮到给某个花园选花时,这最多 3 个邻居,撑死了也只能占用 3 种花色。可我们手里有 4 种花。3 比 4 小,所以不管邻居怎么占,4 种花色里永远至少剩一种是空的。既然总有得选,我们就按花园编号一个个来,每个花园挑一种邻居没用过的花就行,绝不会卡住。
4. 6看 1 号的邻居都种了什么花从 1 号花园开始。先看看它的邻居有没有已经种花的,有的话那些花色就不能用了。1 号的邻居是 2 号和 3 号。
5. 7邻居 2 号还没种花先看邻居 2 号。2 号现在还没轮到,是空地,不会限制 1 号的选择,跳过。
6. 8邻居 3 号还没种花再看邻居 3 号。3 号也还没种花,同样不影响。1 号的两个邻居都看完了,都是空的。
7. 9从花色 1 到 4 选第一个没被占的 → 花色 1它的两个邻居都还没种花,没有任何花色被占用。那就直接从最小的花色 1 开始挑,花色 1 空着,1 号花园就种花色 1。这是种下的第一朵花。
8. 10看 2 号的邻居都种了什么花轮到 2 号花园。它的小路最多,邻居有三个:1 号、3 号和 5 号,正好卡在最多 3 条的上限。挨个看它们种了什么。
9. 11邻居 1 号种的是花色 1先看邻居 1 号。1 号刚才种的是花色 1,所以花色 1 这会儿对 2 号来说不能用了,把它记下来。
10. 12邻居 3 号还没种花再看邻居 3 号。3 号还没种花,是空地,先跳过。
11. 13邻居 5 号还没种花最后看邻居 5 号。5 号也还没种,同样跳过。三个邻居看完,被占用的只有花色 1。
12. 14从花色 1 到 4 选第一个没被占的 → 花色 2统计下来,只有花色 1 被邻居占用了。现在从花色 1 往上找第一个没被占的:花色 1 被 1 号占了不能用,花色 2 还空着,2 号花园就种花色 2。
13. 15看 3 号的邻居都种了什么花轮到 3 号花园。它也有三个邻居:1 号、2 号和 4 号。继续一个个看它们用了哪些花色。
14. 16邻居 1 号种的是花色 1先看邻居 1 号,它种的是花色 1,把花色 1 记成被占用。
15. 17邻居 2 号种的是花色 2再看邻居 2 号,它种的是花色 2,花色 2 也被占用了。现在 3 号身边已经有两种花色不能用。
16. 18邻居 4 号还没种花最后看邻居 4 号,它还没种花,跳过。这一轮被占用的是花色 1 和花色 2。
17. 19从花色 1 到 4 选第一个没被占的 → 花色 3邻居一共占用了花色 1 和花色 2。从 1 往上找:花色 1 被占,花色 2 也被占,花色 3 终于空着,3 号花园就种花色 3。你看,贪心会自动跳过被占的花色,挑到第一个能用的。
18. 20看 4 号的邻居都种了什么花轮到 4 号花园,邻居是 3 号和 5 号。看它们的花色。
19. 21邻居 3 号种的是花色 3先看邻居 3 号,它刚种的是花色 3,把花色 3 记成被占用。
20. 22邻居 5 号还没种花再看邻居 5 号,它还没种花,跳过。这一轮只有花色 3 被占。
21. 23从花色 1 到 4 选第一个没被占的 → 花色 1只有花色 3 被占用。从花色 1 开始找,花色 1 空着就能用,4 号花园种花色 1。这里有个重点:4 号和 1 号都种了花色 1,但它们之间没有小路相连,不相邻的花园花色完全可以重复,这正是只用 4 种花就够的原因。
22. 24看 5 号的邻居都种了什么花最后轮到 5 号花园,它的邻居是 4 号和 2 号。看完这两个就大功告成了。
23. 25邻居 4 号种的是花色 1先看邻居 4 号,它种的是花色 1,记下花色 1 被占。
24. 26邻居 2 号种的是花色 2再看邻居 2 号,它种的是花色 2,花色 2 也被占。5 号身边有两种花色不能用。
25. 27从花色 1 到 4 选第一个没被占的 → 花色 3邻居占用了花色 1 和花色 2。从 1 往上找,花色 1 被占,花色 2 被占,花色 3 空着,5 号花园种花色 3。五个花园全部种好。
26. 28答案 answer = [1, 2, 3, 1, 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 种花,所以按编号一个个贪心地避开邻居用过的花色,一定能种满,永远不会卡住。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from 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

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
        vector<vector<int>> g(n);
        for (auto& p : paths) {
            int x = p[0] - 1, y = p[1] - 1;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        vector<int> ans(n);
        bool used[5];
        for (int x = 0; x < n; ++x) {
            memset(used, false, sizeof(used));
            for (int y : g[x]) {
                used[ans[y]] = true;
            }
            for (int c = 1; c < 5; ++c) {
                if (!used[c]) {
                    ans[x] = c;
                    break;
                }
            }
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int[] gardenNoAdj(int n, int[][] paths) {
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int[] p : paths) {
            int x = p[0] - 1, y = p[1] - 1;
            g[x].add(y);
            g[y].add(x);
        }
        int[] ans = new int[n];
        boolean[] used = new boolean[5];
        for (int x = 0; x < n; ++x) {
            Arrays.fill(used, false);
            for (int y : g[x]) {
                used[ans[y]] = true;
            }
            for (int c = 1; c < 5; ++c) {
                if (!used[c]) {
                    ans[x] = c;
                    break;
                }
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问