“This is the 25th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

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

Example 4:

Input: n = 9
Output: 14
Copy the code

Example 5:

Input: n = 333
Output: 393
Copy the code

Note:

0 <= n <= 109
Copy the code

parsing

Given an integer n, it must be converted to 0 any number of times:

  • Change the rightmost bit of the binary representation of n. It could be 0 to 1, or 1 to 0.
  • If bit (i-1) is set to 1 and bits (i-2) to 0 are set to 0, change bit I in the binary representation of n. It could be 0 to 1, or 1 to 0.

Note that the binary bits in the problem are indexed from right to left, returning the minimum operand to convert n to 0. Because method 1 only interchanges the rightmost 0 and 1, it is not possible to operate on the preceding character, so the key is to skillfully use method 2 to change, let us example, 101011 to 000000, the simplest idea is recursion:

  • To convert 101011 to 100000, call the custom convert function, which finds the minimum number of times 01011 has been converted to 10000
  • (2) use method 2 to change 110000 to 010000, then calculate 10000 to 00000 times, and the same method as above, convert 0000 to 1000 by convert function, then do the same operation, Until it gets to 000000
  • DFS (101011) = convert(01011) + 1 + DFS (10000)

But there are two cases of convert:

  • The first case is when the first digit of binary is 1, such as 1110. Just call DFS (110)
  • Convert (0111) = convert(111) + 1 + DFS (100) 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 the code

The results

Runtime: 44 ms, The linked submissions in Python online submissions for Minimum One Bit Operations to Make Integers Zero. Memory Usage: The linked submissions in Python online submissions for Minimum One Bit Operations to Make Integers Zero.Copy the code

Original link: leetcode.com/problems/mi…

Your support is my biggest motivation