题目描述
思路解析动画文字版
记牢两步:第一步用公式造灰码序列,第二步把序列旋转到 start 开头。下面每帧都在套这两步。
总览 · 先把灰码序列一个一个算出来：舞台上是即将生成的灰码序列 g,一共 8 个槽位,现在都是灰的、还没算。规则只有一条公式:第 i 个数等于 i 异或上「i 右移一位」。从 i=0 开始,一个一个往右填。
生成 g[0] · 二进制 000 异或 000 = 000：算第 0 个:i=0(二进制 000)右移一位得 0(二进制 000),两者异或得 0(二进制 000)。它是序列开头,固定从 0 出发。
生成 g[1] · 二进制 001 异或 000 = 001：算第 1 个:i=1(二进制 001)右移一位得 0(二进制 000),两者异或得 1(二进制 001)。它和上一个 g[0] = 0(二进制 000)对比,二进制 001 与 000 恰好只有一位不同,相邻差一位成立。
生成 g[2] · 二进制 010 异或 001 = 011：算第 2 个:i=2(二进制 010)右移一位得 1(二进制 001),两者异或得 3(二进制 011)。它和上一个 g[1] = 1(二进制 001)对比,二进制 011 与 001 恰好只有一位不同,相邻差一位成立。
生成 g[3] · 二进制 011 异或 001 = 010：算第 3 个:i=3(二进制 011)右移一位得 1(二进制 001),两者异或得 2(二进制 010)。它和上一个 g[2] = 3(二进制 011)对比,二进制 010 与 011 恰好只有一位不同,相邻差一位成立。
生成 g[4] · 二进制 100 异或 010 = 110：算第 4 个:i=4(二进制 100)右移一位得 2(二进制 010),两者异或得 6(二进制 110)。它和上一个 g[3] = 2(二进制 010)对比,二进制 110 与 010 恰好只有一位不同,相邻差一位成立。
生成 g[5] · 二进制 101 异或 010 = 111：算第 5 个:i=5(二进制 101)右移一位得 2(二进制 010),两者异或得 7(二进制 111)。它和上一个 g[4] = 6(二进制 110)对比,二进制 111 与 110 恰好只有一位不同,相邻差一位成立。
生成 g[6] · 二进制 110 异或 011 = 101：算第 6 个:i=6(二进制 110)右移一位得 3(二进制 011),两者异或得 5(二进制 101)。它和上一个 g[5] = 7(二进制 111)对比,二进制 101 与 111 恰好只有一位不同,相邻差一位成立。
生成 g[7] · 二进制 111 异或 011 = 100：算第 7 个:i=7(二进制 111)右移一位得 3(二进制 011),两者异或得 4(二进制 100)。它和上一个 g[6] = 5(二进制 101)对比,二进制 100 与 101 恰好只有一位不同,相邻差一位成立。
定位 start=2 · 在下标 3：序列造好了:[0, 1, 3, 2, 6, 7, 5, 4]。它天然满足相邻只差一位,可它是从 0 开头的,而题目要 start=2 打头。先在 g 里找到 2 的位置,它在下标 3(绿色标出)。下一步就把序列从这里旋转过去。
切开 · 下标 3 之前与之后分两段：把序列在下标 3 处切成两段:绿色是从 start 开始到末尾的前段 [2, 6, 7, 5, 4],蓝色是开头到 start 之前的后段 [0, 1, 3]。旋转就是把绿色段搬到最前面、蓝色段接到它后面。
旋转(1/2) · 前段顶到开头：先把绿色前段 [2, 6, 7, 5, 4] 整段搬到最前面。这样第 0 个数就是 2,正好等于 start=2,第一个约束达成。后面还差把蓝色段接上。
旋转(2/2) · 后段接到末尾：再把蓝色后段 [0, 1, 3] 接到末尾(绿色高亮)。拼出来完整排列 p = [2, 6, 7, 5, 4, 0, 1, 3]。它就是 g[3:] 接上 g[:3] 的结果。接下来逐对检查:相邻是不是真的只差一位。
验相邻 · p[0] 与 p[1]：检查第 0 和第 1 这对:2(二进制 010)和 6(二进制 110),异或结果 100,里面只有一个 1,落在第 2 位,说明只翻了一个比特,相邻差一位成立。
验相邻 · p[1] 与 p[2]：检查第 1 和第 2 这对:6(二进制 110)和 7(二进制 111),异或结果 001,里面只有一个 1,落在第 0 位,说明只翻了一个比特,相邻差一位成立。
验相邻 · p[2] 与 p[3]：检查第 2 和第 3 这对:7(二进制 111)和 5(二进制 101),异或结果 010,里面只有一个 1,落在第 1 位,说明只翻了一个比特,相邻差一位成立。
验相邻 · p[3] 与 p[4]：检查第 3 和第 4 这对:5(二进制 101)和 4(二进制 100),异或结果 001,里面只有一个 1,落在第 0 位,说明只翻了一个比特,相邻差一位成立。
验相邻 · p[4] 与 p[5]：检查第 4 和第 5 这对:4(二进制 100)和 0(二进制 000),异或结果 100,里面只有一个 1,落在第 2 位,说明只翻了一个比特,相邻差一位成立。
验相邻 · p[5] 与 p[6]：检查第 5 和第 6 这对:0(二进制 000)和 1(二进制 001),异或结果 001,里面只有一个 1,落在第 0 位,说明只翻了一个比特,相邻差一位成立。
验相邻 · p[6] 与 p[7]：检查第 6 和第 7 这对:1(二进制 001)和 3(二进制 011),异或结果 010,里面只有一个 1,落在第 1 位,说明只翻了一个比特,相邻差一位成立。
验首尾 · p[7] 与 p[0] 成环：最后看首尾这一对(环形):末尾 3(二进制 011)和开头 2(二进制 010),异或得 001,只有第 0 位不同。环也只差一位,第三个约束达成。8 个数全部检验通过。
边界都同一套路:先造 g,定位 start 的下标,旋转过去;n=1 时序列只有两个数也成立。
面试重点:公式是格雷码定义性质、旋转环不破坏相邻、还能用一次异或 start 的公式省掉数组。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def circularPermutation(self, n: int, start: int) -> List[int]: g = [i ^ (i >> 1) for i in range(1 << n)] j = g.index(start) return g[j:] + g[:j]复杂度
- 时间：O(2 的 n 次方)，设 N = 2 的 n 次方,即输出长度。生成灰码序列扫一遍 N、定位 start 最多扫一遍 N、旋转拼接再走一遍 N,三段都是线性,合起来还是 O(N)
- 空间：O(2 的 n 次方)，要存一条长度 N 的灰码序列,答案本身也有 N 个元素。按峰值占用算是 O(N);若不显式建数组、改用 p[i] = (i 异或 i 右移 1) 异或 start 直接公式输出,可降到除输出外 O(1)
易错点
面试追问把动画讲成自己的话
追问为什么 i 异或 (i 右移 1) 能保证相邻只差一位?
追问旋转之后,首尾为什么仍然只差一位?
追问有没有不显式建数组的写法?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
串联字符串的最大长度
LeetCode 1239 · 中等 · 沿着 回溯套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题