leetcode 1238. Circular Permutation in Binary Representation（python）_王大呀呀

「這是我參與11月更文挑戰的第22天，活動詳情檢視：2021最後一次更文挑戰」

描述

Given 2 integers n and start. Your task is return any permutation p of (0,1,2.....,2^n -1) such that :

p[0] = start
p[i] and p[i+1] differ by only one bit in their binary representation.
p[0] and p[2^n -1] must also differ by only one bit in their binary representation.

Example 1:

Input: n = 2, start = 3
Output: [3,2,0,1]
Explanation: The binary representation of the permutation is (11,10,00,01). 
All the adjacent element differ by one bit. Another valid permutation is [3,1,0,2]

Example 2:

Input: n = 3, start = 2
Output: [2,6,7,5,4,0,1,3]
Explanation: The binary representation of the permutation is (010,110,111,101,100,000,001,011).

Note:

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

解析

根據題意，給定 2 個整數 n 和 start 。題目要求是返回 ( 0 , 1 , 2 ..... , 2^n -1 ) 的任何排列 p 使得：

p[0] = start
p[i] 和 p[i+1] 在二進位制表示中僅相差一位
p[0] 和 p[2^n -1] 在其二進位制表示中也必須僅相差一位

這道題其實就是給出了 grey code 的生成規則，可以使用 grey code 的規則直接來解題，grey code 的生成公式 i^(i>>1) ，生成整數序列列表 result ，然後找到 start 的位置索引 idx ，將 result[idx:] + result[:idx] 即可實現題目要求，返回答案即可。

解答

class Solution(object):
    def circularPermutation(self, n, start):
        """
        :type n: int
        :type start: int
        :rtype: List[int]
        """
        result = []
        for i in range(1 << n):
            result.append(i ^ (i >> 1))
        idx = result.index(start)
        return result[idx:] + result[:idx]

執行結果

Runtime: 196 ms, faster than 76.92% of Python online submissions for Circular Permutation in Binary Representation.
Memory Usage: 23.1 MB, less than 46.15% of Python online submissions for Circular Permutation in Binary Representation.

解析

上面的方法比較取巧，知道公式的話直接就能解題，另外我們還能找規律解題。如例子二，我們可以從 0 還是生成符合題意的序列：

000 初始化都為 0
001 將 000 中最右邊 0 變為 1 得到 001
011 將 001 最右邊 1 變為 0 得到 000 已經用過，所以只能變中間的 0 為 1 得到 011
010 將 011 最右邊 1 變為 0 得到 010
110 將 010 最右邊 0 變為 1 得到 011 已經用過，將中間的 1 變為 0 得到 000 已經用過，只能將最左邊的 0 變為 1 得到 110
111 將 110 最右邊的 0 變為 1 得到 111
101 將 111 最右邊的 1 變為 0 得到 110 已經用過，將中間的 1 變為 0 得到 101
100 將 101 最右邊的 1 變為 0 得到 100

規律已經能看出來了，那就是從 n 個 0 開始，從右往左依次將 0 和 1 互轉，只要出現之前沒有的序列就將其保留，並依次為基礎序列，再從右往左依次進行 0 和 1 互轉的操作，直到得到了 2^n 個序列列表 result 為止。這些序列肯定是滿足題意要求的，然後再找到 start 開始的索引 idx ，將 result 變為 result[idx:]+result[:idx] 即可。

但是結果超時了，這種一個個找結果的方式對 2**n 個數來說計算量太大了。而且一般涉及到二進位制的題用位運算效率為極大提升。

解答

class Solution(object):
    def circularPermutation(self, n, start):
        """
        :type n: int
        :type start: int
        :rtype: List[int]
        """
        result = []
        L = ['0'] * n
        while len(result) < 2**n:
            if int(''.join(L), 2) not in result:
                result.append(int(''.join(L), 2))
            for i in range(n-1, -1, -1):
                self.swap(L, i)
                if int(''.join(L), 2) not in result:
                    break
                self.swap(L, i)
        idx = result.index(start)
        return result[idx:]+result[:idx]

    def swap(self, L,i):
        if L[i] == '1':
            L[i] = '0'
        else:
            L[i] = '1'

執行結果

Time Limit Exceeded

原題連結：http://leetcode.com/problems/circular-permutation-in-binary-representation/

您的支援是我最大的動力