LeetCode(一)GrayCodeの実現について
LeetCodeにはGray Codeの実現についての問題があります.
GrayCodeは、次のようなコードです.
1位Gray Code:
次のようにミラーを追加します.
問題の要件は次のとおりです.
Q:nを与える
A:グレイコードシーケンスの10進数を出力します.上の2桁のグレイコードは、00、01、11、10があります.では、0、1、3、2を出力します.
まず、Gray Codeの定義に従って書いて、それを十進法にすればいいのではないかと考えて、書きましょう.
簡単に考えてみましょう.
1)0の場合は、「0」を含むリストを直接返します.
2)0より大きい場合は、まず配列の最初の2つの要素を0,1に設定します.これは最も基本的な2つの要素です.
3)次に、GrayCodeの定義に従って、この2つの要素にミラーコードを追加します.
4)グレイコードが実装され,それを10進数の数値にしてlistに戻した.
提出は、通過できます.しかし、よく考えてみると、自分はやはり馬鹿なのか、問題の要求は10進数の数値を出力するだけで、なぜ文字列を使うのか、考えてみると、次のような方法が思いつきました.
この方法では,文字列を用いずに直接整数で処理する.
1)最初のステップは,まず0を追加し,nの値を判断し,n>0であれば計算を続ける.
2)n>1の場合,2番目のGray Codeの値は必ず1であるため,直接1を追加する.
3)n>=2の場合は、ミラーコードを追加するたびにミラーコードの前に「1」を追加し、元のGray Codeの前に「0」を追加する2つのケースに分けることができ、前半のグレイコードの値は実際には変わらないことがわかります!実はそれを処理する必要はありません!私はどんなに愚かでやっとこれを考えたのだろう.
一方、後半では、前に1を追加すると、3(n)ビットGray Codeの2(k)ビット(低から高へ)が2^(k-1)=2を追加するなど、対応するビット数の値が加算され、その別の実現形態は
1<<(k-1)ですが、この値は、ちょうど上に出ているのでそのまま使えばいいので、そのままGrayCodeの10進数を求めます.
テスト、合格!
しかし、その後、ネット上で他の人の実現を見て、以下のようにしました.
突然発見して、自分は本当にこの仕事に向いていないで、とても愚かです!
GrayCodeは、次のようなコードです.
1位Gray Code:
0
1
ビットGray Code:次のようにミラーを追加します.
0
1
1
0
その後、元の符号化の前に「0」を追加し、ミラー符号の前に「1」を追加し、以下のようにする.00
01
11
10
で2ビットから3ビットに変更されたGray Codeの実装は、1ビットから2ビットに変更されたプロセスと同様であり、ミラーコードを先に追加し、「0」と「1」をそれぞれ追加した後、.問題の要件は次のとおりです.
Q:nを与える
A:グレイコードシーケンスの10進数を出力します.上の2桁のグレイコードは、00、01、11、10があります.では、0、1、3、2を出力します.
まず、Gray Codeの定義に従って書いて、それを十進法にすればいいのではないかと考えて、書きましょう.
private ArrayList<Integer> grayCode(int n) {
if (n == 0) {
ArrayList<Integer> templist = new ArrayList<>(1);
templist.add(0);
return templist;
}
int length = 1 << n;
ArrayList<Integer> list = new ArrayList<>(length);
String[] numbers = new String[length];
int k = 2;
numbers[0] = "0";
numbers[1] = "1";
while (k <= n) {
int mid = 1 << (k - 1);
for (int i = 0; i < mid; i++) {
numbers[mid + i] = "1" + numbers[mid - i - 1];
numbers[mid - i - 1] = "0" + numbers[mid - i - 1];
}
k++;
}
for (CharSequence number : numbers) {
int value = 0;
int len = number.length();
for (int i = 0; i < len; i++) {
int val = (int) (number.charAt(i) - '0');
value += val * (1 << (len - i - 1));
}
list.add(value);
}
return list;
}
簡単に考えてみましょう.
1)0の場合は、「0」を含むリストを直接返します.
2)0より大きい場合は、まず配列の最初の2つの要素を0,1に設定します.これは最も基本的な2つの要素です.
3)次に、GrayCodeの定義に従って、この2つの要素にミラーコードを追加します.
numbers[mid + i] = numbers[mid - i - 1];
ただし、ミラーコードの前に「1」が追加されることを考慮すると、そのままこのステップで実現すればよいので、上のコードです.4)グレイコードが実装され,それを10進数の数値にしてlistに戻した.
提出は、通過できます.しかし、よく考えてみると、自分はやはり馬鹿なのか、問題の要求は10進数の数値を出力するだけで、なぜ文字列を使うのか、考えてみると、次のような方法が思いつきました.
private ArrayList<Integer> grayCode2(int n) {
int length = 1 << n;
ArrayList<Integer> list = new ArrayList<>(length);
list.add(0);
if (n > 0) {
list.add(1);
int k = 2;
while (k <= n) {
int mid = 1 << (k - 1);
for (int i = 0; i < mid; i++) {
list.add(mid + i, mid + list.get(mid - i - 1));
}
k++;
}
}
return list;
}
この方法では,文字列を用いずに直接整数で処理する.
1)最初のステップは,まず0を追加し,nの値を判断し,n>0であれば計算を続ける.
2)n>1の場合,2番目のGray Codeの値は必ず1であるため,直接1を追加する.
3)n>=2の場合は、ミラーコードを追加するたびにミラーコードの前に「1」を追加し、元のGray Codeの前に「0」を追加する2つのケースに分けることができ、前半のグレイコードの値は実際には変わらないことがわかります!実はそれを処理する必要はありません!私はどんなに愚かでやっとこれを考えたのだろう.
一方、後半では、前に1を追加すると、3(n)ビットGray Codeの2(k)ビット(低から高へ)が2^(k-1)=2を追加するなど、対応するビット数の値が加算され、その別の実現形態は
1<<(k-1)ですが、この値は、ちょうど上に出ているのでそのまま使えばいいので、そのままGrayCodeの10進数を求めます.
テスト、合格!
しかし、その後、ネット上で他の人の実現を見て、以下のようにしました.
private ArrayList<Integer> grayCode3(int n) {
int length = 1 << n;
ArrayList<Integer> list = new ArrayList<>(length);
for (int i = 0; i < length; i++) {
list.add((i >> 1) ^ i);
}
return list;
}
突然発見して、自分は本当にこの仕事に向いていないで、とても愚かです!