题目:
难度: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))
};