Gray Code -- LeetCode

接下来看看怎样接上剩下的2^(n-1)个。我们把n-1位的格雷码倒序排列。然后在每一个前面加入1。然后接到上述的前2^(n-1)个就能够了。首先由于是倒序过来，所以中间两个元素除去第一位其它都是一样的（由于原来最后一个，如今倒序过来就是第一个），而他们第一位各自是0和1，满足格雷码的要求。而剩下的元素由于我们是n-1位的格雷码倒序排列，所以两两都是满足要求的，加上前面都一样的位1。仍然满足条件。最后看看这些数字是不是都不一样。前半部分和后半部分肯定不会一样，而由于前半部分都是0开头，后半部分都是1打头，所以互相之间也不会有反复，能够看出覆盖了全部数字，并且依次下来均满足条件。

如此我们提出了格雷码的递推方法，我们仅仅须要做一次位数的循环，每次依据上面结果构造当前位数的结果就可以。算法复杂度是O(2+2^2+...+2^n-1)=O(2^n)。所以是指数量级的，由于是结果数量无法避免。

空间复杂度则是结果的大小，也是O(2^n)。

代码例如以下：

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;
    }
    res.add(0);
    res.add(1);
    for(int i=2;i<=n;i++)
    {
        int size = res.size();
        for(int j=size-1;j>=0;j--)
        {
            res.add(res.get(j)+(1<<(i-1)));
        }
    }
    return res;
}