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

paths[i] = [x, y] 描述了花园 x 到花园 y 的双向路径。

另外，没有花园有 3 条以上的路径可以进入或者离开。

你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。

以数组形式返回选择的方案作为答案 answer，其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用  1, 2, 3, 4 表示。保证存在答案。

示例 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 条或者更多路径可以进入或离开。
保证存在答案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flower-planting-with-no-adjacent
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

注意是一个点不能与之相连的点相同颜色（图着色问题），而不是整条链路需要不同

func gardenNoAdj(N int, paths [][]int) []int {
    graph := make([][]int, N)
    for _, path := range paths {
        i, j := path[0] - 1, path[1] - 1
        if graph[i] == nil {
            graph[i] = make([]int, 0)
        }
        if graph[j] == nil {
            graph[j] = make([]int, 0)
        }
        graph[i] = append(graph[i], j)
        graph[j] = append(graph[j], i)
    }

    res := make([]int, N)
    for src, dsts := range graph {
        visits := make([]bool, 4)
        for _, dst := range dsts {
            if res[dst] != 0 {
                visits[res[dst] - 1] = true
            }
        }

        for i, visit := range visits {
            if visit {
                continue
            }
            res[src] = i + 1
            break
        }
    }

    return res
}

https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

就是每一项都是数组的总乘积处于自身，但是不能不用除法

常规做法 用两个数组分别来保存下标i的左乘积与右乘积

func constructArr(a []int) []int {
    if len(a) == 0 {
        return a
    } else if len(a) == 1 {
        return []int{0}
    }

    leftSum := make([]int, len(a))
    rightSum := make([]int, len(a))
    res := make([]int, len(a))
    leftSum[0] = a[0]
    rightSum[len(a)-1] = a[len(a)-1]
    for i := 1; i < len(a); i++ {
        leftSum[i] = leftSum[i-1] * a[i]
        rightSum[len(a) - 1 - i] = rightSum[len(a) - i] * a[len(a) - 1 - i]
    }
    res[0] = rightSum[1]
    res[len(a) - 1] = leftSum[len(a) - 2]


    for i := 0; i < len(a); i++ {
        res[i] = 1
        if i+1 < len(a) {
            res[i] *= rightSum[i+1] 
        }
        if i-1 >= 0 {
            res[i] *= leftSum[i-1]
        }
    }
    return res
}

巧妙做法： 可以用一个p保存上一次累乘的结果 那么只需要两次循环（一次左累积 一次右累积）即可。

func constructArr(a []int) []int {
    if len(a) == 0 {
        return a
    } else if len(a) == 1 {
        return []int{0}
    }
    res := make([]int, len(a))

    p := 1
    for i, v := range a {
        res[i] = p
        p *= v
    }

    p = 1
    for i := len(a) - 1; i >= 0; i-- {
        res[i] *= p
        p *= a[i]
    }
    return res
}