原文:89. 格雷编码(leetcode 解题) - 每天一个JavaScript小知识@Js中文网 · 码农进阶题库

原文地址:https://www.javascriptc.com/interview-tips/zh_cn/leetcode/leetcode-javascript-solution-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))
};