題目鏈接

Leetcode.1238 循環(huán)碼排列 Rating ： 1775

題目描述

給你兩個(gè)整數(shù) n和 start。你的任務(wù)是返回任意 (0,1,2,,...,2^n-1)的排列 p，并且滿足：

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

示例 1：

輸入：n = 2, start = 3
輸出：[3,2,0,1]
解釋：這個(gè)排列的二進(jìn)制表示是 (11,10,00,01)
所有的相鄰元素都有一位是不同的，另一個(gè)有效的排列是 [3,1,0,

示例 2：

輸出：n = 3, start = 2
輸出：[2,6,7,5,4,0,1,3]
解釋：這個(gè)排列的二進(jìn)制表示是 (010,110,111,101,100,000,001,011)

提示：

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

分析：
根據(jù)題目要求的 二進(jìn)制表示形式只有一位不同就表明了我們要構(gòu)造的就是 格雷碼。學(xué)過 數(shù)字電路 的同學(xué)可能對(duì)它還有印象。

對(duì)于這樣的 從高位到低位 的二進(jìn)制數(shù) $B=B_{n?1}{B}_{n?2}...B_3{B}_2{B}_1{B}_0$，有他對(duì)應(yīng)的格雷碼 $G=G_{n?1}{G}_{n?2}...G_3{G}_2{G}_1{G}_0$。

二進(jìn)制數(shù) 轉(zhuǎn)換成 格雷碼 的規(guī)則如下：

• 對(duì)于最高位保留，即 $G_{n?1}=B_{n?1}$。
• 除了最高位的其他位，$G_i=B_{i+1}\oplus B_i$

所以我們可以先預(yù)處理出所有的[0,2^n)格雷碼，最后再按照 start分成兩段拼起來即可。

時(shí)間復(fù)雜度：$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 即為 二進(jìn)制數(shù)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;}
}