leetcode 1238. Circular Permutation in Binary Representation(python)

語言: CN / TW / HK

「這是我參與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

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

您的支援是我最大的動力