# Leetcode 1611. Minimum one bit operations to make integers Zero (Python)

Wang Da - Ah! 2021-11-25 09:40:15
leetcode minimum bit operations make

「C'est ma participation11Le défi du mois de juin25Oh, mon Dieu.,Voir les détails de l'événement：2021Un dernier défi

### Description

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
Copier le 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.
Copier le 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.
Copier le Code``````

Example 4:

``````Input: n = 9
Output: 14
Copier le Code``````

Example 5:

``````Input: n = 333
Output: 393
Copier le Code``````

Note:

``````0 <= n <= 109
Copier le Code``````

### Analyse

Selon le titre,Compte tenu d'un entier n, Il doit être converti en 0：

• Changement n Le binaire de représente le BIT le plus à droite .C'est bon. 0 Devient 1 ,C'est possible. 1 Devient 0 .
• Si (i-1) Bit set to 1 Et par (i-2) À la 0 Bit set to 0, Puis changer n Dans la représentation binaire de i Bits.C'est bon. 0 Devient 1 ,C'est possible. 1 Devient 0 .

Notez que les index des bits binaires dans le titre sont de droite à gauche ,Le retour n Convertir en 0 Nombre minimum d'opérations pour. Parce que la première méthode va juste à droite 0 Et 1 Swap, Impossible d'utiliser les caractères précédents , Donc la clé est d'utiliser la méthode 2 pour changer , Si on donnait un exemple ,Oui. 101011 Devient 000000 , L'idée la plus simple est la récursion ：

• （1）101011 La première place est 1 , Pour en faire 100000 , Appelle juste la personnalisation convert Fonctions, La fonction est de trouver ce qui va 01011 Devient 10000 Nombre minimum de
• （2） L'application de la méthode II modifiera 110000 Devient 010000 C'est fait. 1 Opérations secondaires, Et le calcul va 10000 Devient 00000 Nombre de fois, De la même façon que ci - dessus ,Oui. 0000 Adoption convert La fonction devient 1000 , Après la même opération , Jusqu'à ce qu'il devienne 000000
• （3） Alors définissez la fonction récursive dfs , Représente le nombre minimum d'opérations sur le binaire d'entrée , Le processus décrit ci - dessus est dfs(101011) = convert(01011) + 1 + dfs(10000)

Mais convert Il y a deux situations：

• Le premier cas est que le premier chiffre binaire est 1 ,Par exemple: 1110 .C'est un appel direct. dfs(110) C'est tout.
• Le deuxième cas est que le premier chiffre binaire est 0 ,Par exemple: 0111 , Encore besoin de récursion ：convert(0111) = convert(111) + 1 + dfs(100)

### La solution

``````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]
Copier le Code``````

### Résultats des opérations

``````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.
Copier le Code``````

Lien vers la question originale：leetcode.com/problems/mi…

Votre soutien est ma plus grande motivation

https://pythonmana.com/2021/11/20211125094013433l.html