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 <= 1040 <= paths.length <= 2 * 104paths[i].length == 21 <= xi, yi <= nxi != 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/
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
