题目来源

• leetcode：89. 格雷编码

题目描述

题目解析

下表为0为、1位、2位、3位、4位格雷码的实例，我们可以发现这样一个规律。

总结规律：

• 1位格雷码有两个码字
• (n+1)位格雷码中的前2^n个码字等于n位格雷码的码字，按顺序书写，加前缀0
• (n+1)位格雷码中的后2^n个码字等于n位格雷码的码字，按逆序书写，加前缀1
• n+1位格雷码的集合 = n位格雷码集合(顺序)加前缀0 + n位格雷码集合(逆序)加前缀1

根据这个规律就可以直接写代码了。

递归

class Solution {
    vector<int> helper(int n){
        if(n == 1){
            return {0, 1};
        }

        vector<int> pre = helper(n - 1);
        int len_0 = pre.size(), len_1 = 2 * len_0;
        std::vector<int> ans(len_1);
        int i ;
        for (i = 0; i < len_0; ++i) {
            ans[i] = pre[i];
        }

        int t = (1 << (n - 1));
        for (i = len_0; i < len_1; ++i) {
            ans[i] = pre[--len_0] ^ t;
        }
        return ans;
    }
public:
    vector<int> grayCode(int n) {
        return helper(n);
    }
};

class Solution {
public:
    vector<int> grayCode(int n) {
        std::vector<int> result;
        result.push_back(0);
        if (n == 0) {
            return result;
        }


        int first = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = result.size() - 1; j >= 0; --j) {
                result.push_back(first + result[j]);
            }
            first = first << 1;
        }

        return result;
    }
};