1042. Flower Planting With No Adjacent

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  123 , 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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation