Grey Code

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.

找规律

复杂度

时间 O(N) 空间 O(N)

思路

仔细观察格雷码
当n=1时

1
0

当n=2时

00
01
11
10

当n=3时

000
001
011
010
110
111
101
100

可以发现，n的格雷码，就是n-1的格雷码，再加上它们的逆序前面多一个1。

代码

public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<Integer>();
        // 加入初始值0
        res.add(0);
        for(int i = 0; i < n; i++){
            // 每一轮的最高位
            int highestBit = 1 << i;
            int size = res.size();
            // 逆序添加上一轮里出现的数，不过开头加上这一轮的最高位
            for(int j = size - 1; j >= 0; j--){
                int num = res.get(j);
                num += highestBit;
                res.add(num);
            }
        }
        return res;
    }
}

公式法

复杂度

时间 O(N) 空间 O(N)

思路

工业中的第i个格雷码是这么生成的：(i>>1)^i
i是指下标，从0开始，对于n的格雷码序列，一共有2^n个数

代码

public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<Integer>();
        for(int i = 0; i < 1 << n; i++) res.add((i >> 1)^i);
        return res;
    }
}