89. Gray Code 格雷码

题目

给定一个整数 n，返回 2 的 n 次幂的序列，使得这个序列满足格雷码。
格雷码的特点是，将这些数字分解为二进制整数，这些二进制数之间，两两仅有 1 位不同。
格雷码通常用于数电转换，因为在数电转换期间，不可能几位同时变化，就可能出现中间码，导致一些错误情况，使用格雷码能避免这种错误。
所以该题目就是要求给出一种 n 位格雷码生成算法。

解析

！根据格雷码的规律，提出按位反向格雷码。

1. 我们先生成 1 位格雷码
   [0]
   [1]
2. 因为一位格雷码是满足两两相差1位的，对于2位格雷码，我们只需要保证高位不变，然后顺序反向复制低位，即可保证新生成的码连接上前一个也是格雷码。
   即
   [00]
   [01]
   [11] -> 复制 [01]
   [10] -> 复制 [00]
3. 同理，推三位格雷码
   [110]
   [111]
   [101]
   [100]

将这个思路转换成代码，一代一代的生成，一共需要生成 n 代，每一代的个数是 2^(n-1) 个数

伪代码

gn = [2^n]int
gn[0] = 0
gn[1] = 1
for nb=2;i<n;nb++
  num =  1<< (nb-1)
  for i=0;i<num;i++
    gn[num+i] = num | gn[num-i-1]
return gn

代码

func grayCode(n int) []int {
    gn := make([]int, 1<<n)
    gn[0] = 0
    gn[1] = 1
    for g:=2;g<=n;g++ {
        num := 1<<(g-1)
        for i:=0;i<num;i++ {
            gn[num+i] = num | gn[num-i-1]
        }
    }
    return gn
}

image.png