Leetcode.1238 循环码排列

题目链接

Leetcode.1238 循环码排列 Rating ： 1775

题目描述

给你两个整数 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：

输出：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$

分析：
根据题目要求的 二进制表示形式只有一位不同就表明了我们要构造的就是 格雷码。学过 数字电路 的同学可能对它还有印象。

对于这样的 从高位到低位 的二进制数 $B=B_{n-1}{B}_{n-2}...B_3{B}_2{B}_1{B}_0$，有他对应的格雷码 $G=G_{n-1}{G}_{n-2}...G_3{G}_2{G}_1{G}_0$。

二进制数 转换成 格雷码 的规则如下：

• 对于最高位保留，即 $G_{n-1}=B_{n-1}$。
• 除了最高位的其他位，$G_i=B_{i+1}\oplus B_i$

所以我们可以先预处理出所有的[0,2^n)格雷码，最后再按照 start分成两段拼起来即可。

时间复杂度：$O(2^n)$

C++代码：

class Solution {
public:vector<int> circularPermutation(int n, int start) {vector<int> grey;int s = 0;for(int i = 0;i < (1 << n);i++){//x 即为 二进制数i 的格雷码int x = i ^ (i >> 1);//由 s 将 [0,2^n) 分为两段，[s,2^n) [0,s)if(x == start) s = i;grey.push_back(x);}vector<int> ans;//先加上以 s 开头的那段 即 [s,2^n)for(int i = s;i < (1 << n);i++) ans.push_back(grey[i]);//再拼接上这一段  [0,s)for(int i = 0;i < s;i++) ans.push_back(grey[i]);return ans;}
};

Java代码：

class Solution {public List<Integer> circularPermutation(int n, int start) {List<Integer> grey = new ArrayList<>();int s = 0;for(int i = 0;i < (1 << n);i++){int x = i ^ (i >> 1);if(x == start) s = i;grey.add(x);}List<Integer> res = new ArrayList<>();for(int i = s;i < (1 << n);i++) res.add(grey.get(i));for(int i = 0;i < s;i++) res.add(grey.get(i));return res;}
}