current position:Home>leetcode 1611. Minimum One Bit Operations to Make Integers Zero(python)

leetcode 1611. Minimum One Bit Operations to Make Integers Zero(python)

2022-02-01 09:06:40 Wang Daya

「 This is my participation 11 The fourth of the yuegengwen challenge 25 God , Check out the activity details :2021 One last more challenge

describe

Given an integer n, you must transform it into 0 using the following operations any number of times:

  • Change the rightmost (0th) bit in the binary representation of n.
  • Change the ith bit in the binary representation of n if the (i-1)th bit is set to 1 and the (i-2)th through 0th bits are set to 0.

Return the minimum number of operations to transform n into 0.

Example 1:

Input: n = 0
Output: 0
 Copy code 

Example 2:

Input: n = 3
Output: 2
Explanation: The binary representation of 3 is "11".
"11" -> "01" with the 2nd operation since the 0th bit is 1.
"01" -> "00" with the 1st operation.
 Copy code 

Example 3:

Input: n = 6
Output: 4
Explanation: The binary representation of 6 is "110".
"110" -> "010" with the 2nd operation since the 1st bit is 1 and 0th through 0th bits are 0.
"010" -> "011" with the 1st operation.
"011" -> "001" with the 2nd operation since the 0th bit is 1.
"001" -> "000" with the 1st operation.
 Copy code 

Example 4:

Input: n = 9
Output: 14
 Copy code 

Example 5:

Input: n = 333
Output: 393
 Copy code 

Note:

0 <= n <= 109
 Copy code 

analysis

According to the meaning , Given an integer n, It must be converted to... Using any number of the following operations 0:

  • change n The binary of represents the rightmost bit . Sure 0 Turn into 1 , It's fine too 1 Turn into 0 .
  • If the first (i-1) Bit is set to 1 And No (i-2) To the first 0 Bit is set to 0, Then change n In the binary representation of i position . Sure 0 Turn into 1 , It's fine too 1 Turn into 0 .

Note that the index of binary bits in the title is from right to left , Return to n Convert to 0 Minimum operands of . Because method one just puts the rightmost 0 and 1 swap , Cannot operate on previous characters , So the key is to skillfully use method 2 to change , If we give an example , take 101011 Turn into 000000 , The simplest idea is recursion :

  • (1)101011 The first is 1 , Want to turn it into 100000 , Just call the custom convert function , The function of this function is to find out that 01011 Turn into 10000 The minimum number of times
  • (2) Application method 2 will change the 110000 Turn into 010000 the 1 operations , Then the calculation will 10000 Turn into 00000 The number of times , The same method as above , take 0000 adopt convert The function becomes 1000 , Doing the same thing , Until it finally becomes 000000
  • (3) So define recursive functions dfs , Indicates the minimum number of operations on the input binary , To express the above process is dfs(101011) = convert(01011) + 1 + dfs(10000)

however convert There are two situations :

  • The first case is that the first number of binary is 1 , Such as 1110 . Then call directly dfs(110) that will do
  • The second case is that the first number of binary is 0 , Such as 0111 , Recursion is needed again :convert(0111) = convert(111) + 1 + dfs(100)

answer

class Solution(object):
    
    def __init__(self):
        self.d = {}
        self.t = {}
        
    def minimumOneBitOperations(self, n):
        """
        :type n: int
        :rtype: int
        """
        return(self.dfs(bin(n)[2:]))
    
    def dfs(self, s):
        if s == '0' : return 0
        if s == '1' : return 1
        if s in self.d : return self.d[s]
        if  s[0] == '0': return self.dfs(s[1:])
        m = s[1:]
        n = list(s[1:])
        n[0] = '1'
        for i in range(1, len(n)):
            n[i] = '0'
        n = ''.join(n)
        self.d[s] = self.convert(m) + 1 + self.dfs(n)
        return self.d[s]
    
    def convert(self, s):
        if s == '0' : return 1
        if s == '1' : return 0
        if s in self.t : return self.t[s]
        if s[0] == '1': 
            self.t[s] = self.dfs(s[1:])
        else:
            m = s[1:]
            n = list(s[1:])
            n[0] = '1'
            for i in range(1, len(n)):
                n[i] = '0'
            n = ''.join(n)
            self.t[s] = self.convert(m) + 1 + self.dfs(n)
        return self.t[s]

        
                    	      
		
 Copy code 

Running results

Runtime: 44 ms, faster than 5.17% of Python online submissions for Minimum One Bit Operations to Make Integers Zero.
Memory Usage: 13.3 MB, less than 77.59% of Python online submissions for Minimum One Bit Operations to Make Integers Zero.
 Copy code 

Original link :leetcode.com/problems/mi…

Your support is my greatest motivation

copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/02/202202010906389669.html

Random recommended