写点什么

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

作者:Lee Chen
  • 2023-02-23
    福建
  • 本文字数:595 字

    阅读完需:约 2 分钟

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

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


解题思路:


  1. 该题要求返回格雷编码序列,我们并不需要思考编码的生成方法,只要实现百科中提供的思路即可

  2. 假设我们已经知道了n - 1的序列,那么n位的序列就等于已有的n - 1序列,再加上逆序书写的n - 1序列,在逆序数列的前面加上 1 即可。

  3. 举个例子:

  4. n = 3时,n - 1即 2 位的序列为[00, 01, 11, 10]

  5. 3 位序列就等于 2 位的序列[00, 01, 11, 10]前面加前缀0,得到[000, 001, 011, 010]

  6. 再依次拼接上:

  7. 10加前缀 1,得到110

  8. 11加前缀 1,得到111

  9. 01加前缀 1,得到101

  10. 00加前缀 1,得到100

  11. 最后的结果为[000, 001, 011, 010, 110, 111, 101, 100]

  12. 如何实现拼接前缀 1, 以10为例:

  13. 先将1向左移动 2 位,得到100

  14. 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}
复制代码


发布于: 刚刚阅读数: 7
用户头像

Lee Chen

关注

还未添加个人签名 2018-08-29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:89.格雷编码,归纳法,详细注释_JavaScript_Lee Chen_InfoQ写作社区