https://leetcode.com/problems/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 <= 100000 <= paths.size <= 20000- No garden has 4 or more paths coming into or leaving it.
- It is guaranteed an answer exists.
https://blog.csdn.net/u013383813/article/details/90146538
存在N个花园，给定int[][] paths 为花园的连接关系。每个花园至多只能与其他3个花园连接。
要求为每个花园指定1 - 4 种 颜色，使得相邻花园的颜色不同。
将 paths，转化为 图 表示。
查看每个节点，看起相邻的点已经使用了 4 种颜色的哪种，然后选择一种未使用的颜色给自己涂色。
查看每个节点，看起相邻的点已经使用了 4 种颜色的哪种，然后选择一种未使用的颜色给自己涂色。
解题思路：可供选的花的种类只有[1,2,3,4]四种，对于任意一个待种植的花园，只需要判断相邻的花园是否已经种植花卉。如果种植了，把已种植的种类从可供选择的列表中去除，最后在剩余的种类中任选一个即可。
Time complexity: O(|V|+|E|)
Space complexity: O(|V|+|E|)
public int[] gardenNoAdj(int N, int[][] paths) { List<Integer>[] graph = new List[N+1]; for(int[] path : paths){ if(graph[path[0]] == null) graph[path[0]] = new LinkedList<Integer>(); graph[path[0]].add(path[1]); if(graph[path[1]] == null) graph[path[1]] = new LinkedList<Integer>(); graph[path[1]].add(path[0]); } int[] cols = new int[N]; Set<Integer> set = new HashSet(); for(int i = 1 ; i <= N;i++){ if(graph[i] == null || cols[i-1]!=0) continue; set.clear(); for(int nNode:graph[i]){ if(cols[nNode-1]!=0) set.add(cols[nNode-1]); } for(int index = 1;index <= 4 && cols[i-1] == 0 ;index++) if(!set.contains(index)){ cols[i-1] = index; } } for(int i = 0 ; i<N;i++) if(cols[i] == 0) cols[i] =1; return cols; }https://leetcode.com/problems/flower-planting-with-no-adjacent/discuss/290858/JavaC%2B%2BPython-Greedily-Paint
Greedily paint nodes one by one.
Because there is no node that has more than 3 neighbors,
always one possible color to choose.
Because there is no node that has more than 3 neighbors,
always one possible color to choose.
Complexity
Time
Space
O(N) with O(paths) = O(1.5N)Space
O(N) 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;
}http://www.noteanddata.com/leetcode-1042-Flower-Planting-With-No-Adjacent-java-solution-note.html
- 有1到N编号的花， 然后有一些边表示哪些花相邻， 相邻的花颜色不能一样； 总共有4种花的颜色， 题目保证一定存在一个合法解， 求一个合法的解
- 可以归类为染色问题。 这个题目的好处是答案一定是存在的
- 这个我自己是dfs做的， 后来看了下， 直接一层循环遍历也可以（贪心思想？）？
- dfs的思路， 第一个节点，可以随便选, 后面，就根据前面选择的颜色来排除。 如果没有排除， 那么也可以在剩下的里面任意选， 因为颜色都是对等的。 dfs的话，处理完有边的节点以后，还要继续看一下是否有没有边的节点
- 贪心的思路，是指对每一个节点，直接看下有没有相邻边的颜色，没有的话随便选； 一路遍历过去就是可以的
public int[] gardenNoAdj(int N, int[][] paths) { Map<Integer, Set<Integer>> graph = new HashMap<>(); for(int[] path: paths) { graph.compute(path[0], (k,v)->{ if(null == v) v = new HashSet<>(); v.add(path[1]); return v; }); graph.compute(path[1], (k,v)->{ if(null == v) v = new HashSet<>(); v.add(path[0]); return v; }); } int[] table = new int[N]; for(int i = 1; i <= N; ++i) { Set<Integer> candidates = Stream.of(1,2,3,4).collect(Collectors.toSet()); Set<Integer> nextSet = graph.get(i); if(null != nextSet) { for(int next: nextSet) { candidates.remove(table[next-1]); } } table[i-1] = candidates.iterator().next(); } return table; }
https://leetcode.com/problems/flower-planting-with-no-adjacent/discuss/291026/Java-greedy-clear-code
public int[] gardenNoAdj(int N, int[][] paths) {
Map<Integer, Set<Integer>> map = new HashMap<>();
for (int i = 1; i <= N; i++) map.put(i, new HashSet<>());
for (int[] edge: paths) {
map.get(edge[0]).add(edge[1]);
map.get(edge[1]).add(edge[0]);
}
int[] ans = new int[N];
for (int i = 1; i <= N; i++) {
Set<Integer> set = new HashSet<>();
for (int k = 1; k <= 4; k++) set.add(k);
for (int next : map.get(i)) {
if (set.contains(ans[next - 1])) set.remove(ans[next - 1]);
}
ans[i - 1] = set.iterator().next();
}
return ans;
}
Basic idea: adjust the color of nodes whenever two nodes have the same color. Initialy, every node has color 1.
public int[] gardenNoAdj(int n, int[][] paths) {
int[] result = new int[n];
Arrays.fill(result, 1);
boolean stop = false;
do {
stop = true;
for(int[] edge: paths) {
int u = Math.min(edge[0], edge[1]);
int v = Math.max(edge[0], edge[1]);
if (result[u - 1] == result[v - 1]) {
stop = false;
result[v - 1] = result[v - 1] == 4 ? 1 : result[v - 1] + 1;
}
}
}
while(!stop);
return result;
} 