“This is the 22nd day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

describe

Given 2 integers 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:

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 Permutation is,1,0,2 [3]Copy the code

Example 2:

Input: n = 3, start = 2 Output: [2,6,7,5,4,0,1,3] Explanation: The binary representation of The permutation is (010110111101100000001011).Copy the code

Note:

1 <= n <= 16
0 <= start < 2 ^ n
Copy the code

parsing

Given two integers n and start And they want to return 0, 1, 2….. , 2^ n-1) such that:

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

This question actually gives the generation rule of Grey code, which can be directly solved by using the rule of Grey Code. The generation formula of Grey Code is I ^(I >>1), the integer sequence list result is generated, and then the location index IDX of start is found. Result [idx:] + result[:idx]

answer

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]  


        	      
		
Copy the code

The results

Runtime: 196 ms, Linked links in the linked node. Memory Usage: Submissions in Python online submissions for Circular Permutation in Binary RepresentationCopy the code

parsing

The above method is more clever, if we know the formula, we can solve the problem directly, and we can also find rules to solve the problem. For example, in example 2, we can generate a sequence from 0:

000 is initialized to 0, 001 if you change the rightmost 0 of 000 to 1 you get 001. 011 if you change the rightmost 1 of 001 to 0 you get 000 already used, So you have to change the middle 0 to 1 to get 011, 010 to get 0 to get 010, 110 to get 0 to get 1 to get 011 we've already used it, we have to change the middle 1 to 0 to get 000 we've already used it, You can only change the leftmost 0 to 1 to get 110, 111 you can change the rightmost 0 of 110 to 1 to get 111, 101 you can change the rightmost 1 of 111 to 0 to get 110 and I've already used that, If YOU take the 1 in the middle and you turn it into 0 you get 101, 100 if you turn the 1 on the far right of 101 into 0 you get 100Copy the code

The rule can already be seen, that is, starting from n 0’s, 0’s and 1’s are interrotated from right to left, as long as there is no sequence before, they are retained, and then the basic sequence, and then the operation of 0’s and 1’s interrotated from right to left, until 2^n sequence list result is obtained. Idx = result[idx:]+result[:idx] = result[:idx]

But I’m running out of time, and that’s a lot of work for 2**n numbers. And generally involving the binary problem bit operation efficiency is greatly improved.

answer

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'
Copy the code

The results

Time Limit Exceeded
Copy the code

Original link: leetcode.com/problems/ci…

Your support is my biggest motivation