LeetCode 1042. Flower Planting With No Adjacent
2020-05-28 20:11:09 # leetcode # greedy # graph

Problem

LeetCode 1042. Flower Planting With No Adjacent

1. 题目简述

给出N个花园(1…N)，给出花园中的路径paths，每个花园最多有三条连通路径。一共可以种四种花(1, 2, 3, 4)，每条路径两段的花的种类不能一致，给出一种符合条件的解。

Input: N = 3, paths = [[1,2],[2,3],[3,1]]
Output: [1,2,3]

条件限制：

1 <= N <= 10000
0 <= paths.size <= 20000
No garden has 4 or more paths coming into or leaving it.
It is guaranteed an answer exists.

2. 算法思路

这道题很多人点了不喜欢，一开始我也没做出来，看了解析之后才发现是自己想复杂了。

和二分图不同，这里像是四分图，且保证一定有解，这里不是非黑即白的选择，例如和1连通的有2，3，和4，我们假设四种颜色为红黄蓝白，1为红色，2、3、4可选的颜色种类太多了，如果都为黄色，那么遍历到[2, 3]这条路径的时候，我们又发现不行，不能都为黄色，又需要调整，容易陷入怪圈。

我们细心点可以发现这里有一个条件是每个花园最多有三条路径相连，也就是说每个花园一定能够被赋予某种颜色，而不会有冲突，一定存在解，所以现在的问题就在于如何找这种解法。

贪心法

稍微再想一想，我们完全没必要关心邻居究竟是怎么样的颜色分布，只要当前节点的颜色符合规定不就Ok了嘛，题中都保证一定有解了。

对于此题，我们需要先将整个图给遍历出来，然后，对于每个顶点，我们遍历其neighbors，找到其邻居的所有染色，然后随便选一种尚未出现的颜色对当前节点上色即可。

因此这是一种保证当前节点和之前节点最优解的方法，可以认为是贪心法。

注意

这里同样要注意ArrayList数组的初始化方法，不能使用List[]作为数组，因为List是抽象接口，不能这么做，需要用ArrayList。

3. 解法

Greedy：

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) {
        int[] res = new int[N];
        Arrays.fill(res, 0);
        ArrayList<Integer>[] graph = new ArrayList[N];

        for (int i = 0; i < N; i++) {
            graph[i] = new ArrayList();
        }

        for (int[] path : paths) {
            graph[path[0] - 1].add(path[1] - 1);
            graph[path[1] - 1].add(path[0] - 1);
        }

        for (int i = 0; i < N; i++) {
            int[] color = new int[5];

            for (int neighbor : graph[i]) {
                color[res[neighbor]] = 1;
            }

            for (int j = 1; j < 5; j++) {
                if (color[j] != 1) {
                    res[i] = j;
                    break;
                }
            }
        }

        return res;
    }
}
Prev
2020-05-28 20:11:09 # leetcode # greedy # graph
Next