美文网首页JavaScript
LeetCode题解:1238. 循环码排列,归纳法,详细注释

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

作者: Lee_Chen | 来源:发表于2023-02-26 17:37 被阅读0次

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

    相关文章

      网友评论

        本文标题:LeetCode题解:1238. 循环码排列,归纳法,详细注释

        本文链接:https://www.haomeiwen.com/subject/fwjcldtx.html