【图】【Map】【数组】
有 N 个花园，按从 1 到 N 标记。在每个花园中，你打算种下四种花之一。
paths[i] = [x, y] 描述了花园 x 到花园 y 的双向路径。
另外，没有花园有 3 条以上的路径可以进入或者离开。
你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。
以数组形式返回选择的方案作为答案 answer，其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用 1, 2, 3, 4 表示。保证存在答案。
Example:
示例 1：
输入：N = 3, paths = [[1,2],[2,3],[3,1]]
输出：[1,2,3]
示例 2：
输入：N = 4, paths = [[1,2],[3,4]]
输出：[1,2,1,2]
示例 3：
输入：N = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
输出：[1,2,3,4]
提示：
1 <= N <= 100000 <= paths.size <= 20000- 不存在花园有 4 条或者更多路径可以进入或离开。
- 保证存在答案。
Analysis
这是一道简单题，限制每个节点的度为3，同时提供四种颜色，因此不需要回溯
- 存储邻接点信息
- 遍历所有节点，对于每个节点
- 查看其邻接点颜色，使用不同的颜色染色即可
Solution 【图】【Map】 ( 96ms)
执行用时 : 96 ms, 在Flower Planting With No Adjacent的Java提交中击败了30.59% 的用户
内存消耗 : 66.4 MB, 在Flower Planting With No Adjacent的Java提交中击败了100.00% 的用户
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
class Solution {
public int[] gardenNoAdj(int N, int[][] paths) {
/* 这是一道简单题，限制每个节点的度为3，同时提供四种颜色，因此不需要回溯 */
/* 初始化节点，使用map保存节点与其临界点的关系 */
/* 第一版本采用了内部类构建，参考评论区的HashMap更简洁 */
Map<Integer, Set<Integer>> graph = new HashMap<>();
for (int i = 0; i < N; i++) {
graph.put(i, new HashSet<>());
}
/* 初始化路径信息 */
for (int[] path: paths) {
int a = path[0] - 1;
int b = path[1] - 1;
graph.get(a).add(b);
graph.get(b).add(a);
}
int[] res = new int[N];
for (int i = 0; i < N; i++) {
boolean[] used = new boolean[5];
/* 查看当前节点的所有邻接点的色彩 */
for (int adj: graph.get(i)) {
used[res[adj]] = true;
}
/* 为当前节点染色 */
for (int j = 1; j <= 4; j++) {
if (!used[j]) {
res[i] = j;
}
}
}
return res;
}
}
|
复杂度分析
时间：$O(|V| + |E|)$
对每个节点，都要查看（共|V|次）其邻接点，需要查看 2|E| 次
可能不太对
空间：$O(|V| + |E|)$
Solution 【数组】 ( 10ms)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public int[] gardenNoAdj(int N, int[][] paths) {
int[][] topo = new int[N+1][3] ;
for( int[] cur : paths ){
int temp = 0 ;
while( topo[cur[0]][temp] != 0 ) temp++ ;
topo[cur[0]][temp] = cur[1] ;
temp = 0 ;
while( topo[cur[1]][temp] != 0 ) temp++ ;
topo[cur[1]][temp] = cur[0] ;
}
int[] res1 = new int[N+1] ;
int[] res = new int[N] ;
for( int i = 1 ; i <= N ; i++ ){
int temp = 1 ;
while( res1[topo[i][0]] == temp || res1[topo[i][1]] == temp || res1[topo[i][2]] == temp ) temp++ ;
res1[i] = temp ;
}
for( int i = 0 ; i < N ; i++ ) res[i] = res1[i+1] ;
return res ;
}
}
|
目前提交的结果中最快，【基本数据结构太强了