一、題目

Gray Code

二、解題

Gray Code：格雷碼

題目的意思是在給出一個(gè)字節(jié)長度n，生成一個(gè)序列，這個(gè)序列的要求是格雷碼（每連續(xù)的兩個(gè)數(shù)的二進(jìn)制只能有一位的不同，例如000 和 010只有第二位1不同）。

三、獨(dú)立思考

1）判斷前后兩個(gè)二進(jìn)制數(shù)是否滿足格雷碼條件？
首先想到的就是對(duì)兩個(gè)數(shù)進(jìn)行一次異或（^），然后把得到的值通過divmod 進(jìn)行除2求余，如果余數(shù)值為1的個(gè)數(shù)只有1個(gè)，則滿足條件，反之不滿足。
2）怎么遍歷字節(jié)長為n的所有數(shù)？
使用sourceCodeList列表初始化儲(chǔ)存0～2^n的數(shù)字，從第一個(gè)0開始，每次遍歷這個(gè)列表里面從小到大找下一個(gè)數(shù)字，滿足則保存到resultCodeList里面，然后從sourceCodeList刪除該數(shù)字。（這樣考慮的是隨著數(shù)字找出的越多，sourceCodeList越少，就越來越快）
3）怎么確定邊界
存在兩個(gè)邊界：

• sourceCodeList為空，即遍歷完了
• sourceCodeList不為空，找不到下一個(gè)了。

四、嘗試與結(jié)果

#!/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)

結(jié)果n＝11到時(shí)候開始TL，自己嘗試了一下，在5s左右

n=11

四、學(xué)習(xí)與記錄

1）解決方法：按照格雷碼的定義
從最右邊一位起，依次將每一位與左邊一位異或(XOR)，作為對(duì)應(yīng)格雷碼該位的值，最左邊一位不變(相當(dāng)于左邊是0)。

格雷碼的是特點(diǎn)是：
相鄰兩數(shù)的格雷碼，僅僅有一位二進(jìn)制發(fā)生變化。
而且在其范圍內(nèi)的最小值和最大值，也僅僅有一位二進(jìn)制發(fā)生變化。
例如下面兩數(shù)：
最?。憾M(jìn)制0000＝格雷碼0000
最大：二進(jìn)制1111＝格雷碼1000

那基本上就是右移然后異或就可以了

    def grayCode(self,numLen):
        resultCodeList = []
        for i in range(0,2 ** numLen):
            grayCode = (i >> 1)^i
            resultCodeList.append(grayCode)
        return resultCodeList