题目链接：89. 格雷编码
解法一
如果 $n-1$ 位的格雷码序列是 $G(n-1)$，将其反转，可以得到 $reversed(G(n-1))$，然后将 $G(n-1)$ 和 $reversed(G(n-1))$ 首尾相接，那么可以得到除相接处外，每处相邻元素都只差一位的序列。将 $reversed(G(n-1))$ 中的每个元素增加 $2^{n-1}$，得到 $reversed(G(n-1)) + 2^{n-1}$。将这两个序列首尾相接，那么可以得到 $n$ 位的格雷码序列：
\[G(n)=concat(G(n-1), reversed(G(n-1)) + 2^{n-1}).\]from typing import List
class Solution:
def grayCode(self, n: int) -> List[int]:
ret = [0]
for i in range(0, n):
tail = list(map(lambda it: it + (1 << i), ret[::-1]))
ret = ret + tail
return ret
解法二
这个公式不懂是咋推出来的，但是它的确有用。用这个公式计算出来的序列和解法一计算出来的序列是一样的。
from typing import List
class Solution:
def grayCode(self, n: int) -> List[int]:
return [(i >> 1) ^ i for i in range(1 << n)]