# 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
示例2:
输入: 0
输出: [0]
解释: 我们定义格雷编码序列必须以 0 开头。
给定编码总位数为 n 的格雷编码序列，其长度为 2n。当 n = 0 时，长度为 20 = 1。
因此，当 n = 0 时，其格雷编码序列为 [0]。
1
2
3
4
5
2
3
4
5
# 思路
找出镜像对称规律
输入：1 输入：2 输入：3
结果：0 结果：00 结果：000
1 01 001
11 011
10 010
110
111
101
100
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
可以发现一个规律就是当n为几，格雷编码就是先几个0开头，然后再几个1开头；然后0后面跟的数字就是n-1时候的格雷编码，1跟着的就是与n-1对称的。。。
# 代码
# 自己的代码
/**
* @param {number} n
* @return {number[]}
*/
var grayCode = function(n) {
let map = new Map()
let endResult = []
map.set(1,['0','1'])
if(n === 1) {
return map.get(1)
} else if(n === 0){
return [0]
} else {
for(let j = 2;j<= n;j++){
let result = []
let max = Math.pow(2,j) - 1
let newArr = map.get(j-1)
let lh = newArr.length
for(let i = 0;i<lh;i++) {
result[i] = `0${newArr[i]}`
result[max - i] = `1${newArr[i]}`
}
map.set(j, result)
}
let testArr = map.get(n)
for(let z in testArr) {
endResult.push(parseInt(testArr[z], 2))
}
return endResult
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 递归解法
/**
* @param {number} n
* @return {number[]}
*/
var grayCode = function(n) {
let make = (n) => {
if (n === 0) return ['0']
if (n === 1) return ['0', '1']
let prev = make(n - 1)
let result = []
let maxIndex = Math.pow(2, n) - 1
for (let i = 0, len = prev.length; i < len; i++) {
result[i] = `0${prev[i]}`
result[maxIndex - i] = `1${prev[i]}`
}
return result
}
return make(n).map(item => parseInt(item, 2))
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 位运算
/**
* @param {number} n
* @return {number[]}
*/
var grayCode = function(n) {
let ans = [];
let head = 1;
ans.push(0);
for(let i = 0; i < n;i ++) {
let len = ans.length - 1;
for(let j = len; j >=0; j--) {
ans.push(head + ans[j])
}
// 位运算: b1等于b1乘以2的1次方
head <<=1;
}
return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18