[Leetcode 1042] Flower Planting With No Adjacent

原题说明

You have N gardens, labelled 1 to N. In each garden, you want to plant one of 4 types of flowers.

paths[i] = [x, y] describes the existence of a bidirectional path from garden x to garden y.

Also, there is no garden that has more than 3 paths coming into or leaving it.

Your task is to choose a flower type for each garden such that, for any two gardens connected by a path, they have different types of flowers.

Return any such a choice as an array answer, where answer[i] is the type of flower planted in the (i+1)-th garden. The flower types are denoted 1, 2, 3, or 4. It is guaranteed an answer exists.

Example 1:

Input: N = 3, paths = [[1,2],[2,3],[3,1]]
Output: [1,2,3]

Example 2:

Input: N = 4, paths = [[1,2],[3,4]]
Output: [1,2,1,2]

Example 3:

Input: N = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
Output: [1,2,3,4]

Note:

1 <= N <= 10000
0 <= paths.size <= 20000
No garden has 4 or more paths coming into or leaving it.
It is guaranteed an answer exists.

解题思路

这道题相当与给我们N个点，每个点最多与图中另外三个点相连，要求我们用4种颜色给图染色，同时任意一条边上的2个点不能是相同的颜色。

因为题目保证了一定存在解，所以我们只要搜索出一种染色方法就可以了。对于一个图，它一定是由若干个最大连通子图组成的。任意两个不同的连通图，它们之间的染色互相不影响。而我们对每个连通图，分别做一次dfs就可以把这个连通图中所有的点做一次满足要求的染色，并把结果保存到我们返回的染色数组中即可。

示例代码 (cpp)

Java和Python代码与C++略有不同，但主题思想是一致的。

class Solution {
public:
    vector<int> gardenNoAdj(int N, vector<vector<int>>& paths) {
        vector<int> ans(N, 0);
        unordered_map<int, unordered_set<int>> edges;
        for (auto path : paths) {
            edges[path[0] - 1].insert(path[1] - 1);
            edges[path[1] - 1].insert(path[0] - 1);
        }
        for (auto i = 0; i < N; ++i) {
            if (edges.count(i) == 0) {
                ans[i] = 1;
            }
            else if (ans[i] == 0) {
                color(ans, edges, i);
            }
        }
        return ans;
    }
    void color(vector<int>& ans, unordered_map<int, unordered_set<int>>& edges, int i) {
        for (int c = 1; c <= 4; ++c) {
            bool canColor = true;
            for (auto next : edges[i]) {
                if (ans[next] == c) {
                    canColor = false;
                    break;
                }
            }
            if (canColor) {
                ans[i] = c;
                break;
            }
        }
        for (auto next : edges[i]) {
            if (ans[next] == 0) {
                color(ans, edges, next);
            }
        }
    }
};

示例代码 (java)

class Solution {
    public int[] gardenNoAdj(int N, int[][] paths) {
        Map<Integer, Set<Integer>> G = new HashMap<>();
        for (int i = 0; i < N; i++) G.put(i, new HashSet<>());
        for (int[] p : paths) {
            G.get(p[0] - 1).add(p[1] - 1);
            G.get(p[1] - 1).add(p[0] - 1);
        }
        int[] res = new int[N];
        for (int i = 0; i < N; i++) {
            int[] colors = new int[5];
            for (int j : G.get(i))
                colors[res[j]] = 1;
            for (int c = 4; c > 0; --c)
                if (colors[c] == 0)
                    res[i] = c;
        }
        return res;
    }
}

示例代码 (python)

class Solution(object):
    def gardenNoAdj(self, N, paths):
        """
        :type N: int
        :type paths: List[List[int]]
        :rtype: List[int]
        """
        g = collections.defaultdict(list)
        for x, y in paths:
            g[x].append(y)
            g[y].append(x)
        plantdict = {i: 0 for i in range(1, N + 1)}
        for garden in g: 
            pick = set(range(1,5))
            for each in g[garden]:
                if plantdict[each] != 0 and plantdict[each] in pick:
                    pick.remove(plantdict[each])
            plantdict[garden] = pick.pop()
        return [plantdict[x] if plantdict[x] != 0 else 1 for x in range(1, N+1)]

复杂度分析

时间复杂度: 每个点都会被visit一次，同时每次visit一个点，都会同时检查它连接的最多3个点。因此，时间复杂度就是O(N + 3*N) = O(N)
空间复杂度: O(N)

归纳总结

我们在Youtube上更新了视频讲解，欢迎关注！