【leetcode】No.89：gray-code

题目描述

格雷码是一种二进制编码系统，如果任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code）。
给定一个非负整数n，表示代码的位数，打印格雷码的序列。格雷码序列必须以0开头。
例如：给定n=2，返回[0,1,3,2]. 格雷码的序列为：

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

注意：
对于一个给定的n，格雷码的序列不一定是唯一的，
例如：根据题目描述，[0,2,3,1]也是一个有效的格雷码序列

思路：

仔细观察上图，从后往前拿出数字，在最高位前面加1，因为最高位前面总是0，新加入的数字可以与尾部数字只有最高位前一位不同，而因为之前的序列是满足只有一位不同的，由于新的数字最高位都为1，所以这些数字也是满足要求的，而且这样可以保证遍历所有的情况。

代码：

import java.util.ArrayList;

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