89. 格雷编码

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

1. 每个整数都在范围 [0, 2n – 1] 内（含 0 和 2n – 1）
2. 第一个整数是 0
3. 一个整数在序列中出现 不超过一次
4. 每对 相邻 整数的二进制表示 恰好一位不同 ，且
5. 第一个 和 最后一个 整数的二进制表示 恰好一位不同

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

解法：对称生成。找到规律后生成。

class Solution:
    def grayCode(self, n: int) -> List[int]:
        if n == 1:
            return [0,1]
        temp_ans = ["0","1"]
        for i in range(n-1):
            new_temp_ans = []
            # 添加0在首位
            for temp in temp_ans:
                temp = "0" + temp
                new_temp_ans.append(temp)
            # 添加1在首位
            for temp in temp_ans[::-1]:
                temp = "1" + temp
                new_temp_ans.append(temp)
            temp_ans = new_temp_ans
        # print(temp_ans)
        ans = []
        for temp in temp_ans:
            ans.append(int(temp,2))
        return ans

官方标答：对称生成

知道n-1的情况，生成n的情况

class Solution:
    def grayCode(self, n: int) -> List[int]:
        ans = [0]
        for i in range(1, n + 1):
            for j in range(len(ans) - 1, -1, -1):
                ans.append(ans[j] | (1 << (i - 1)))
        return ans

二进制数转格雷码

class Solution:
    def grayCode(self, n: int) -> List[int]:
        ans = [0] * (1 << n)
        for i in range(1 << n):
            ans[i] = (i >> 1) ^ i
        return ans

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/gray-code
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识补充

• 关于Python位操作规则，例如”|”、”<<“等，见链接https://blog.csdn.net/qq_32591415/article/details/111828121
• Python 逆序排列切片[::-1].