グレイ符号化


タイトル説明:グレイ符号化はバイナリデジタルシステムであり、このシステムでは、2つの連続した数値は1つのバイナリの違いしかない.非負の整数nが与えられ、コード内のすべてのバイナリの総数を表し、そのグレイ符号化順序を見つけてください.1つのグレイ符号化順序は0で開始され、すべての2 n個の整数を上書きしなければならない.
注意:所与のnに対して、そのグレイ符号化順序は一意ではない.以上の定義によれば、[0,2,3,1]も有効なグレイ符号化順序である.
例:n=2を指定し、[0,1,3,2]を返します.そのグレイ符号化順序は以下の通りである.
00 - 0 01 - 1 11 - 3 10 - 2
この問題には実は小さなテクニックがあります(個人的にはこのようないわゆる「テクニック」は実際にプログラミング能力を高めることができないと思っています)、コードの法則です.どんな法則ですか.観察により,グレイ符号化は上位レベルの符号化によって得られることが分かった.すなわち、n個数の符号化は、n−1個数の符号化により得ることができる.
n=1の場合、符号化は[0,1]である.
n=2であり、符号化は[00,10,11,01]である.
n=3,符号化は[00000,100,110,010,011,111,101,001]であった.
したがって、n段の符号化の生成は、n−1符号化の最後の符号化から逆ループを開始し、1つの符号化をループするたびに、この符号化+1後の符号語を結果リストの後に追加し、その後、この符号化+0を行う.
例えば、n=2であり、[00,10,11,01]と符号化され、逆順に遍歴し、得られる:
01,+1後に新しいコードワードを生成して後に追加し、01+0に対して結果リストは[00,10,11,010,011]となる.
次に、前へ遍歴し、11に対して前のステップと同じ処理を行い、結果リストは[00,10,110,010,011,111]となる.
最後に、結果リストは[00000,100,110,010,011,111,101,001]となる.このように生成された符号化は、グレイ符号化条件に合致する.すなわち、n級グレイ符号化は、n−1級グレイ符号化によって生成され、これは典型的な再帰思想である.
最後に、バイナリの文字を10進数整数に変換すればいいです.コードは次のとおりです.
class Solution:
    # @param {int} n a number
    # @return {int[]} Gray code
    def grayCode(self, n):
        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
        # Write your code here

pythonではint(a,2)はバイナリ文字列を対応する整数に変換することを意味する.