LeetCode（一）關於GrayCode的實現

在LeetCode上面有一道題，是關於Gray Code的實現的。

GrayCode是這樣一種編碼：

1 位Gray Code ：

0
1

2 位Gray Code：

先添加一個鏡像，如下：

0
1
1
0

然後，在原來的編碼前面添加“0”，在鏡像碼前面添加“1”，如下：

00
01
11
10

而從2位變化到3位的Gray Code的實現方式跟從1位變化到2位的過程是一樣的， 都是先添加鏡像碼，再分別添加 “0” 和 “1”，然後，。。。

題目的要求是：

Q：給出一個n

A：輸出格雷碼序列的十進制，上面2位的格雷碼，有00，01，11，10，那麼就要輸出0，1，3，2。

第一想法就是，先照著Gray Code的定義寫出來，再將其變成十進制不就好了嗎，於是寫吧。

	private ArrayList grayCode(int n) {
		if (n == 0) {
			ArrayList templist = new ArrayList<>(1);
			templist.add(0);
			return templist;
		}
		int length = 1 << n;
		ArrayList 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”的list。

2）如果大於0，那麼先將數組的前兩個元素先置成0，1，這是最基本的兩個元素。

3）接下來，按照GrayCode的定義，為這兩個元素添加鏡像碼，本來應該是下面這樣的變成鏡像碼：

numbers[mid + i] = numbers[mid - i - 1];

不過考慮到鏡像碼前面會添加“1”，那麼就直接在這一步實現就好了，所以就是上面的代碼了。

4）格雷碼實現好了，將它變成十進制的數值，然後放到list，返回。

提交，是可以通過的。不過接著仔細一想，自己果然是傻的呀，題目的要求只是要輸出十進制的數值，干嘛要用字符串呢，於是琢磨著琢磨著，就想出了下面的方法：

	private ArrayList grayCode2(int n) {
		int length = 1 << n;
		ArrayList 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，那麼第二個Gray Code的值一定是1，所以就直接添加1。

3）對於n >=2 的情況，則可以分成兩種情況，每次添加鏡像碼的時候，在鏡像碼前面添加“1”，而在原來的Gray Code前面添加"0"，那麼可以發現，前半部分的格雷碼，它們的值其實是不變的！其實根本沒有必要處理它！我這是多麼笨才想到這的啊！

而對於後半部分，前面添加1，其實就是加上一個相對應位數的值，比如3（n）位Gray Code的第 2（k）位（從低往高數），就是添加2 ^ (k-1) = 2，它的另外的實現方式則是

1 <<（k - 1），而這個值，剛好在上面其實就算出來了，所以就直接用就好了，這樣一來，就直接將GrayCode的十進制數值給求出來了。

一測試，通過！

但是，後來在網上看到別人的實現，如下：

	private ArrayList grayCode3(int n) {
		int length = 1 << n;
		ArrayList list = new ArrayList<>(length);
		for (int i = 0; i < length; i++) {
			list.add((i >> 1) ^ i);
		}
		return list;
	}

突然發現，自己真的是不適合干這行，太笨了！