0089. Gray Code
===============
题目信息
--------
:题号: 0089. 格雷编码
:难度: Medium
:主题: 位运算、构造、二进制反射
:原题: `LeetCode 0089 `_
:重点: 从超立方体路径搜索,推导到镜像反射与 ``i ^ (i >> 1)`` 闭式
题目重述
--------
给定整数 ``n``,返回一个长度为 ``2^n`` 的整数序列,满足:
- 第一个整数为 0;
- ``0`` 到 ``2^n - 1`` 中的每个整数恰好出现一次;
- 任意相邻两个整数的二进制表示恰好有一位不同;
- 最后一个整数与第一个整数也恰好有一位不同。
任意满足条件的序列均可返回。约束为 ``1 <= n <= 16``。
自建示例
--------
.. code-block:: text
输入:n = 2
输出:[0,1,3,2]
对应二进制序列为 ``00,01,11,10``。相邻项只改变一位,末项 ``10`` 与首项 ``00``
也只改变一位。
.. code-block:: text
输入:n = 3
输出:[0,1,3,2,6,7,5,4]
它在二位 Gray 序列后拼接反向序列,并为后半部分补上新的最高位。
C++ 实现
--------
.. code-block:: cpp
#include
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& used,
std::vector& 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 hypercubeSearch(int n) {
int total = 1 << n;
std::vector used(total);
std::vector path{0};
used[0] = true;
buildCycle(0, n, used, path);
return path;
}
std::vector reflection(int n) {
int total = 1 << n;
std::vector result{0};
result.reserve(total);
for (int bit = 0; bit < n; ++bit) {
int prefix = 1 << bit;
int oldSize = static_cast(result.size());
for (int index = oldSize - 1; index >= 0; --index) {
result.push_back(prefix | result[index]);
}
}
return result;
}
std::vector directFormula(int n) {
int total = 1 << n;
std::vector result;
result.reserve(total);
for (int value = 0; value < total; ++value) {
result.push_back(value ^ (value >> 1));
}
return result;
}
public:
std::vector grayCode(int n) {
return directFormula(n);
}
};
题解
----
超立方体搜索
~~~~~~~~~~~~
把每个 ``n`` 位整数看作一个顶点。两个整数只相差一位时,它们之间连一条边。题目要求从顶点 0
出发,访问全部 ``2^n`` 个顶点一次,并让末顶点还能通过一条边回到 0。
最直接的回溯维护当前顶点、已访问集合和路径。下一步枚举翻转哪一位,得到:
.. code-block:: text
next = current XOR (1 << bit)
路径包含全部顶点后,再检查首尾异或值是否为 2 的幂。这个模型准确,但它在大量候选路径之间搜索,
没有利用 Gray Code 的确定结构。
镜像反射
~~~~~~~~
从一位序列 ``[0,1]`` 继续增加位数。假设已有 ``k`` 位 Gray 序列:
.. code-block:: text
00, 01, 11, 10
构造 ``k+1`` 位序列时:
- 前半部分保持原顺序,新最高位补 0;
- 后半部分按原序列的逆序排列,新最高位补 1。
.. code-block:: text
原序列:00, 01, 11, 10
逆序列:10, 11, 01, 00
新序列:000,001,011,010,110,111,101,100
前半内部沿用旧序列的一位差性质。后半只统一增加一个最高位,内部差异仍由低位决定。
两半连接处是 ``010`` 与 ``110``,低位完全相同,只改变新增最高位。
首尾成环
~~~~~~~~
反射构造的首项始终为全 0。后半最后一项来自旧序列首项 0,只增加当前最高位,因此新序列末项
恰好只有最高位为 1。它与首项也只相差一位,循环条件随位数扩展一直成立。
闭式生成
~~~~~~~~
二进制反射 Gray Code 的第 ``i`` 项可直接写成:
.. code-block:: text
gray(i) = i XOR (i >> 1)
设二进制位为 ``b``,Gray 位为 ``g``,则:
.. code-block:: text
g[k] = b[k + 1] XOR b[k]
每个 Gray 位记录相邻两层二进制位是否不同,这正是镜像反射在各层产生的翻转关系。
相邻一位差
~~~~~~~~~~
从 ``i`` 增加到 ``i+1`` 时,二进制会把末尾连续的 1 变为 0,并把它们上方第一个 0 变为 1。
因此 ``i XOR (i+1)`` 是一段连续的低位 1。
Gray 公式还会把该差异右移一位再异或,连续低位 1 中除最高位外都两两抵消,最终只剩一个置位。
所以:
.. code-block:: text
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)``。闭式方法除返回结果外只使用常量额外空间,达到输出规模决定的下界。