0089. Gray Code

# 89. Gray Code#

## 题目 #

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

Example 1:

``````Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2

For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.

00 - 0
10 - 2
11 - 3
01 - 1
``````

Example 2:

``````Input: 0
Output: [0]
Explanation: We define the gray code sequence to begin with 0.
A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1.
Therefore, for n = 0 the gray code sequence is [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 {
for i := len(num) - 1; i >= 0; i-- {
}
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
}

``````

Apr 8, 2023