题目描述

Given 2 integers n and start. Your task is return any permutation p of (0,1,2.....,2^n -1)such that :

• p[0] = start
• p[i] and p[i+1] differ by only one bit in their binary representation.
• p[0] and p[2^n -1] must also differ by only one bit in their binary representation.

Example 1:

Input: n = 2, start = 3
Output: [3,2,0,1]
Explanation: The binary representation of the permutation is (11,10,00,01). 
All the adjacent element differ by one bit. Another valid permutation is [3,1,0,2]

Example 2:

Input: n = 3, start = 2
Output: [2,6,7,5,4,0,1,3]
Explanation: The binary representation of the permutation is (010,110,111,101,100,000,001,011).

Constraints:

• 1 <= n <= 16
• 0 <= start < 2 ^ n

题意：给你两个整数n和 start。你的任务是返回任意(0,1,2,,...,2^n-1) 的排列 p，并且满足：

p[0] = start
p[i]和p[i+1] 的二进制表示形式只有一位不同
p[0] 和 p[2^n -1] 的二进制表示形式也只有一位不同

算法1

题解：该问题可以分解为以下三个部分：

1. 我们首先考虑从0开始生成n位格雷码(Leetcode89)
2. 找到start在格雷码数组中的位置k（遍历即可）
3. 将数组向左循环移动k位(Leetcode189)。

    vector<int> circularPermutation(int n, int start) {
        vector<int> res = {0,1};
        int size = 2,t = 2;
        // 生成n位格雷码
        for(int i = 2 ; i <= n ; i ++)
        {
            vector<int> cur;
            cur.assign(res.begin(),res.end());
            for(int j = size - 1 ; j >= 0 ; j --)
                cur.push_back(res[j] + t);
            t = t << 1;
            size = size << 1;
            res = cur;
        }
        //  找到start是第多少位格雷码
        int u = 0;
        while(res[u] != start) u ++;

        // 开始循环移位数组,相当于将数组向右循环移动(size - u)位
        reverse(res.begin(),res.end());
        reverse(res.begin(),res.begin() + size - u);
        reverse(res.begin() + size - u,res.end());
        return res;
    }