菜鸟的每日力扣系列——89. 格雷编码

题目中介绍的格雷码序列可能不太好理解，我这里画了一张1～3位格雷编码的图来更直观的看下它的生成过程。首先格雷编码的第一位是0，从一位开始是0和1；然后到两位时，先在一位的基础上补0，在最高位产生进位时在前面加个1；到三位时在两位的基础上补0，产生进位时在最高位补1。

另外，我们看箭头连起来的数据块是和上一次的数据除了最高位，其余部分是对称的关系，即可以将原序列反转后拼到最高位的后面。由此，本题可以转换为推导n-1位和n位数集合数字之间的关系：

• n-1位构造本身不论正序还是倒序，相邻之间都是差1，在反转后最高位补1；
• 反转后，原先的最后一位会和自己相邻，在最高位补1后，差异恰好是1位；
• 反转后，原先的第一位成为最后一位，在最高位补1后，最后一位和第一位恰好有1位不同。

from typing import List

def grayCode(n: int) -> List[int]:
    if n == 1:
        return [0, 1]
    pre_res = grayCode(n-1)
    res: list = []
    res = [(1<<(n-1)) + i for i in pre_res[::-1]]
    return pre_res + res


print(grayCode(2))  # [0, 1, 3, 2]

END