89. Gray Code ---M

Q:
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.
A:     递归调用而已

class Solution {
public:
    vector<int> grayCode(int n) {        
        if(n==0)
            return vector<int>{0};        
        auto sub = grayCode(n-1);
        int subSize = sub.size();
        for(int i =subSize -1 ; i>=0; i--){
            sub.push_back(sub[i] + pow(2,n-1));
        }
        return sub;
    }
};

Error: 
 1: 刚开始，base情况设为了n == 1
2： 后面要加的时候，没有逆序



-------------------第二遍，迭代，基于binary的一个个位置的从0变1， 就把之前的list都copy下来，再0变1.  -----------

public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> al = new LinkedList();
        al.add(0);
        int start = 0;
        for(int i =0;i<n;i++){
            List<Integer> copyAL = new LinkedList(al);
            for(int j =copyAL.size()-1;j>=0;j--)
                al.add( (1<<i) +copyAL.get(j));
        }
        return al;
    }
}

Mistakes:
1: curList  必须先initialize （刚开始，是在n ==0, 和n==1的时候，initilize了，但是， 其余的情况，就忘了initialize了）

2：输入为0 的时候，输入应该是 【0】， 而不是空的----------》这个是应该面试的时候问明白。

0
Output:	[]
Expected:	[0]

Learned:
1:  直接把一个数组，转换成String是不太容易的。 结果会有【】 出现。 例如下面：
        int[] iArray= {2,3};
        String str = Arrays.toString(tmp);
        System.out.println(str);
因此，要把“，” 去掉，  还有前后的[] 也要去掉。

String temp = Arrays.toString(iArray).replace(", ", " ");
String encoded = temp.substring(1, temp.length()-2);