一、题目
Gray Code
二、解题
Gray Code：格雷码
题目的意思是在给出一个字节长度n，生成一个序列，这个序列的要求是格雷码（每连续的两个数的二进制只能有一位的不同，例如000 和 010只有第二位1不同）。
三、独立思考
1）判断前后两个二进制数是否满足格雷码条件？
首先想到的就是对两个数进行一次异或（^），然后把得到的值通过divmod 进行除2求余，如果余数值为1的个数只有1个，则满足条件，反之不满足。
2）怎么遍历字节长为n的所有数？
使用sourceCodeList列表初始化储存0～2^n的数字，从第一个0开始，每次遍历这个列表里面从小到大找下一个数字，满足则保存到resultCodeList里面，然后从sourceCodeList删除该数字。（这样考虑的是随着数字找出的越多，sourceCodeList越少，就越来越快）
3）怎么确定边界
存在两个边界：
- sourceCodeList为空，即遍历完了
- sourceCodeList不为空，找不到下一个了。
四、尝试与结果
#!/usr/bin/python
#coding:utf-8
class Solution(object):
def isGrayCode(self,x,y):
count = 0
tBin = x^y
while (tBin != 0):
tBin,mod = divmod(tBin,2)
if mod == 1:
count += 1
if (count ==1):
return True
else:
return False
def grayCode(self, numLen):
sourceCodeList = []
for i in range(0,2 ** numLen):
sourceCodeList.append(i)
resultCodeList = [0]
sourceCodeList.remove(0)
while True:
for i in sourceCodeList:
if i not in resultCodeList:
if (self.isGrayCode(resultCodeList[-1],i)):
resultCodeList.append(i)
sourceCodeList.remove(i)
break
if (len(sourceCodeList) <= 0):
break
if (i == sourceCodeList[-1]):
break
return resultCodeList
if __name__ == '__main__':
print Solution().grayCode(11)
结果n＝11到时候开始TL，自己尝试了一下，在5s左右
n=11
四、学习与记录
1）解决方法：按照格雷码的定义
从最右边一位起，依次将每一位与左边一位异或(XOR)，作为对应格雷码该位的值，最左边一位不变(相当于左边是0)。
格雷码的是特点是：
相邻两数的格雷码，仅仅有一位二进制发生变化。
而且在其范围内的最小值和最大值，也仅仅有一位二进制发生变化。
例如下面两数：
最小：二进制0000＝格雷码0000
最大：二进制1111＝格雷码1000
那基本上就是右移然后异或就可以了
def grayCode(self,numLen):
resultCodeList = []
for i in range(0,2 ** numLen):
grayCode = (i >> 1)^i
resultCodeList.append(grayCode)
return resultCodeList
