Flower Planting With No Adjacent
这题好tricky啊, 上眼立刻觉得是颜色问题, 难道是dfs+剪枝?, 试了好久感觉不应该那么难, 打开答案才看到, 原来3度4个颜色, 不就是正好能满配的么. 下面是抄leetcode的一个答案写的.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution { public int[] gardenNoAdj(int n, int[][] E) { int[] R = new int[n]; Arrays.fill(R, 1); boolean f; do { f = false; for (int[] e : E) { int u = Math.min(e[0], e[1]) - 1; int v = Math.max(e[0], e[1]) - 1; if (R[u] == R[v]) { f = true; R[v] = R[u] == 4 ? 1 : R[u] + 1; } } } while (f); return R; } } |