89. Gray Code

Loading...LeetCode

原来是需要借助 gray code 的一些性质，参考维基百科：n位元的格雷码可以从n-1位元的格雷码以上下镜射后加上新位元的方式快速的得到，如下图所示一般。

其实就是把 (n-1) 位的gray code逆序，前面加个1（换成十进制来看就是加了2^(n-1)）。

class Solution:
    def grayCode(self, n):
        if n == 0: return [0]
        else:
            res = self.grayCode(n - 1)
            for i in range(len(res) - 1, -1, -1):
                res.append((2 ** (n - 1)) + res[i])
            return res