LeetCode题解：1238. 循环码排列，归纳法，详细注释

原题链接：
https://leetcode.cn/problems/circular-permutation-in-binary-representation/

前置条件：

1. 在解题之前，请先一定要阅读89.格雷编码的题解
2. 格雷编码可以满足题目的条件“p[i] 和 p[i+1] 的二进制表示形式只有一位不同”，以及“p[0] 和 p[2^n -1] 的二进制表示形式也只有一位不同”
3. 我们需要将格雷编码转换成以start开头的一串编码即可
4. 为何要用异或：
   • 格雷编码的第一个是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

解法一：两次循环：

1. 按照89.格雷编码的方法求出格雷编码
2. 将格雷编码的每一位都按位异或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
}

解法二：

1. 可以在解法一的基础上，将第二步的异或操作，放到第一步的第二层循环中，具体方法如下：
   • 每次查找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
}