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

[chencl1986]

原题链接：
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
}