1. 不邻接植花 - Flower Planting With No Adjacent

【图】【Map】【数组】

Problem Link

N 个花园,按从 1N 标记。在每个花园中,你打算种下四种花之一。

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 <= 10000
  • 0 <= 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
34
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
23
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 ;
    }
}

目前提交的结果中最快,【基本数据结构太强了