美文网首页JavaScript
LeetCode题解:89.格雷编码,归纳法,详细注释

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

作者: Lee_Chen | 来源:发表于2023-02-22 17:03 被阅读0次

原题链接:
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
    • 10100进行“或”位运算,即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
}

相关文章

  • 91. 解码方法/89. 格雷编码/78. 子集/5 N进制小数

    91. 解码方法 89. 格雷编码 78. 子集 5 N进制小数

  • Leetcode 89. 格雷编码(回溯算法)

    问题描述 格雷编码是一个二进制数字系统,在该系统中,两个连续的数值仅有一个位数的差异。给定一个代表编码总位数的非负...

  • LeetCode 力扣 89. 格雷编码

    题目描述(中等难度) 生成 n 位格雷码,所谓格雷码,就是连续的两个数字,只有一个 bit 位不同。 解法一 动态...

  • 89. 格雷编码

    leetcode 其他的思路:

  • 89. 格雷编码

    题目描述 格雷编码是一个二进制数字系统,在该系统中,两个连续的数值仅有一个位数的差异。 给定一个代表编码总位数的非...

  • 89.格雷编码

    题目格雷编码是一个二进制数字系统,在该系统中,两个连续的数值仅有一个位数的差异。 给定一个代表编码总位数的非负整数...

  • 89. 格雷编码

    格雷编码是一个二进制数字系统,在该系统中,两个连续的数值仅有一个位数的差异。 给定一个代表编码总位数的非负整数 n...

  • 89. 格雷编码

    这个题其实有个小技巧(个人一直觉得这种所谓的“技巧”其实并不能真正提高编程能力),就是编码的规律。什么规律呢?通过...

  • python实现leetcode之89. 格雷编码

    解题思路 答案分为两部分第一部分最高位为0,其他每个相邻的数字一位不同第二部分最高位为1,其他每个相邻的数字一位不...

  • 89. 格雷编码(medium)

    格雷编码是一个二进制数字系统,在该系统中,两个连续的数值仅有一个位数的差异。给定一个代表编码总位数的非负整数 n,...

网友评论

    本文标题:LeetCode题解:89.格雷编码,归纳法,详细注释

    本文链接:https://www.haomeiwen.com/subject/wuvakdtx.html