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

[chencl1986]

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

解题思路：

1. 该题要求返回格雷编码序列，我们并不需要思考编码的生成方法，只要实现百科中提供的思路即可
2. 假设我们已经知道了n - 1的序列，那么n位的序列就等于已有的n - 1序列，再加上逆序书写的n - 1序列，在逆序数列的前面加上1即可。
3. 举个例子：
   • 在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]
4. 如何实现拼接前缀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
}