Gray Code leetcode

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位(2^n 个码)变为n+1位(2^n+1)个码:

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

n = 0时，[0]

n = 1时，[0,1]

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

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

所以从头开始构建, n每增加1 就把当前2^n个结果逆序并且在前面+1 再加到结果中得到2^n+1个结果

1 << n 二进制的位运算: 1 向左移动n位 >>是向右移动
算法复杂度是O(2+2^2+...+2^n-1)=O(2^n)，所以是指数量级的，因为是结果数量无法避免。空间复杂度则是结果的大小，也是O(2^n)。

public class Solution {
    /**
     * @param n a number
     * @return Gray code
     */
    public ArrayList<Integer> grayCode(int n) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        
        res.add(0);
        if (n == 0) {
            return res;
        }
        res.add(1);
        for (int j = 2; j <=n; j++) {
            int size = res.size();
            int addnum = 1 << j-1;
            for (int i = size - 1; i >= 0; i--) {
                res.add(addnum + res.get(i));
            }
        }
        return res;
    }
}