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

語言: CN / TW / HK

「這是我參與11月更文挑戰的第25天,活動詳情檢視:2021最後一次更文挑戰

描述

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

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.

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.

Example 4:

Input: n = 9
Output: 14

Example 5:

Input: n = 333
Output: 393

Note:

0 <= n <= 109

解析

根據題意,給定一個整數 n,必須使用任意次數的以下操作將其轉換為 0:

  • 更改 n 的二進位制表示最右邊的位。可以 0 變為 1 ,也可以 1 變為 0 。
  • 如果第 (i-1) 位設定為 1 並且第 (i-2) 到第 0 位設定為 0,則更改 n 的二進位制表示中的第 i 位。可以 0 變為 1 ,也可以 1 變為 0 。

注意題目中的二進位制位的索引都是從右向左的,返回將 n 轉換為 0 的最小運算元。因為方法一隻是將最右邊的 0 和 1 互換,無法對前面的字元進行操作,所以關鍵就是巧用方法二進行變化,假如我們舉例,將 101011 變為 000000 ,其最簡單的思路就是遞迴:

  • (1)101011 第一位為 1 ,想要將其變為 100000 ,就呼叫自定義的 convert 函式,該函式的功能就是找出將 01011 變為 10000 的最少次數
  • (2)應用方法二將變化之後的 110000 變為 010000 進行了 1 次操作,然後計算將 10000 變為 00000 的次數,和上面同樣的方法,將 0000 通過 convert 函式變為 1000 ,在進行相同的操作,直到最後變為 000000
  • (3)所以定義遞迴函式 dfs ,表示對輸入二進位制的最少次數操作,將上面的過程表示出來就是 dfs(101011) = convert(01011) + 1 + dfs(10000)

但是 convert 有兩種情況:

  • 第一種情況是二進位制的第一個數字是 1 ,如 1110 。那直接呼叫 dfs(110) 即可
  • 第二種情況是二進位制的第一個數字是 0 ,如 0111 ,又是需要遞迴 :convert(0111) = convert(111) + 1 + dfs(100)

解答

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]

執行結果

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.

原題連結:https://leetcode.com/problems/minimum-one-bit-operations-to-make-integers-zero/

您的支援是我最大的動力