原题链接:
https://leetcode.cn/problems/circular-permutation-in-binary-representation/
前置条件:
- 在解题之前,请先一定要阅读89.格雷编码的题解
- 格雷编码可以满足题目的条件“
p[i]
和p[i+1]
的二进制表示形式只有一位不同”,以及“p[0]
和p[2^n -1]
的二进制表示形式也只有一位不同” - 我们需要将格雷编码转换成以
start
开头的一串编码即可 - 为何要用异或:
- 格雷编码的第一个是
0
,可以得知0 ^ start = start
- 回顾一下异或操作,可以知道如果对每一位都进行异或操作,每一位之间的逻辑关系的变化是同步的
- 也就是说,
p[i]
和p[i+1]
的相互关系,以及p[0]
和p[2^n -1]
的相互关系不会改变
a | b | a XOR b
---|---|---------
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
- 格雷编码的第一个是
解法一:两次循环:
- 按照89.格雷编码的方法求出格雷编码
- 将格雷编码的每一位都按位异或
start
,即可求得结果
/**
* @param {number} n
* @param {number} start
* @return {number[]}
*/
var circularPermutation = function (n, start) {
/*
* 第一步,先求格雷编码
*/
let result = [0] // 存储结果,第一个整数为0
// 一共计算n位格雷码序列,需要循环n次
for (let i = 0; i < n; i++) {
// 每次计算时,已有的序列不变
// 只需要计算已有序列的逆序列,每个再加前缀1
// 需要缓存已有序列的长度,用于计算下一段序列
const len = result.length
// 由于是逆序计算,因此要从len - 1开始加前缀
for (let j = len - 1; j >= 0; j--) {
// 加前缀1后,把新值存入结果
result.push(result[j] | (1 << i))
}
}
/*
* 第二步,将格雷编码的每一项都按位异或start
*/
for (let i = 0; i < result.length; i++) {
result[i] ^= start
}
return result
}
解法二:
- 可以在解法一的基础上,将第二步的异或操作,放到第一步的第二层循环中,具体方法如下:
- 每次查找
result
中的元素时,将其异或start
,将其转为格雷编码 - 给格雷编码加上前缀
1
- 存入
result
时,将其异或start
,转为以start
开头的编码
- 每次查找
/**
* @param {number} n
* @param {number} start
* @return {number[]}
*/
var circularPermutation = function (n, start) {
let result = [start] // // 存储结果,第一个整数为start
// 一共计算n位编码,需要循环n次
for (let i = 0; i < n; i++) {
// 每次计算时,已有的序列不变
// 只需要计算已有序列的逆序列,每个再加前缀1
// 需要缓存已有序列的长度,用于计算下一段序列
const len = result.length
// 由于是逆序计算,因此要从len - 1开始加前缀
for (let j = len - 1; j >= 0; j--) {
// 加前缀1后,把新值存入结果
result.push(
// 将编码异或start,转为格雷编码
((result[j] ^ start) |
// 为格雷编码加上前缀1
(1 << i)) ^
// 将格雷编码异或start,转为以start开头的编码
start
)
}
}
return result
}
网友评论