📑 题目：89. 格雷编码

🚀 本题 LeetCode 传送门

题目大意

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。

解题思路

• 输出 n 位格雷码
• 格雷码生成规则：以二进制为0值的格雷码为第零项，第一次改变最右边的位元，第二次改变右起第一个为1的位元的左边位元，第三、四次方法同第一、二次，如此反复，即可排列出 n 个位元的格雷码。
• 可以直接模拟，也可以用递归求解。

代码

package leetcode
// 解法一 递归方法，时间复杂度和空间复杂度都较优
func grayCode(n int) []int {
 if n == 0 {
  return []int{0}
 }
 res := []int{}
 num := make([]int, n)
 generateGrayCode(int(1<<uint(n)), 0, &num, &res)
 return res
}
func generateGrayCode(n, step int, num *[]int, res *[]int) {
 if n == 0 {
  return
 }
 *res = append(*res, convertBinary(*num))
 if step%2 == 0 {
  (*num)[len(*num)-1] = flipGrayCode((*num)[len(*num)-1])
 } else {
  index := len(*num) - 1
  for ; index >= 0; index-- {
   if (*num)[index] == 1 {
    break
   }
  }
  if index == 0 {
   (*num)[len(*num)-1] = flipGrayCode((*num)[len(*num)-1])
  } else {
   (*num)[index-1] = flipGrayCode((*num)[index-1])
  }
 }
 generateGrayCode(n-1, step+1, num, res)
 return
}
func convertBinary(num []int) int {
 res, rad := 0, 1
 for i := len(num) - 1; i >= 0; i-- {
  res += num[i] * rad
  rad *= 2
 }
 return res
}
func flipGrayCode(num int) int {
 if num == 0 {
  return 1
 }
 return 0
}
// 解法二 直译
func grayCode1(n int) []int {
 var l uint = 1 << uint(n)
 out := make([]int, l)
 for i := uint(0); i < l; i++ {
  out[i] = int((i >> 1) ^ i)
 }
 return out
}