0089. Gray Code

题目信息

题号:
  1. 格雷编码

难度:

Medium

主题:

位运算、构造、二进制反射

原题:

LeetCode 0089

重点:

从超立方体路径搜索,推导到镜像反射与 i ^ (i >> 1) 闭式

题目重述

给定整数 n,返回一个长度为 2^n 的整数序列,满足:

  • 第一个整数为 0;

  • 0 到 2^n - 1 中的每个整数恰好出现一次;

  • 任意相邻两个整数的二进制表示恰好有一位不同;

  • 最后一个整数与第一个整数也恰好有一位不同。

任意满足条件的序列均可返回。约束为 1 <= n <= 16。

自建示例

输入:n = 2
输出:[0,1,3,2]

对应二进制序列为 00,01,11,10。相邻项只改变一位,末项 10 与首项 00 也只改变一位。

输入:n = 3
输出:[0,1,3,2,6,7,5,4]

它在二位 Gray 序列后拼接反向序列,并为后半部分补上新的最高位。

C++ 实现

#include <vector>

class Solution {
private:
    bool differsByOneBit(int first, int second) {
        int difference = first ^ second;
        return difference != 0 &&
               (difference & (difference - 1)) == 0;
    }

    bool buildCycle(int current, int n,
                    std::vector<char>& used,
                    std::vector<int>& path) {
        if (path.size() == used.size()) {
            return differsByOneBit(path.back(), path.front());
        }

        for (int bit = 0; bit < n; ++bit) {
            int next = current ^ (1 << bit);
            if (used[next]) {
                continue;
            }

            used[next] = true;
            path.push_back(next);

            if (buildCycle(next, n, used, path)) {
                return true;
            }

            path.pop_back();
            used[next] = false;
        }
        return false;
    }

    std::vector<int> hypercubeSearch(int n) {
        int total = 1 << n;
        std::vector<char> used(total);
        std::vector<int> path{0};
        used[0] = true;
        buildCycle(0, n, used, path);
        return path;
    }

    std::vector<int> reflection(int n) {
        int total = 1 << n;
        std::vector<int> result{0};
        result.reserve(total);

        for (int bit = 0; bit < n; ++bit) {
            int prefix = 1 << bit;
            int oldSize = static_cast<int>(result.size());

            for (int index = oldSize - 1; index >= 0; --index) {
                result.push_back(prefix | result[index]);
            }
        }
        return result;
    }

    std::vector<int> directFormula(int n) {
        int total = 1 << n;
        std::vector<int> result;
        result.reserve(total);

        for (int value = 0; value < total; ++value) {
            result.push_back(value ^ (value >> 1));
        }
        return result;
    }

public:
    std::vector<int> grayCode(int n) {
        return directFormula(n);
    }
};

题解

超立方体搜索

把每个 n 位整数看作一个顶点。两个整数只相差一位时,它们之间连一条边。题目要求从顶点 0 出发,访问全部 2^n 个顶点一次,并让末顶点还能通过一条边回到 0。

最直接的回溯维护当前顶点、已访问集合和路径。下一步枚举翻转哪一位,得到:

next = current XOR (1 << bit)

路径包含全部顶点后,再检查首尾异或值是否为 2 的幂。这个模型准确,但它在大量候选路径之间搜索, 没有利用 Gray Code 的确定结构。

镜像反射

从一位序列 [0,1] 继续增加位数。假设已有 k 位 Gray 序列:

00, 01, 11, 10

构造 k+1 位序列时:

  • 前半部分保持原顺序,新最高位补 0;

  • 后半部分按原序列的逆序排列,新最高位补 1。

原序列:00, 01, 11, 10
逆序列:10, 11, 01, 00
新序列:000,001,011,010,110,111,101,100

前半内部沿用旧序列的一位差性质。后半只统一增加一个最高位,内部差异仍由低位决定。 两半连接处是 010 与 110,低位完全相同,只改变新增最高位。

首尾成环

反射构造的首项始终为全 0。后半最后一项来自旧序列首项 0,只增加当前最高位,因此新序列末项 恰好只有最高位为 1。它与首项也只相差一位,循环条件随位数扩展一直成立。

闭式生成

二进制反射 Gray Code 的第 i 项可直接写成:

gray(i) = i XOR (i >> 1)

设二进制位为 b,Gray 位为 g,则:

g[k] = b[k + 1] XOR b[k]

每个 Gray 位记录相邻两层二进制位是否不同,这正是镜像反射在各层产生的翻转关系。

相邻一位差

从 i 增加到 i+1 时,二进制会把末尾连续的 1 变为 0,并把它们上方第一个 0 变为 1。 因此 i XOR (i+1) 是一段连续的低位 1。

Gray 公式还会把该差异右移一位再异或,连续低位 1 中除最高位外都两两抵消,最终只剩一个置位。 所以:

gray(i) XOR gray(i + 1)

始终是 2 的幂,相邻编码恰好相差一位。

完整覆盖

Gray 映射可以从高位向低位恢复原二进制数:最高二进制位等于最高 Gray 位,之后使用 b[k] = b[k + 1] XOR g[k] 逐位恢复。映射可逆,因此不同输入不会得到相同输出。

公式枚举 0 到 2^n - 1 后,会得到 2^n 个互不相同且仍在该范围内的整数,因而完整覆盖 所有 n 位整数。

复杂度

回溯搜索最坏需要探索指数级路径。反射构造和闭式生成都输出 2^n 个整数,时间与输出空间均为 Theta(2^n)。闭式方法除返回结果外只使用常量额外空间,达到输出规模决定的下界。