[LeetCode] 1042. Flower Planting With No Adjacent

[grandyang]

You have n gardens, labeled from 1 to n, and an array paths where paths[i] = [xi, yi] describes a bidirectional path between garden xi to garden yi. In each garden, you want to plant one of 4 types of flowers.

All gardens have at most 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]
Explanation:
Gardens 1 and 2 have different types.
Gardens 2 and 3 have different types.
Gardens 3 and 1 have different types.
Hence, [1,2,3] is a valid answer. Other valid answers include [1,2,4], [1,4,2], and [3,2,1].

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]

Constraints:

• 1 <= n <= 104
• 0 <= paths.length <= 2 * 104
• paths[i].length == 2
• 1 <= xi, yi <= n
• xi != yi
• Every garden has at most 3 paths coming into or leaving it.

这道题说是有n个花园，标号分别是1到n，现在有个二维数组 paths，标记了哪些花园是相连通的，限定了每个花园最多只能连通三个其他的花园。现在要给每个花园选择一种颜色的花来种，可供选择的颜色只有四种，编号1到4，要求相连的花园不能种相同颜色的花，现在让返回一种选择花颜色的方式。题目说了一定有合理的解，这是为啥呢？因为限定了每个花园最多只能连通其他三个花园，而总共可有四种颜色可以选择，最坏情况就是相连的三个花园各自的颜色都不同，但总还是有一种颜色可以供当前的花园选择。这道题可以用贪婪算法来做，为了快速知道每个花园都和其他哪些花园相连，需要建立一个无向图结构，这里可以使用邻接矩阵来做。由于花园的序号是从1开始的，建立邻接矩阵的时候统一都减1。然后遍历每个花园，由于知道了其相邻的花园，就可以知道它们种的花的颜色。这里使用一个布尔型的数组 colors，来标记某种颜色是否被使用，大小为5，因为颜色是从1开始的。将相邻的花园对应的颜色标记为 true，然后从颜色4开始往前遍历，只要某种颜色没有被使用，就赋值给当前花园即可，参见代码如下：

class Solution {
public:
    vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
        vector<int> res(n);
        vector<vector<int>> graph(n);
        for (auto &path : paths) {
            graph[path[0] - 1].push_back(path[1] - 1);
            graph[path[1] - 1].push_back(path[0] - 1);
        }
        for (int i = 0; i < n; ++i) {
            vector<bool> colors(5);
            for (int j : graph[i]) colors[res[j]] = true;
            for (int c = 4; c > 0; --c) {
                if (!colors[c]) res[i] = c;
            }
        }
        return res;
    }
};

Github 同步地址:

#1042

参考资料：

https://leetcode.com/problems/flower-planting-with-no-adjacent/

https://leetcode.com/problems/flower-planting-with-no-adjacent/discuss/327959/Lee's-Solution-with-Comments

https://leetcode.com/problems/flower-planting-with-no-adjacent/discuss/290858/JavaC%2B%2BPython-Greedily-Paint

LeetCode All in One 题目讲解汇总(持续更新中...)