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

2024-10-24
福建
本文字数：1242 字
阅读完需：约 4 分钟

原题链接：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 | 00 | 1 | 11 | 0 | 11 | 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}