题目中介绍的格雷码序列可能不太好理解,我这里画了一张1~3位格雷编码的图来更直观的看下它的生成过程。首先格雷编码的第一位是0,从一位开始是0和1;然后到两位时,先在一位的基础上补0,在最高位产生进位时在前面加个1;到三位时在两位的基础上补0,产生进位时在最高位补1。
另外,我们看箭头连起来的数据块是和上一次的数据除了最高位,其余部分是对称的关系,即可以将原序列反转后拼到最高位的后面。由此,本题可以转换为推导n-1位和n位数集合数字之间的关系:
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