LeetCode --- 89. Gray Code
タイトルリンク:Gray Code
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
この問題の要求は,すべてのnビットグレイコードを順番に生成することである.
一組の数の符号化において、任意の2つの隣接するコードが1ビットのバイナリ数だけ異なる場合、この符号化はグレイコード(Gray Code)と呼ばれ、また最大数と最小数の間にも1桁の数しかないため、すなわち「首尾がつながっている」したがって、サイクルコードまたは反射コードとも呼ばれる.デジタルシステムでは、コードが一定の順序で変化することが要求されることが多い.例えば、自然数でカウントをインクリメントし、8421符号を採用すると、数0111が1000になると4ビットが変化するが、実際の回路では4ビットの変化が絶対的に同時に発生することはない、カウント中に短い他のコード(1100、1111など)が発生する可能性があります.特定の場合、回路状態エラーや入力エラーを引き起こす可能性があります.グレイコードを使用すると、このようなエラーを回避できます.グレイコードにはいくつかの符号化形式があります.
グレイコード(Gray Code)はGrey Code、グレイコード、グレイコード、ゴレコード、サイクルコード、反射バイナリコード、最小エラーコードなどの名前を使ったことがありますが、間違っているものもあれば、他の名前と混同されやすいものもあります.これらの名前を使わないことをお勧めします.
ちょくせつはいち
2進数0の値を持つグレイ符号は0項目、1項目は右端のビットを変更し、2項目は右端から1番目のビットの左端のビットを変更し、3、4項目は1、2項目と同じ方法で繰り返し、n個のビットのグレイ符号を並べることができる.
ミラー配列
nビットのグレイ符号は、n−1ビットのグレイ符号以上の下鏡射後に新しいビットを加える方式から迅速に得ることができる.この方法はグレイ符号が反射符号であるという事実に基づいて,再帰的な次の規則を用いて構築される.
1ビットグレイ符号には2つの符号語がある
(n+1)ビットグレイ符号の最初の2^n個の符号語はnビットグレイ符号の符号語に等しく、順番に書き、プレフィックス0 を付ける.
(n+1)ビットグレイ符号の後2^n個の符号語はnビットグレイ符号の符号語に等しく、逆順序で書き、接頭辞1 を付ける.
バイナリトランスグレイコード
(2進数0の値をグレイコードの0とすると仮定)
G:グレイコードB:バイナリコード
G(N) = (B(n)/2) XOR B(n)
グレイコードへんかんにしんすう
バイナリ・コードnビット目=バイナリ・コードn+1ビット目+グレイ・コードnビット.バイナリ・コードとグレイ・コードは同じビット数であるため、バイナリ・コードは最上位の左ビットから0を取って計算することができる.(注:1+1に遭遇した場合、結果は0とみなす)
例えば、グレイ符号0111は、4ビット数であるため、その変換されたバイナリ符号も必ず4ビット数であるため、変換されたバイナリ符号の5ビット目は0、すなわち0 b 3 b 2 b 1 b 0とすることができる.
従って、変換されたバイナリコードは0101である.
参考はウィキペディア.
最後に
この問題はnビットグレイコードの生成を要求し,合計2^n個である.上記の式G(N)=B(n)XOR(B(n)/2)によれば、すべてのグレイ符号を逐次生成することができる.
時間複雑度:O(2^n)
空間複雑度:O(2^n)
転載は出典を説明してください:LeetCode---89.Gray Code
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0
01 - 1
11 - 3
10 - 2
Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
この問題の要求は,すべてのnビットグレイコードを順番に生成することである.
一組の数の符号化において、任意の2つの隣接するコードが1ビットのバイナリ数だけ異なる場合、この符号化はグレイコード(Gray Code)と呼ばれ、また最大数と最小数の間にも1桁の数しかないため、すなわち「首尾がつながっている」したがって、サイクルコードまたは反射コードとも呼ばれる.デジタルシステムでは、コードが一定の順序で変化することが要求されることが多い.例えば、自然数でカウントをインクリメントし、8421符号を採用すると、数0111が1000になると4ビットが変化するが、実際の回路では4ビットの変化が絶対的に同時に発生することはない、カウント中に短い他のコード(1100、1111など)が発生する可能性があります.特定の場合、回路状態エラーや入力エラーを引き起こす可能性があります.グレイコードを使用すると、このようなエラーを回避できます.グレイコードにはいくつかの符号化形式があります.
グレイコード(Gray Code)はGrey Code、グレイコード、グレイコード、ゴレコード、サイクルコード、反射バイナリコード、最小エラーコードなどの名前を使ったことがありますが、間違っているものもあれば、他の名前と混同されやすいものもあります.これらの名前を使わないことをお勧めします.
ちょくせつはいち
2進数0の値を持つグレイ符号は0項目、1項目は右端のビットを変更し、2項目は右端から1番目のビットの左端のビットを変更し、3、4項目は1、2項目と同じ方法で繰り返し、n個のビットのグレイ符号を並べることができる.
ミラー配列
nビットのグレイ符号は、n−1ビットのグレイ符号以上の下鏡射後に新しいビットを加える方式から迅速に得ることができる.この方法はグレイ符号が反射符号であるという事実に基づいて,再帰的な次の規則を用いて構築される.
1ビットグレイ符号には2つの符号語がある
(n+1)ビットグレイ符号の最初の2^n個の符号語はnビットグレイ符号の符号語に等しく、順番に書き、プレフィックス0 を付ける.
(n+1)ビットグレイ符号の後2^n個の符号語はnビットグレイ符号の符号語に等しく、逆順序で書き、接頭辞1 を付ける.
バイナリトランスグレイコード
(2進数0の値をグレイコードの0とすると仮定)
G:グレイコードB:バイナリコード
G(N) = (B(n)/2) XOR B(n)
グレイコードへんかんにしんすう
バイナリ・コードnビット目=バイナリ・コードn+1ビット目+グレイ・コードnビット.バイナリ・コードとグレイ・コードは同じビット数であるため、バイナリ・コードは最上位の左ビットから0を取って計算することができる.(注:1+1に遭遇した場合、結果は0とみなす)
例えば、グレイ符号0111は、4ビット数であるため、その変換されたバイナリ符号も必ず4ビット数であるため、変換されたバイナリ符号の5ビット目は0、すなわち0 b 3 b 2 b 1 b 0とすることができる.
0+0=0， b3=0
0+1=1， b2=1
1+1 0， b1=0
0+1 1， b0=1
従って、変換されたバイナリコードは0101である.
参考はウィキペディア.
最後に
この問題はnビットグレイコードの生成を要求し,合計2^n個である.上記の式G(N)=B(n)XOR(B(n)/2)によれば、すべてのグレイ符号を逐次生成することができる.
時間複雑度:O(2^n)
空間複雑度:O(2^n)
1 class Solution
2 {
3 public:
4 vector<int> grayCode(int n)
5 {
6 vector<int> v;
7 for(int i = 0; i < 1 << n; ++ i)
8 v.push_back(i ^ i >> 1);
9 return v;
10 }
11 };転載は出典を説明してください:LeetCode---89.Gray Code