LeetCode 题解：89. 格雷编码，归纳法，详细注释

2024-10-24
福建
本文字数：595 字
阅读完需：约 2 分钟

原题链接：https://leetcode.cn/problems/gray-code/

解题思路：

该题要求返回格雷编码序列，我们并不需要思考编码的生成方法，只要实现百科中提供的思路即可
假设我们已经知道了n - 1的序列，那么n位的序列就等于已有的n - 1序列，再加上逆序书写的n - 1序列，在逆序数列的前面加上 1 即可。
举个例子：
在n = 3时，n - 1即 2 位的序列为[00, 01, 11, 10]
3 位序列就等于 2 位的序列[00, 01, 11, 10]前面加前缀0，得到[000, 001, 011, 010]
再依次拼接上：
10加前缀 1，得到110
11加前缀 1，得到111
01加前缀 1，得到101
00加前缀 1，得到100
最后的结果为[000, 001, 011, 010, 110, 111, 101, 100]
如何实现拼接前缀 1，以10为例：
先将1向左移动 2 位，得到100
将10与100进行“或”位运算，即10 | 100 = 110

/** * @param {number} n * @return {number[]} */var grayCode = function (n) {  let result = [0] // 存储结果，第一个整数位0
  // 一共计算n位格雷码序列，需要循环n位  for (let i = 0; i < n; i++) {    // 每次计算时，已有的序列不变    // 只需要计算已有序列的逆序列，每个再加前缀1    // 需要缓存已有序列的长度，用于计算下一段序列    const len = result.length
    // 由于是逆序计算，因此要从len - 1开始加前缀    for (let j = len - 1; j >= 0; j--) {      // 加前缀1后，把新值存入结果      result.push(result[j] | (1 << i))    }  }
  return result}