LintCodeグレイ符号化
1424 ワード
タイトル
グレイ符号化はバイナリデジタルシステムであり,このシステムでは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-1ビットグレイコード、さらに1<
コード#コード# public class Solution {
/**
* @param n a number
* @return Gray code
*/
public ArrayList grayCode(int n) {
ArrayList result = new ArrayList();
if (n <= 1) {
for (int i = 0; i <= n; i++){
result.add(i);
}
return result;
}
result = grayCode(n - 1);
ArrayList r1 = reverse(result);
int x = 1 << (n-1);
for (int i = 0; i < r1.size(); i++) {
r1.set(i, r1.get(i) + x);
}
result.addAll(r1);
return result;
}
public ArrayList reverse (ArrayList r) {
ArrayList rev = new ArrayList();
for (int i = r.size() - 1; i >= 0; i--) {
rev.add(r.get(i));
}
return rev;
}
}
再帰を使って作ることができます.法則は次のとおりです.
一部はn-1ビットグレイコード、さらに1<
コード#コード# public class Solution {
/**
* @param n a number
* @return Gray code
*/
public ArrayList grayCode(int n) {
ArrayList result = new ArrayList();
if (n <= 1) {
for (int i = 0; i <= n; i++){
result.add(i);
}
return result;
}
result = grayCode(n - 1);
ArrayList r1 = reverse(result);
int x = 1 << (n-1);
for (int i = 0; i < r1.size(); i++) {
r1.set(i, r1.get(i) + x);
}
result.addAll(r1);
return result;
}
public ArrayList reverse (ArrayList r) {
ArrayList rev = new ArrayList();
for (int i = r.size() - 1; i >= 0; i--) {
rev.add(r.get(i));
}
return rev;
}
}
public class Solution {
/**
* @param n a number
* @return Gray code
*/
public ArrayList grayCode(int n) {
ArrayList result = new ArrayList();
if (n <= 1) {
for (int i = 0; i <= n; i++){
result.add(i);
}
return result;
}
result = grayCode(n - 1);
ArrayList r1 = reverse(result);
int x = 1 << (n-1);
for (int i = 0; i < r1.size(); i++) {
r1.set(i, r1.get(i) + x);
}
result.addAll(r1);
return result;
}
public ArrayList reverse (ArrayList r) {
ArrayList rev = new ArrayList();
for (int i = r.size() - 1; i >= 0; i--) {
rev.add(r.get(i));
}
return rev;
}
}