1. 首页

LeetCode 089. 格雷编码

题目描述:

难度:Middle

相关话题:回溯算法

格雷编码是一个二进制数字系统,在该系统中,两个连续的数值仅有一个位数的差异。

给定一个代表编码总位数的非负整数n ,打印其格雷编码序列。格雷编码序列必须以 0 开头。

示例 1:

输入:2
输出:[0,1,3,2]
解释:
00 - 0
01 - 1
11 - 3
10 - 2

对于给定的n,其格雷编码序列并不唯一。
例如,[0,2,3,1]也是一个有效的格雷编码序列。

00 - 0
10 - 2
11 - 3
01 - 1

示例2:

输入:0
输出:[0]
解释: 我们定义格雷编码序列必须以 0 开头。
    给定编码总位数为 n 的格雷编码序列,其长度为 2n。当 n = 0 时,长度为 20 = 1。
    因此,当 n = 0 时,其格雷编码序列为 [0]。

思路:

2种思路,一种是回溯,定义一个初始状态00000...(n个0)。

对这个数字每一位都尝试翻转(0变1,1变0),并且用hash保存,检查以避免重复。

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
 * @param {number} n
 * @return {number[]}
 */
var grayCode = function(n) {
  if(n===0)return [0]
  let cache={}, str="0".repeat(n)
  let result=[str]
  cache[str]=1
  function checkNoExist(str){
    if(cache[str])return false
    cache[str]=1
    return true
  }
  function backtrack(str){
    for(let i=0;i<n;i++){
      let curIdx=str[i]==="0"?"1":"0"
      let newStr=str.substring(0,i)+curIdx+str.substring(i+1,n)
      if(checkNoExist(newStr)){
        result.push(newStr)
        return backtrack(newStr)
      }
    }
  }
  backtrack(str)
  return result.map(n=>parseInt(n,2))
};

另一种方法是找出规律,我们要计算n的格雷编码,先计算出n-1的格雷编码,然后对于n-1,正序遍历头部添加0,再逆序遍历头部添加1

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
 * @param {number} n
 * @return {number[]}
 */
var grayCode = function(n) {
  // 找规律,"0"+(n-1正序遍历每一个值),"1"+(n-1倒序遍历每一个值)
  function compute(n){
    if(n===1)return [0,1]
    let arr=compute(n-1)
    let newArr=[]
    for(let i=0;i<arr.length;i++){
      newArr.push("0"+arr[i])
    }
    for(let i=arr.length-1;i>=0;i--){
      newArr.push("1"+arr[i])
    }
    return newArr
  }
  if(n===0)return [0]
  return compute(n).map(n=>parseInt(n,2))
};

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 089. 格雷编码

链接:https://www.javascriptc.com/4449.html

« LeetCode 090. 子集 II
从源码解读Vue生命周期,让面试官对你刮目相看»
Flutter 中文教程资源

相关推荐

QR code