河西网站建设公司,自在源码网,扬州网站商城建设价格表,广西河池住房和城乡建设厅网站原题链接#xff1a; https://leetcode.cn/problems/circular-permutation-in-binary-representation/
前置条件#xff1a;
在解题之前#xff0c;请先一定要阅读89.格雷编码的题解格雷编码可以满足题目的条件“p[i] 和 p[i1] 的二进制表示形式只有一位不同”#xff0c…原题链接 https://leetcode.cn/problems/circular-permutation-in-binary-representation/
前置条件
在解题之前请先一定要阅读89.格雷编码的题解格雷编码可以满足题目的条件“p[i] 和 p[i1] 的二进制表示形式只有一位不同”以及“p[0] 和 p[2^n -1] 的二进制表示形式也只有一位不同”我们需要将格雷编码转换成以start开头的一串编码即可为何要用异或 格雷编码的第一个是0可以得知0 ^ start start回顾一下异或操作可以知道如果对每一位都进行异或操作每一位之间的逻辑关系的变化是同步的也就是说p[i]和p[i1]的相互关系以及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
}
