摘要：例如，也是一个有效的格雷编码序列。示例输入输出解释我们定义格雷编码序列必须以开头。给定编码总位数为的格雷编码序列，其长度为。因此，当时，其格雷编码序列为。
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"]
n = 1 0 1 n = 2 00 01 -- 11 10 n = 3 000 001 011 010 --- 110 111 101 100
分析上面的数字排列 我们可以注意到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.89)
数据结构与算法-LeetCode 种花问题(No.605)
LeetCode-电话号码的字母组合(No.17) 递归+hash
JavaScript 数据结构与算法 这题你会吗？
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/109513.html
摘要：电话号码的字母组合给定一个仅包含数字的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下与电话按键相同。注意不对应任何字母。 LeetCode 17. 电话号码的字母组合 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。 注意 1 不对应任何字母。 showImg(https://user-gold-cdn.xit...
摘要：能否在不打破种植规则的情况下种入朵花能则返回，不能则返回。示例输入输出示例输入输出注意数组内已种好的花不会违反种植规则。输入的数组长度范围为。是非负整数，且不会超过输入数组的大小。 LeetCode 605. 种花问题 假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。 给定一个花坛（表示为一个数组包含0和1，...
最近入职的公司主要做微信端的h5，所以在所难免要引用sdk。虽然官方文档写的还算清楚，但是还是有坑。 1.在index.html中 引入微信sdk 2.在assets/js 下新建文件 wx.js export default { wxShowMenu: function (that,sign=) { let url = window.location.href.split(#)[...
摘要：微信小程序图片上传阿里云服务器也折腾了蛮久才解决的，所以特意去记录一下。上传失败第四步源码在这里如果觉得这面文章对你有帮助的话，可给我点个这里，谢谢最后，希望这篇文章对你有所帮助，真真确确是可以在微信小程序中上传图片到阿里云的。 本人今年6月份毕业，最近刚在上海一家小公司实习，做微信小程序开发。最近工作遇到一个小问题。 微信小程序图片上传阿里云服务器Oss也折腾了蛮久才解决的，所以特意...
阅读 2445·2021-09-09 09:33
阅读 2819·2019-08-30 15:56
阅读 3099·2019-08-30 14:21
阅读 869·2019-08-30 13:01
阅读 829·2019-08-26 18:27
阅读 3565·2019-08-26 13:47
阅读 3439·2019-08-26 10:26
阅读 1566·2019-08-23 18:38
