You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

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

. 3 min read

【图】【Map】【数组】

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% 的用户

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)

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 ;
    }
}

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