题目

n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：

  • 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
  • 第一个整数是 0
  • 一个整数在序列中出现 不超过一次
  • 每对 相邻 整数的二进制表示 恰好一位不同 ，且
  • 第一个 和 最后一个 整数的二进制表示 恰好一位不同

给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

来源：力扣（LeetCode）

解答

用找规律的方法进行递归。

alt

可以发现，求给定n的数组，结果可以分成两部分，一部分是0开头 + （（n - 1） 的答案），另一部分是 1 开头 + （（n-1）的答案的逆序），用递归即可求解。

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ret;

        if (n == 1) {
            return {0, 1};
        }

        auto get = grayCode(n - 1);
        for (auto i: get) {
            ret.push_back(i);
        }

        int sz = get.size();
        for (int i = sz - 1; i >= 0; --i) {
            ret.push_back(get[i] + (1 << (n - 1)));
        }

        return ret;
    }
};