LeetCode-Gray Code

##题目

####Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

##解题思路
学过格雷码的童鞋应该比较好理解，比如n=3时

000
001
011
010
------
110
111
101
100

规律是将格雷码看成是上下两部分，上部分是第一位为0，下部分是第一位为1，这样后面n-1位即为n-1位的格雷码。例如

n=1 
0
--
1
上 0  下 1

n=2
00
01
---
11
10
上为n=1时的格雷码 下为n=1时的格雷码的倒序再加上最前面的1

找到了如上的规律，则求解n位的格雷码就是从1位格雷码不断求解即可

##算法代码
代码采用JAVA实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public class Solution {
    public ArrayList<Integer> grayCode(int n) {
        ArrayList<Integer> res=new ArrayList<Integer>();
        if(n<0)
        	return res;
        if(n==0)
        {
        	res.add(0);
        	return res;
        }
        //n=1的格雷码
        res.add(0);
        res.add(1);
        for(int i=2;i<=n;i++)
        {
        	int num=1<<(i-1);
        	//第i位格雷码为（第i-1位格雷码前面+0）和（第i-1位格雷码倒序后前面+1）
        	//而前面+0即为i-1位的格雷码，所以不需要做
        	//只需要对i-1位进行倒序，然后前面+1
        	for(int j=res.size()-1;j>=0;j--)
        		res.add(res.get(j)+num);
        }
        return res;
    }
}