這個(gè)題其實(shí)有個(gè)小技巧（個(gè)人一直覺(jué)得這種所謂的“技巧”其實(shí)并不能真正提高編程能力），就是編碼的規(guī)律踩娘。什么規(guī)律呢娘荡？通過(guò)觀察我們可以發(fā)現(xiàn)，格雷編碼是通過(guò)上一級(jí)的編碼得到的魁袜。也就是n個(gè)數(shù)的編碼可以通過(guò)n - 1個(gè)數(shù)的編碼得到桩撮。
如果n = 1敦第，那么編碼為[0, 1]；
n = 2店量，編碼為[00, 10, 11, 01]芜果；
n = 3，編碼為[000, 100, 110, 010, 011, 111, 101, 001]融师；
所以右钾，n級(jí)的編碼的生成，是從n - 1編碼的最后一個(gè)編碼開(kāi)始倒序遍歷旱爆，每遍歷一個(gè)編碼舀射，就將這個(gè)編碼+1后的碼字添加到結(jié)果列表的后面，然后再將這個(gè)編碼+0怀伦。
比如脆烟，n = 2，編碼為[00, 10, 11, 01]房待，倒序遍歷邢羔，得到：
01，+1后生成新的碼字添加到后面桑孩，再對(duì)01+0拜鹤，結(jié)果列表變成[00, 10, 11, 010, 011]；
接著向前遍歷洼怔，對(duì)11做與上一步相同的處理署惯，結(jié)果列表變成[00, 10, 110, 010, 011, 111]；
最后镣隶，結(jié)果列表變?yōu)閇000, 100, 110, 010, 011, 111, 101, 001]极谊。這樣生成的編碼就是符合格雷編碼條件的。也就是說(shuō)安岂，n級(jí)格雷編碼是由n - 1級(jí)格雷編碼生成的轻猖，這是很典型的遞歸思想。
最后域那，把二進(jìn)制的字符轉(zhuǎn)換成十進(jìn)制整數(shù)就行咙边。代碼如下：
class Solution:
def grayCode(self, n: int) -> List[int]:
result = []
if n == 0:
return [0]
for i in self.helper(n):
result.append(int(i, 2))
return result
def helper(self, n):
result = []
if n == 1:
return ["0", "1"]
elif n > 1:
result = self.helper(n - 1)
index = len(result) - 1
while index >= 0:
temp = result[index]
temp += "1"
result.append(temp)
result[index] += "0"
index -= 1
return result
