LeetCode(一)GrayCodeの実現について


LeetCodeにはGray Codeの実現についての問題があります.
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;
	}

突然発見して、自分は本当にこの仕事に向いていないで、とても愚かです!