Gray码问题

算法课碰到的问题，尝试用一次Python写写看了，不过时间复杂度还是挺高的O(n*2^n)。

Gray码是一个长度为2^n的序列。序列中无相同元素，每个元素都是长度为n位的(0,1)串，相邻元素恰好只有一位不同，用分治策略设计一个算法对任意的n位构造相应的Gray码。

class GrayCode:
    def getGray(self, n):
        return [bin((i>>1)^i).replace("0b","").rjust(n,"0") for i in range(2**n)]

# bin() 返回一个整数 int 或者长整数 long int 的二进制表示。
# replace() 方法把字符串中的 old(旧字符串) 替换成 new(新字符串)
# rjust() 返回一个原字符串右对齐

t = GrayCode()
i = input()
print (t.getGray(int(i)))

主要核心就一行return那里，利用了二进制两两xor得出格雷码的特性。