原文链接: https://leetcode-cn.com/problems/circular-permutation-in-binary-representation

英文原文

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：

输入：n = 2, start = 3
输出：[3,2,0,1]
解释：这个排列的二进制表示是 (11,10,00,01)
     所有的相邻元素都有一位是不同的，另一个有效的排列是 [3,1,0,2]

示例 2：

输出：n = 3, start = 2
输出：[2,6,7,5,4,0,1,3]
解释：这个排列的二进制表示是 (010,110,111,101,100,000,001,011)

 

提示：

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

通过代码

高赞题解

时间: O(n)
空间: O(1)

三步解决问题

1. 生成格雷码，与第89题相同
2. 找到start的位置
3. 旋转数组，与第189题相同

如何生成格雷码？
基于格雷码是反射码的事实，利用如下规则：

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

例如： 生成一个3位格雷码的过程

• 初始: 0,1
• 复制前一行，添加前缀0: 00, 01
  逆序复制前一行，添加前缀1: 11, 10
  于是得到 00, 01, 11, 10
• 复制前一行，添加前缀0: 000, 001, 011, 010
  逆序复制前一行，添加前缀1: 110, 111, 101, 100
  于是得到 000, 001, 011, 010, 110, 111, 101, 100

vector<int> circularPermutation(int n, int start) {
    vector<int> res = {0,1};
    for(int i = 2;i <= n;i++){
        for(int j = res.size()-1;j >= 0;j--){
            res.push_back(res[j] + (1 << (i-1)));
        }
    }
        
    int l = 0,r = res.size()-1;
    while(l <= r){
        if(res[l] == start || res[r] == start) break;
        l++,r--;
    }
        
    if(res[l] == start){
        reverse(res.begin(),res.end());
        reverse(res.begin(),res.end()-l);
        reverse(res.end()-l,res.end());
    }else{
        reverse(res.begin(),res.end());
        reverse(res.begin(),res.begin()+l+1);
        reverse(res.begin()+l+1,res.end());
    }
    return res;
}


## 统计信息
| 通过次数 | 提交次数 | AC比率 |
| :------: | :------: | :------: |
|    3251    |    4905    |   66.3%   |

## 提交历史
| 提交时间 | 提交结果 | 执行时间 |  内存消耗  | 语言 |
| :------: | :------: | :------: | :--------: | :--------: |