leetcode
leetcode 1151 ~ 1200
循环码排列

循环码排列

难度:

标签:

题目描述

代码结果

运行时间: 108 ms, 内存: 25.1 MB


/*
 * The task is to generate a Gray code sequence of length 2^n where the first element is 'start'.
 * The solution here uses Java Streams to generate the sequence efficiently.
 */

import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.List;

public class Solution {
    public List<Integer> circularPermutation(int n, int start) {
        return IntStream.range(0, 1 << n)
                .map(i -> start ^ (i ^ (i >> 1)))
                .boxed()
                .collect(Collectors.toList());
    }
}

解释

方法:

这个题解使用了格雷码(Gray code)的性质来构造循环码排列。格雷码是一种二进制数系统,其中两个连续的数只有一位二进制位不同。首先,构造长度为 2^n 的格雷码序列。然后,找到序列中值为 start 的元素,并将这个序列从这个元素开始重新排列,使得首元素为 start。这样就得到了符合条件的循环码排列。

时间复杂度:

O(2^n)

空间复杂度:

O(2^n)

代码细节讲解

🦆
题解中提到使用格雷码来构造序列,能否解释一下什么是格雷码,以及它如何保证每两个连续的数只有一位二进制位不同?
格雷码(Gray code)是一种二进制编码方式,其中任意两个连续的数在二进制形式下只有一位不同。这种编码的设计使得每次转换只涉及到一个二进制位的改变,减少了错误和复杂性。它在硬件设计中特别有用,因为在多位同时改变时可能引起错误的风险更高。格雷码的构造可以通过递归方法实现。基本的构造方法是:先取一个较小的格雷码序列,然后创建一个新序列,它是原序列的反向并在每个数前加上一个高位的1。这样确保了新生成的序列的前半部分和后半部分只在新加的最高位上有差异,而在拼接点处的两个数(前半部分的最后一个数和后半部分的第一个数)也保证只有一位不同。
🦆
题解中使用的方法是将格雷码序列分成两部分后重新组合,这种分割和重组的步骤是如何保证结果序列的循环性质的?
题解中的方法通过首先生成一个完整的格雷码序列,然后找到序列中的某个特定起始值'start',并以此值为起点重新排列格雷码序列,从而生成一个循环序列。具体来说,从'start'开始的元素到序列末尾的元素先被取出,然后将序列开始到'start'之前的元素接在后面。这种重组方法利用了格雷码本身连续元素只改变一位的特性,保证了即使在新序列的末尾到开头的过渡也仅涉及一位的变化,从而维持了循环序列的连续性和一致性。
🦆
在构造格雷码时,通过反向遍历前一半的格雷码并加上2^(i-1),这一操作的目的是什么,它是如何确保新生成的数字依旧满足格雷码的性质的?
在格雷码的构造过程中,反向遍历前一半的格雷码并在每个数前加上2^(i-1)(即添加一个更高位的1),这一步骤的目的是生成一组新的数,它们与原来的序列在新的最高位上有所区别,从而实现长度翻倍的新格雷码序列。这样做的关键在于,反向遍历保证了新添加的部分(后半部分)的第一个元素与原序列(前半部分)的最后一个元素只在新加的这一位上有差异,确保了格雷码的连续性。此外,由于原序列已经满足格雷码的条件,反向遍历并添加相同的高位不会破坏原有序列内部的每两个连续数字只改变一位的性质。

相关问题