89. 格雷编码

描述

n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
第一个整数是 0
一个整数在序列中出现 不超过一次
每对 相邻 整数的二进制表示 恰好一位不同 ，且
第一个 和 最后一个 整数的二进制表示 恰好一位不同
给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

分析

找规律G(n)的格雷码是在G(n-1)的基础上反转G(n-1)的格雷码且加上(1<<n-1)得来的。
比如G(1)的格雷码是00、01,G(2)的格雷码是00、01、11、10
G(2)的格雷码可以看成由00、01加上（01 | 1 << 1）、（00 | 1 << 1）得来，也就是G(2)的格雷码等于G(1)的格雷码加上反转后的G(1)的格雷码且给每个反转的G(1)格雷码加上2的1次方。
要求更高的格雷码可以从2开始推算得到。

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> ans = new ArrayList<>();
        ans.add(0);
        if(n == 0) return ans;
        ans.add(1);
        if(n == 1) return ans;

        int index = 1;
        while(index < n){
            int size = ans.size()-1;
            for(int i = size; i >= 0; i--){
                ans.add(ans.get(i) | 1 << index );
            }
            index++;
        }
        return ans;
    }
}