格雷编码 图解题解

这道题到底在问什么

n

3

输出

[0,1,3,2,6,7,5,4]

长度

2³ = 8 个

最优解：一步一步想明白

1. 3回溯当然行,但又要记访问过哪些、又要翻哪一位、还可能走死胡同回退。有没有「直接算出来」的办法?
2. 4i >> 1 是把 i 右移一位(去掉最低位),再和 i 本身异或。下面我们就逐个 i 套这条公式,把 8 个数一个个算出来填进序列。
3. 58 个格子待填这排 8 个格子就是要填的序列(先全看成 0)。指针停在第 0 格,我们让 i 从 0 走到 7,每步算一个格雷码填进对应格子。
4. 60 ^ 0 = 0 → 000i=0:右移还是 0,0 ^ 0 = 0。第 0 个格雷码是 000,填进第 0 格。序列从 0 开头,符合要求。
5. 71 ^ 0 = 1 → 001i=1:1 右移变 0,1 ^ 0 = 1,二进制 001。和上一个 000 比,只有最低位从 0 变 1——差一位,达标。
6. 82 ^ 1 = 3 → 011i=2 是 010,右移成 001,010 ^ 001 = 011 = 3。和上一个 001 比,只翻了第二位。填 3 进第 2 格。
7. 93 ^ 1 = 2 → 010i=3 是 011,右移 001,011 ^ 001 = 010 = 2。和上一个 011 比,只翻最低位。填 2 进第 3 格。前四个:0,1,3,2。
8. 104 ^ 2 = 6 → 110i=4 是 100,右移成 010,100 ^ 010 = 110 = 6。和上一个 010 比,只翻最高位。填 6 进第 4 格。
9. 115 ^ 2 = 7 → 111i=5 是 101,右移 010,101 ^ 010 = 111 = 7。和上一个 110 比,只翻最低位。填 7 进第 5 格。
10. 126 ^ 3 = 5 → 101i=6 是 110,右移成 011,110 ^ 011 = 101 = 5。和上一个 111 比,只翻中间位。填 5 进第 6 格。
11. 137 ^ 3 = 4 → 100i=7 是 111,右移 011,111 ^ 011 = 100 = 4。和上一个 101 比,只翻最低位。填 4 进最后一格,8 个全填完!
12. 14[0,1,3,2,6,7,5,4]8 个数全部算出:0,1,3,2,6,7,5,4。一条公式 i^(i>>1) 顺序套一遍就出结果,不用判重、不用回退。
13. 15000 vs 001 · 差1位 ✓现在逐对验证「相邻只差一位」。第 0 和第 1 个:000 与 001,异或得 001,只有一位是 1,达标。
14. 16001 vs 011 · 差1位 ✓第 1 和第 2 个:001 与 011,异或得 010,只翻一位,达标。高亮对往右滑一格。
15. 17011 vs 010 · 差1位 ✓第 2 和第 3 个:011 与 010,异或得 001,只翻最低位,达标。
16. 18010 vs 110 · 差1位 ✓第 3 和第 4 个:010 与 110,异或得 100,只翻最高位,达标。跨过中点也照样成立。
17. 19110 vs 111 · 差1位 ✓第 4 和第 5 个:110 与 111,异或得 001,只翻最低位,达标。
18. 20111 vs 101 · 差1位 ✓第 5 和第 6 个:111 与 101,异或得 010,只翻中间位,达标。
19. 21101 vs 100 · 差1位 ✓第 6 和第 7 个:101 与 100,异或得 001,只翻最低位,达标。中间 7 对全部过关。
20. 22100 → 000 闭环最后看首尾:第 7 个 100 和第 0 个 000 比,也只差最高位一位——题目要的「首尾相连」也天然满足。8 对全部通过!
21. 23下面我们不套公式,改用「照镜子」的办法,从 n=1 一层层长到 n=3,看序列怎么翻倍生长,每步只动一个新加入的数。
22. 24[0, 1]n=1 最简单:就是 0, 1(前两格)。把它当「种子」,后面靠照镜子长大。
23. 250,1 前补 0 → 00,01造 n=2:上半段直接抄 n=1 的 0,1,在最高位补 0,值不变还是 0,1。下半段(灰色)马上由镜像填出来。
24. 26逆序 1,0 前补 1 → 11,10下半段把 n=1 序列倒过来(1,0),各自最高位补 1:11=3, 10=2。拼起来 n=2 = 0,1,3,2,和公式法一模一样!
25. 27抄 n=2,前补 0造 n=3:上半段照抄 n=2 的 0,1,3,2,最高位补 0 值不变。下半段(灰色)再镜像一次。
26. 28逆序 2,3,1,0 前补 1下半段把 n=2 序列倒过来(2,3,1,0),最高位补 1(即 +4):6,7,5,4。拼成 n=3 = 0,1,3,2,6,7,5,4——和公式法分毫不差。两条路殊途同归。
27. 29直观理解:相邻整数 i 与 i+1 在二进制上变化集中在低位进位;公式 i^(i>>1) 把这种规律「折叠」成恰好一位的改变。记住公式会用就足够应对面试。
28. 33循环 4 次 → [0,1,3,2]换 n=2 验证:循环 2² = 4 次,套公式得 0,1,3,2,即 00→01→11→10,相邻仍只差一位。若把循环写成 range(2) 只跑 2 次,就只剩 0,1——这就是雷区①。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def grayCode(self, n):
        res = []
        for i in range(1 << n):      # i 从 0 到 2^n - 1
            res.append(i ^ (i >> 1)) # 公式直接出第 i 个
        return res

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res;
        for (int i = 0; i < (1 << n); i++) {
            res.push_back(i ^ (i >> 1));
        }
        return res;
    }
};

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < (1 << n); i++) {
            res.add(i ^ (i >> 1));
        }
        return res;
    }
}

复杂度

面试官可能追问