LeetCode（一）关于GrayCode的实现

在LeetCode上面有一道题，是关于Gray Code的实现的。

GrayCode是这样一种编码：

1 位Gray Code ：

0
1

先添加一个镜像，如下：

0
1
1
0

00
01
11
10

题目的要求是：

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];

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; }