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）
20220201 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 (0^{th}) bit in the binary representation of n.
 Change the i^{th} bit in the binary representation of n if the (i1)^{th} bit is set to 1 and the (i2)^{th} through 0^{th} 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 (i1) Bit is set to 1 And No (i2) 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
The sidebar is recommended
 Python * * packaging and unpacking details
 Python realizes weather query function
 Python from 0 to 1 (day 12)  Python data application 2 (STR function)
 Python from 0 to 1 (day 13)  Python data application 3
 Numpy common operations of Python data analysis series Chapter 8
 How to implement mockserver [Python version]
 Van * Python! Write an article and publish the script on multiple platforms
 Python data analysis  file reading
 Python data De duplication and missing value processing
 Python office automation  play with browser
guess what you like

Python series tutorial 127  Reference vs copy

Control flow in Python: break and continue

Teach you how to extract tables in PDF with Python

leetcode 889. Construct Binary Tree from Preorder and Postorder Traversal（python）

leetcode 1338. Reduce Array Size to The Half（python）

Object oriented and exception handling in Python

How to configure load balancing for Django service

How to embed Python in go

Python Matplotlib drawing graphics

Python objectoriented programming 05: concluding summary of classes and objects
Random recommended
 Python from 0 to 1 (day 14)  Python conditional judgment 1
 Several very interesting modules in Python
 How IOS developers learn Python Programming 15  object oriented programming 1
 Daily python, Chapter 20, exception handling
 Understand the basis of Python collaboration in a few minutes
 [centos7] how to install and use Python under Linux
 leetcode 1130. Minimum Cost Tree From Leaf Values（python）
 leetcode 1433. Check If a String Can Break Another String（python）
 Python Matplotlib drawing 3D graphics
 Talk about deep and shallow copying in Python
 Python crawler series  network requests
 Python thread 01 understanding thread
 Analysis of earthquake distribution in the past 10 years with Python~
 You need to master these before learning Python crawlers
 After the old friend (R & D post) was laid off, I wanted to join the snack bar. I collected some data in Python. It's more or less a intention
 Python uses redis
 Python crawler  ETF fund acquisition
 Detailed tutorial on Python operation Tencent object storage (COS)
 [Python] comparison of list, tuple, array and bidirectional queue methods
 Go Python 3 usage and pit Prevention Guide
 Python logging log error and exception exception callback method
 Learn Python quickly and take a shortcut~
 Python from 0 to 1 (day 15)  Python conditional judgment 2
 Python crawler actual combat, requests module, python to capture headlines and take beautiful pictures
 The whole activity collected 8 proxy IP sites to pave the way for the python proxy pool, and the 15th of 120 crawlers
 Why can't list be used as dictionary key value in Python
 Python from 0 to 1 (day 16)  Python conditional judgment 3
 What is the python programming language?
 Python crawler reverse webpack, a real estate management platform login password parameter encryption logic
 Python crawler reverse, a college entrance examination volunteer filling platform encrypts the parameter signsafe and decrypts the returned results
 Python simulated Login, selenium module, python identification graphic verification code to realize automatic login
 Python  datetime (timedelta class)
 Python's five strange skills will bring you a sense of enrichment in mastering efficient programming skills
 [Python] comparison of dictionary dict, defaultdict and orderdict
 Test driven development using Django
 Face recognition practice: face recognition using Python opencv and deep learning
 leetcode 1610. Maximum Number of Visible Points（python）
 Python thread 03 thread synchronization
 Introduction and internal principles of Python's widely used concurrent processing Library Futures
 Python  progress bar artifact tqdm usage