0089. 格雷编码
大约 1 分钟
0089. 格雷编码
- 标签:位运算、数学、回溯
- 难度:中等
题目大意
- 格雷编码:二进制数字系统,两个连续的数值仅有一个位数的差异。
现在给定一个代表格雷编码总位数的非负整数 n
,打印对应的格雷编码序列。只需要返回其中一个答案即可。
解题思路
格雷编码生成规则:以二进制值为
0
的格雷编码作为第0
项,第一次改变最右边的数位,第二次改变从右边数第一个为1
的数位左边的数位,第三次跟第一次一样,改变最右边的数位,第四次跟第二次一样,改变从右边数第一个为1
的数位左边的数位。此后,第五、六次,第七、八次 ... 都跟第一二次一样反复进行,直到生成 个格雷编码。也可以直接利用二进制转换为格雷编码公式:
image.png
代码
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