89. 格雷编码
题目描述
输入整数 n，构造一个长度为 2^n 的整数序列，即 n 位格雷码。
序列要求：每个数都在 0 到 2^n - 1 之间；第一个数是 0；每个数至多出现一次；任意相邻两个数的二进制恰好只有一位不同；最后一个数和第一个数的二进制也恰好只差一位。
满足要求的序列可能有多个，返回任意一个即可。
示例 1
输入：n = 2 输出：[0,1,3,2]
解释：二进制为 00,01,11,10，相邻及首尾都只差一位；[0,2,3,1] 也是合法答案。
示例 2
输入：n = 1 输出：[0,1]
数据范围
1 <= n <= 16
解题思路：对称构造（镜像反射法）
镜像构造：已有 i 位的格雷码 res，把它倒过来拼在后面，并给后半段每个数加上第 i 位（1<<i）。前半段内部、后半段内部相邻仍只差一位；接缝处是同一个数加不加第 i 位，也只差一位；首尾一个是 0，一个是 1<<i，同样只差一位。
为什么正确
外层循环第 i 轮开始时，res 是长度 2^i 的合法 i 位格雷码（含首尾相邻）。
复杂度分析
时间 O(2^n)，空间 O(1)（不计输出）。
易错点
内层必须倒序遍历，而且要先固定起点 len(res)-1；如果顺序遍历，接缝处会变两位以上。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def grayCode(self, n: int) -> List[int]:
res = [0]
for i in range(n):
for j in range(len(res) - 1, -1, -1):
res.append(res[j] | (1 << i))
return resclass Solution {
public List<Integer> grayCode(int n) {
List<Integer> res = new ArrayList<>();
res.add(0);
for (int i = 0; i < n; i++) {
for (int j = res.size() - 1; j >= 0; j--) {
res.add(res.get(j) | (1 << i));
}
}
return res;
}
}class Solution {
public:
vector<int> grayCode(int n) {
vector<int> res = {0};
for (int i = 0; i < n; i++) {
for (int j = (int)res.size() - 1; j >= 0; j--) {
res.push_back(res[j] | (1 << i));
}
}
return res;
}
};func grayCode(n int) []int {
res := []int{0}
for i := 0; i < n; i++ {
for j := len(res) - 1; j >= 0; j-- {
res = append(res, res[j]|(1<<i))
}
}
return res
}var grayCode = function(n) {
const res = [0];
for (let i = 0; i < n; i++) {
for (let j = res.length - 1; j >= 0; j--) {
res.push(res[j] | (1 << i));
}
}
return res;
};function grayCode(n: number): number[] {
const res: number[] = [0];
for (let i = 0; i < n; i++) {
for (let j = res.length - 1; j >= 0; j--) {
res.push(res[j] | (1 << i));
}
}
return res;
}其他解法
镜像反射法由 n-1 位格雷码递推出 n 位，正确性一目了然；公式法 i ^ (i >> 1) 更短，还能单独求任一项，两者复杂度相同。
解法 2：二进制数转格雷码 时间 O(2ⁿ)，空间 O(1)
格雷码有一个闭式公式：第 i 个格雷码等于 i 异或 (i 右移一位)，即 g(i) = i ^ (i >> 1)。相邻的 i 和 i+1 只在末尾的一串位上不同，经过这次异或后，恰好只剩一位不同。按 i = 0, 1, …, 2ⁿ-1 依次套公式就得到答案。
代码只有一行，且可以直接算出任意第 i 项，不依赖前面的项。缺点是需要记住或推导公式，不如镜像构造那样能从定义直接想到。
from typing import List
class Solution:
def grayCode(self, n: int) -> List[int]:
return [i ^ (i >> 1) for i in range(1 << n)]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;
}
}class Solution {
public:
vector<int> grayCode(int n) {
vector<int> res(1 << n);
for (int i = 0; i < (1 << n); i++) res[i] = i ^ (i >> 1);
return res;
}
};func grayCode(n int) []int {
res := make([]int, 1<<n)
for i := range res {
res[i] = i ^ (i >> 1)
}
return res
}var grayCode = function(n) {
const res = [];
for (let i = 0; i < (1 << n); i++) res.push(i ^ (i >> 1));
return res;
};function grayCode(n: number): number[] {
const res: number[] = [];
for (let i = 0; i < (1 << n); i++) res.push(i ^ (i >> 1));
return res;
}