LEETCODE 1238. Circular Permutation in Binary Representation解题思路分析

题目大意：

循环码排列

给你两个整数 n 和 start。你的任务是返回任意 (0,1,2,,...,2^n-1) 的排列 p，并且满足：

• p[0] = start
• p[i] 和 p[i+1] 的二进制表示形式只有一位不同
• p[0] 和 p[2^n -1] 的二进制表示形式也只有一位不同

示例 1：

输入：n = 2, start = 3
输出：[3,2,0,1]
解释：这个排列的二进制表示是 (11,10,00,01)
      所有的相邻元素都有一位是不同的，另一个有效的排列是 [3,1,0,2]

示例 2：

输出：n = 3, start = 2
输出：[2,6,7,5,4,0,1,3]
解释：这个排列的二进制表示是 (010,110,111,101,100,000,001,011)

提示：

• 1 <= n <= 16
• 0 <= start < 2^n

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1238

解题思路分析：

这道题如果不精通二进制的话很难想出思路，题目描述的排列实际上是Gray Code，中文名称为格雷码。当连续的二进制数个数为2的n次方时，这些个二进制数一定可以组成格雷码排序。由于本人对二进制也不是十分精通，看了大神的实现代码及其言简意赅，三两行就解决了这个问题，比较代表性的实现如下：

public List<Integer> circularPermutation(int n, int start) {
    List<Integer> res = new ArrayList<>();
    for (int i = 0; i < 1 << n; ++i)
        res.add(start ^ i ^ i >> 1);
    return res;
}

上面代码的执行效率很高，时间为7ms。但说实话我并没有理解。但这并不妨碍我们寻找其他解法。经过我耐心的观察，终于找到了一个最好理解的实现方式，虽然代码量多于大神的成果，但执行效率毫不逊色，同样为7ms。

对于格雷码的排序，我发现如果使用如下的思路很容易做到。

我们先定义二个数0和1，然后从左至右给2个数字最高位加上一个0，再对称的从右至左给每个数字最高位加上一个1。这时，就形成的4个数。

0, 1
00, 01, 11, 10

如果想再加一组，同样可以：

00, 01, 11, 10
000, 001, 011, 010 // 从左到右在最高位加0
110, 111, 101, 100 // 从右到左在最高位加1

接下来的操作同理。因此，题目给出的n即代表作出几次上述的操作而已。这样我们可以很轻松的得到格雷码方式的排序。不过我们的排序是从0开始，但题目要求从给定的start为起点，这也不难，我们只需要将start前的数移动到后面去就好了。

看下实现代码：

public List<Integer> circularPermutation(int n, int start) {
    int[] res = new int[]{0,1}; // 返回结果。初始只有0和1
    int max = (int)Math.pow(2, n); // 计算出最大值
    int offset=1; // 当前二进制高位
    while(res.length<max){
        int[] temp = new int[res.length*2]; // 新的数组（数量翻倍）
        for(int i=0;i<res.length;i++){
            // 给每个数前加个0
            temp[i] = (res[i] | (0 << offset));
            // 给每个数前加个1，并按照对称顺序放入数组
            temp[temp.length-i-1] = (res[i] | (1 << offset));
        }
        offset++; // 更新最高位
        res = temp; // 更新res
    }
    // 根据start，将start前的数字放到尾部
    List<Integer> list1 = new ArrayList<>();
    List<Integer> list2 = new ArrayList<>();
    boolean isStart = false;
    for(int num : res){
        if(num == start){
            isStart = true;
        }
        if(isStart){
           list1.add(num);
        }else{
           list2.add(num);
        }
    }
    list1.addAll(list2);
    return list1;
}

本题解法执行时间为7ms。

Runtime: 7 ms, faster than 88.61% of Java online submissions for Circular Permutation in Binary Representation.

Memory Usage: 45.3 MB, less than 100.00% of Java online submissions for Circular Permutation in Binary Representation.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1238-circular-permutation-in-binary-representation解题思路分析/