1.题目基本信息

1.1.题目描述

n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：

• 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）

• 第一个整数是 0

• 一个整数在序列中出现 不超过一次

• 每对 相邻 整数的二进制表示 恰好一位不同 ，且

• 第一个 和 最后一个 整数的二进制表示 恰好一位不同

给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

1.2.题目地址

https://leetcode.cn/problems/gray-code/description/

2.解题方法

2.1.解题思路

假设n-1位格雷码序列为G(n-1)，复制G(n-1)为G(n-1)_2，将G(n-1)_2翻转，然后对于每一项，在其二进制的首位添加1，得到G(n-1)_3。最终G(n)=G(n-1)+G(n-1)_3

3.解题代码

python代码

class Solution:
    def grayCode(self, n: int) -> List[int]:
        # 思路：假设n-1位格雷码序列为G(n-1)，复制G(n-1)为G(n-1)2，将G(n-1)2翻转，然后对于每一项，在其二进制的首位添加1，得到G(n-1)3。最终G(n)=G(n-1)+G(n-1)3
        g = [0]
        for i in range(n):
            temp = []
            for num in g[::-1]:
                temp.append(num | (1 << i))
            g = g + temp
        return g

4.执行结果