0089. Gray Code | LeetCode Cookbook

[halfrost]

https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0089.Gray-Code/

[hanlins]

这题也可以用递推，能用归纳法证明。当n = 1 时结果为 [0, 1]。对于 n+1 的情况，新加入的节点就是把第 n 位设成 1，然后在把之前的解反着复制一遍。举例，由于 n = 1 时结论位 [0, 1]，最高位为第0位为1，在 n = 2 时我们把 n = 1 的结论倒序复制一遍加入队尾，那么新加入的数就是 [1, 0]。然后我们再把这些新加入的数第1位都设成1，也就变成了 [0b11, 0b10]，最终结果就是 [0, 1, 3, 2]。这个用数学归纳法很容易证明正确性。代码如下:

func grayCode(n int) (res []int) {
    res = make([]int, 0, 1 << n)

    res = append(res, 0, 1)
    for i := 1; i < n; i++ {
        for j := (1 << i) - 1; j >= 0; j-- {
            res = append(res, res[j] + (1 << i))
        } 
    }

    return
}