89 Gray Code

https://leetcode.com/problems/gray-code/#/description

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integernrepresenting the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, givenn= 2, return[0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a givenn, 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位所有的可能

内层循环表示，在上一个数位长度基础上的所有数，前面都加一个1.

但是要反着处理

举个例子，如果我们已经处理完2位了，arrayList里面有这些数

000, 001, 011, 010 那么下面的数应该是 101, 111, 101, 100

public List<Integer> grayCode(int n) {
    List<Integer> res = new ArrayList<>();
    res.add(0);
    for(int i = 0; i < n; i++) {
        int size = res.size();
        for(int j = size - 1; j >= 0; j--) {
            res.add(res.get(j) | 1 << i);
        }
    }
    return res;
}

O(2^n)