leetcode真题-格雷码

一秉

题目：格雷码是一个二进制数字系统，其中两个连续的值仅相差一位。
给定一个代表代码中位数总数的非负整数n，则打印格雷码序列。格雷码序列必须以0开头。
示例：
输入：  2
输出： [0,1,3,2]
说明：
00 - 0
01 - 1
11 - 3
10 - 2
对于给定的  n，格雷码序列可能没有唯一定义。
例如，[0,2,3,1]也是有效的格雷码序列。
解析：
假设我们找到了GrayCode（n-1）的解决方案，即一个包含2 ^（n-1）个元素的向量（向量中的元素都是字符串，如“ 00010”），我们需要做的是追加每个元素一个“ 0”，然后复制向量，将其反转，然后将我们刚刚附加的所有“ 0”替换为“ 1”。最后，我们合并这两个列表，仅此而已。
代码：
class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<Integer>();
        res.add(0);

        int offset = 1;
        for(int i = 1 ; i <= n ; i ++) {
            for (int j = res.size() - 1; j >= 0 ; j --) {
                res.add(res.get(j) + offset);
            }
            offset <<= 1;
        }

        return res;
    }
}