难度: Medium
给你两个整数 n 和 start。你的任务是返回任意 (0,1,2,,...,2^n-1) 的排列 p，并且满足：
p[0] = startp[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 <= 160 <= start < 2^n运行时间: 108 ms
内存: 25.1 MB
ans = [[] for _ in range(17)]
ans[1] = [0,1]
for i in range(2,17):
l = []
for j in range(2**(i-1)-1,-1,-1):
l.append(ans[i-1][j]+2**(i-1))
ans[i] = ans[i-1] + l
class Solution:
def circularPermutation(self, n: int, start: int) -> List[int]:
l = ans[n]
i = l.index(start)
return l[i:] + l[:i]
这个题解使用了格雷码（Gray code）的性质来构造循环码排列。格雷码是一种二进制数系统，其中两个连续的数只有一位二进制位不同。首先，构造长度为 2^n 的格雷码序列。然后，找到序列中值为 start 的元素，并将这个序列从这个元素开始重新排列，使得首元素为 start。这样就得到了符合条件的循环码排列。
时间复杂度: O(2^n)
空间复杂度: O(2^n)
ans = [[] for _ in range(17)]
ans[1] = [0,1]
for i in range(2,17):
l = []
for j in range(2**(i-1)-1,-1,-1):
l.append(ans[i-1][j]+2**(i-1)) # 将前一半的格雷码反向遍历，并加上 2^(i-1)
ans[i] = ans[i-1] + l # 合并前一半和后一半的格雷码
class Solution:
def circularPermutation(self, n: int, start: int) -> List[int]:
l = ans[n]
i = l.index(start) # 找到起始位置
return l[i:] + l[:i] # 重新排列序列，使得首元素为 start
格雷码（Gray code）是一种二进制编码方式，其中任意两个连续的数在二进制形式下只有一位不同。这种编码的设计使得每次转换只涉及到一个二进制位的改变，减少了错误和复杂性。它在硬件设计中特别有用，因为在多位同时改变时可能引起错误的风险更高。格雷码的构造可以通过递归方法实现。基本的构造方法是：先取一个较小的格雷码序列，然后创建一个新序列，它是原序列的反向并在每个数前加上一个高位的1。这样确保了新生成的序列的前半部分和后半部分只在新加的最高位上有差异，而在拼接点处的两个数（前半部分的最后一个数和后半部分的第一个数）也保证只有一位不同。
题解中的方法通过首先生成一个完整的格雷码序列，然后找到序列中的某个特定起始值'start'，并以此值为起点重新排列格雷码序列，从而生成一个循环序列。具体来说，从'start'开始的元素到序列末尾的元素先被取出，然后将序列开始到'start'之前的元素接在后面。这种重组方法利用了格雷码本身连续元素只改变一位的特性，保证了即使在新序列的末尾到开头的过渡也仅涉及一位的变化，从而维持了循环序列的连续性和一致性。
在格雷码的构造过程中，反向遍历前一半的格雷码并在每个数前加上2^(i-1)（即添加一个更高位的1），这一步骤的目的是生成一组新的数，它们与原来的序列在新的最高位上有所区别，从而实现长度翻倍的新格雷码序列。这样做的关键在于，反向遍历保证了新添加的部分（后半部分）的第一个元素与原序列（前半部分）的最后一个元素只在新加的这一位上有差异，确保了格雷码的连续性。此外，由于原序列已经满足格雷码的条件，反向遍历并添加相同的高位不会破坏原有序列内部的每两个连续数字只改变一位的性质。