Skip to main content

格雷编码

Tips

题目类型: Bit Manipulation

题目​

n 位格雷码序列是一个由 2ⁿ 个整数组成的序列, 其中:

  • 每个整数都在范围 [0, 2ⁿ - 1] 内(含 0 和 2ⁿ - 1)
  • 第一个整数是 0
  • 一个整数在序列中出现不超过一次
  • 每对相邻整数的二进制表示恰好一位不同, 且第一个和最后一个整数的二进制表示恰好一位不同

给你一个整数 n, 返回任一有效的 n 位格雷码序列.

提示:
  • 1 <= n <= 16
示例
输入: n = 2
输出: [0, 1, 3, 2]
解释:
[0, 1, 3, 2] 的二进制表示是 [00, 01, 11, 10].
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0, 2, 3, 1] 也是一个有效的格雷码序列, 其二进制表示是 [00, 10, 11, 01].
- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同
输入: n = 1
输出: [0, 1]

题解​

/**
 * @param {number} n
 * @return {number[]}
 */
var grayCode = function (n) {
  const res = [0]

  for (let i = 1; i <= n; i++) {
    const m = res.length

    for (let j = m - 1; j >= 0; j--) {
      res.push(res[j] | (1 << (i - 1)))
    }
  }

  return res
}