题目
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.

答案

The gray code sequence contains number 0 to 2^n - 1

Consider the following examples

consider n = 1
0 - 0
1 - 1

consider n = 2
0 - 00
1 - 01
3 - 11
2 - 10

consider n = 3

0 - 000
1 - 001
3 - 011
2 - 010

6 - 110
7 - 111
5 - 101
4 - 100

consider n = 4

0 - 0000
1 - 0001
3 - 0011
2 - 0010
6 - 0110
7 - 0111
5 - 0101
4 - 0100

12 - 1100
13 - 1101
15 - 1111
14 - 1110
10 - 1010
11 - 1011
9 - 1001
8 - 1000

Interestingly, as long as you have the sequence for n = 2, you can generate the sequence for n = 3 by just setting the third bit(counting from right, start from 1 not 0) of every integer in the n=2 sequence to be 1.

Using the patter we find, let's code up a solution.
The solution uses some sort of dynamic programming thinking, as it reuses calculations done previously.

Wow, 竟然beat了100%，很好

class Solution {     
    public List<Integer> grayCode(int n) {
        List<Integer> list = new ArrayList<>();
        if(n == 0) return new ArrayList<Integer>(Arrays.asList(0));
        int[] dp = new int[(int) Math.pow(2, n)];
        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            // [0, 2^(i-1)) stays the same, copy values in [0, 2^(i-1)) to [2^(i - 1), 2^i), and set set (i-1)th bit to 1
            int offset = 1;
            int mask = 1 << (i - 1);
            int start = (int) Math.pow(2, i - 1), end = (int) Math.pow(2, i);
            for (int j = start; j < end; j++) {
                int k = start - offset++;
                dp[j] = dp[k] | mask;
            }
        }

        for (int i = 0; i < dp.length; i++)
            list.add(dp[i]);
        return list;
    }
}