LC.P1042[不邻接植花]

方法一：建图+枚举

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) {
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int[] path : paths) {
            int x = path[0] - 1, y = path[1] - 1;
            g[x].add(y);
            g[y].add(x);
        }
        int[] ans = new int[n];
        for (int x = 0; x < n; ++x) {
            boolean[] used = new boolean[5];
            for (int y : g[x]) used[ans[y]] = true;
            for (int c = 1; c < 5; ++c) {
                if (!used[c]) {
                    ans[x] = c;
                    break;
                }
            }
        }
        return ans;
    }
}

方法二：建图(map)+枚举

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
class Solution {

    Map<Integer, List<Integer>> g = new HashMap<>();

    private void add(int a, int b) {
        g.computeIfAbsent(a, key -> new ArrayList<>()).add(b);
    }

    public int[] gardenNoAdj(int n, int[][] paths) {
        for (int[] path : paths) {
            int x = path[0] - 1, y = path[1] - 1;
            add(x, y);
            add(y, x);
        }
        int[] ans = new int[n];
        for (int x = 0; x < n; ++x) {
            boolean[] used = new boolean[5];
            List<Integer> list = g.getOrDefault(x, new ArrayList<>());
            for (int y : list) used[ans[y]] = true;
            for (int c = 1; c < 5; ++c) {
                if (!used[c]) {
                    ans[x] = c;
                    break;
                }
            }
        }
        return ans;
    }
}
  • 时间复杂度：$O(m + n)$
  • 空间复杂度：$O(m + n)$