[leetcode]Gray Code

两种思路，详情请参考新博文地址：[leetcode]Gray Code

http://oj.leetcode.com/problems/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.

格雷码， 提示中称：[0,2,3,1]也是一组合法的格雷码，把我彻底搞糊涂了，既然如此，为什么要返回[0,1,3,2]而不能返回[0,2,3,1]呢？后来手贱去百度了一下格雷码。尼玛....

看下格雷码的特征：

n == 1时，[0,1]

n == 2时，[00,01,11,10]

n == 3时，[000,001,011,010,110,111,101,100]

1位格雷码有两个码字
(n+1)位格雷码中的前2n个码字等于n位格雷码的码字，按顺序书写，加前缀0
(n+1)位格雷码中的后2n个码字等于n位格雷码的码字，按逆序书写，加前缀1

前后两部分的后n - 1位是对称的。

知道定义之后，代码就很简单了

    public ArrayList<Integer> grayCode(int n) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		list.add(0);
		if (n <= 0) {
			if(n == 0)return list;
			else return new ArrayList<Integer>();
		}
			list.add(1);
		for (int i = 1; i < n; i++) {
			ArrayList<Integer> newList = new ArrayList<Integer>();
			for (int j = 0; j < list.size(); j++) {
				newList.add(list.get(j));
			}
			for (int k = list.size() - 1; k >= 0; k--) {
				newList.add((int) Math.pow(2, i) + list.get(k));
			}
			list = newList;
		}
		return list;
	}