数据结构与算法LeetCode-格雷编码No89

jiezi

6 年前

LeetCode 89. 格雷编码

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数 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]。

这题的难度主要是将给定的 n 转化为格雷编码

第一步将 n 转变为格雷编码1=>['0','1']

分析上面的数字排列我们可以注意到 3 点

以 -- 为间隔上面的编码与下面的编码是轴对称的（除了第一位以外）
后一个格雷编码是以上一个为基础做轴对称生成，并且前一半编码每项'0'+'xxx', 后一半编码每项'1'+'xxx',
每组的编码的长度为 2^n

先实现这部分逻辑

let make = (n) => {if (n === 1) {return ['0', '1']
 } else {let pre = make(n - 1)// 获取上次的格雷编码
   let result = [] // 存放结果
   let max = Math.pow(2, n) - 1// 当前 n 个最后一位的索引
   for (let i = 0, len = pre.length; i < len; i++) {result[i] = `0${pre[i]}`
     result[max - i] = `1${pre[i]}`
   }
   return result
 }
}

完整解题

let make = (n) => {if (n === 1) {return ['0', '1']
 } else {let pre = make(n - 1)// 获取上次的格雷编码
   let result = [] // 存放结果
   let max = Math.pow(2, n) - 1// 当前 n 个最后一位的索引
   for (let i = 0, len = pre.length; i < len; i++) {result[i] = `0${pre[i]}`
     result[max - i] = `1${pre[i]}`
   }
   return result
 }
}
let grayCode = (n) => {if (n === 0) return [0]

 let arr = make(n)
 return arr.map(item => {return parseInt(item, 2)  //parseInt(item,10)默认以十进制来换算
 })

};

将二进制转十进制 parseInt

parseInt(string, radix)  String -> Number
console.log(parseInt('11', 2));// 返回一个数字 radix 默认 10 按照十进制解析 如果字符串的第一个字符不能转为数字 将返回 NaN

提到这个parseInt 就要提 toString

let num = 100;
NumberObject.toString(radix); Number -> String
console.log(num.toString(2));// 返回一个字符串 radix 默认 10 按照十进制解析
"1100100"

最快的范例

他的思路其实也差不多只是不采用递归的形式比较直接以1=>['0', '1'] 为基础生成目标格雷编码

var grayCode = function (n) {//n=2
  if (n === 0) return [0]

  const nums = ['0', '1']
  const arr_splice = Array.prototype.splice
  for (let t = 2; t <= n; t++) {let args = nums.slice().reverse()//['1','0']
    args.forEach((s, i) => args[i] = '1' + s)//['11','10']
    args.unshift(0)//['0',11','10']
    args.unshift(nums.length)//['2','0',11','10']
    console.log(args)
    nums.forEach((s, i) => nums[i] = '0' + s)// ['00', '01']
    arr_splice.apply(nums, args)// nums=> ['00', '01', '11', '10']
  }
  return nums.map(binary => parseInt(binary, 2))
};

上面最关键步骤

const arr_splice = Array.prototype.splice
...
args.unshift(0)//['0',11','10']
args.unshift(nums.length)//['2','0',11','10']
...
arr_splice.apply(nums, args)// nums=> ['00', '01', '11', '10']


['00', '01']+['11','10'] => ['00', '01', '11', '10']
由于 splice 接受的是参数列表 arr.splice(2,0,'00','01') 不接受数组
所以巧妙的采用 apply，因为 apply 自身就是可以将集合的形式转变为参数列表的形式
这也是 call 与 apply 的区别之一

如果喜欢 LeetCode 或者更多数据结构的内容，可以戳这里, 欢迎 star

数据结构与算法 -LeetCode 种花问题(No.605)
LeetCode- 电话号码的字母组合(No.17) 递归 +hash
JavaScript 数据结构与算法这题你会吗？

LeetCode 89. 格雷编码

往期文章