生成格雷码（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=1时，格雷码为{“0”}，{“1”}，当n=2时，格雷码为{“00”，“01”}，{“11”，“10”}，当n=3时，格雷码为{“000”，“001”，“011”，“010”}，{“110”，“111”，“101”，“100”}。。。看到这里我们是否发现了一个规律，就

是n位的格雷码是在n-1的基础上，先从前往后扫描，在最前面插入一个“0”，然后从后往前扫描，插入一个“1”.

以此类推，便可得到结果。

	public ArrayList<Integer> grayCode(int n) 
	{
		ArrayList<Integer> answer = new ArrayList<Integer>();
		if(n==0)
		{
			answer.add(0);
			return answer;
		}
		ArrayList<String> result = generateCode(n);
		
		for(String str : result)
		{
			answer.add(transfer(str));
		}
		return answer;
    }
	//二进制转十进制
	public int transfer(String binary)
	{
		int result = 0;
		for(int i = binary.length()-1;i>=0;i--)
		{
			result+=(binary.charAt(i)-‘0‘)*(int)Math.pow(2, binary.length()-i-1);
		}
		return result;
	}
	public ArrayList<String> generateCode(int n)
	{
		ArrayList<String> tmp = new ArrayList<String>();
		ArrayList<String> result = new ArrayList<String>();
		tmp.add("0");
		tmp.add("1");
		if(n==1)
		{
			return tmp;
		}
		for(int i = 2;i<=n;i++)
		{
			result = new ArrayList<String>();
			for(String str : tmp)
			{
				result.add("0"+str);
			}
			for(int j = tmp.size()-1;j>=0;j--)
			{
				result.add("1"+tmp.get(j));
			}
			tmp = result;
		}
		return result;
	}

生成格雷码（Gray Code）

原文：http://blog.csdn.net/cow__sky/article/details/19703237