0089. 格雷编码 #

• 标签：位运算、数学、回溯
• 难度：中等

题目大意 #

• 格雷编码：二进制数字系统，两个连续的数值仅有一个位数的差异。

现在给定一个代表格雷编码总位数的非负整数 n，打印对应的格雷编码序列。只需要返回其中一个答案即可。

解题思路 #

• 格雷编码生成规则：以二进制值为 0 的格雷编码作为第 0 项，第一次改变最右边的数位，第二次改变从右边数第一个为 1 的数位左边的数位，第三次跟第一次一样，改变最右边的数位，第四次跟第二次一样，改变从右边数第一个为 1 的数位左边的数位。此后，第五、六次，第七、八次 … 都跟第一二次一样反复进行，直到生成 $2^n$​ 个格雷编码。

• 也可以直接利用二进制转换为格雷编码公式：

  

代码 #

1
2
3
4
5
6
7
8

class Solution:
    def grayCode(self, n: int) -> List[int]:
        gray = []
        binary = 0
        while binary < (1 << n):
            gray.append(binary ^ binary >> 1)
            binary += 1
        return gray