🎎改頭換面 二進位操作 用最少的bit翻轉讓兩個數字相同_Leetcode #2220

閱讀時間約 1 分鐘

題目敘述 Minimum Bit Flips to Convert Number


給定兩個整數start 和 goal,請問最少需要幾次bit翻轉,使得start等於goal?

註:

bit翻轉的定義就是0->1 或者1->0


測試範例

Example 1:

Input: start = 10, goal = 7
Output: 3
Explanation: The binary representation of 10 and 7 are 1010 and 0111 respectively. We can convert 10 to 7 in 3 steps:
- Flip the first bit from the right: 1010 -> 1011.
- Flip the third bit from the right: 1011 -> 1111.
- Flip the fourth bit from the right: 1111 -> 0111.
It can be shown we cannot convert 10 to 7 in less than 3 steps. Hence, we return 3.

Example 2:

Input: start = 3, goal = 4
Output: 3
Explanation: The binary representation of 3 and 4 are 011 and 100 respectively. We can convert 3 to 4 in 3 steps:
- Flip the first bit from the right: 011 -> 010.
- Flip the second bit from the right: 010 -> 000.
- Flip the third bit from the right: 000 -> 100.
It can be shown we cannot convert 3 to 4 in less than 3 steps. Hence, we return 3.

約束條件

Constraints:

  • 0 <= start, goal <= 10^9

start, goal都介於0~十億之間。


演算法 用XOR運算子計算有幾個bit不同


想法相當直覺,

start和goal的二進位表達式有幾個bit不同,就需要幾次對應的bit翻轉


先計算start XOR goal的值

接著,建造一個迴圈,計算有幾個bit不同,最後返回作為答案。


Python程式碼 用XOR運算子計算有幾個bit不同

class Solution:
def minBitFlips(self, start: int, goal: int) -> int:

# User XOR(^) for finding different bits
# then count bits 1 in difference
difference = start ^ goal

counter = 0

for i in range(32):

if difference & 1 == 1:
counter += 1

difference >>= 1

return counter

Go 程式碼 用XOR運算子計算有幾個bit不同

func minBitFlips(start, goal int) int {

// User XOR(^) for finding different bits
// then count bits 1 in difference
difference := start ^ goal

counter := 0
for i := 0 ; i < 32 ; i++{
if difference & 1 == 1{
counter += 1
}
difference >>= 1
}
return counter
}

複雜度分析

時間複雜度: O(1)

掃描32bit整數的每一個位置,所需時間為O(32) = O(1) 常數級別。


空間複雜度: O(1)

所用到的都是固定尺寸的臨時變數,為常數級別O(1)。


Reference

[1] Minimum Bit Flips to Convert Number - LeetCode

84會員
424內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
2326. Spiral Matrix IV 題目給定一個Linked list和對應的矩陣高度m、寬度n。 請依照順時針的拜訪順序, 從左上角出發,依照次序把Linked List的內容填到矩陣裡。 如果有剩餘不足的空位,就填補-1。 最後將填補好的矩陣返回作為答案。
Walking Robot Simulation 機器人在一個無限大小的 X-Y 2D平面上行走,從點 (0, 0) 開始出發,一開始面向北方。 機器人可以接收以下三種類型的命令 -2 :向左轉 90 度 -1 :向右轉 90 度 1 <= x <= 9 :向前移動 x步
Leetcode #1945. Sum of Digits of String After Convert 給定一個由小寫字母組成的字串 s ,以及一個整數 k 。 首先,用英文字母順序的位置替換每個字母,將 s 轉換 為整數 並且計算digits sum,反覆迭代k次。
給定一個長度為 n,而且索引從 0 開始的整數陣列 chalk 和參數 k 。一開始粉筆盒裡總共有 k 支粉筆。 當編號為 i 的學生回答問題時,會消耗 chalk[i] 支粉筆。 如果剩餘粉筆數量小於 chalk[i] ,那麼學生 i 需要 補充 粉筆。 請找出需要補充粉筆的學生的學生編號。
Convert 1D Array Into 2D Array 給定一個一維輸入陣列,請轉換成高度為m*寬度為n的二維陣列, 以二維陣列的形式輸出。 如果無法轉換,請輸出空陣列。
題目敘述 624. Maximum Distance in Arrays 給定一個輸入二維陣列arrays。 請計算的陣列距離是多少? 陣列距離的定義 = max | a - b | 其中 a, b 來自不同的一維陣列
2326. Spiral Matrix IV 題目給定一個Linked list和對應的矩陣高度m、寬度n。 請依照順時針的拜訪順序, 從左上角出發,依照次序把Linked List的內容填到矩陣裡。 如果有剩餘不足的空位,就填補-1。 最後將填補好的矩陣返回作為答案。
Walking Robot Simulation 機器人在一個無限大小的 X-Y 2D平面上行走,從點 (0, 0) 開始出發,一開始面向北方。 機器人可以接收以下三種類型的命令 -2 :向左轉 90 度 -1 :向右轉 90 度 1 <= x <= 9 :向前移動 x步
Leetcode #1945. Sum of Digits of String After Convert 給定一個由小寫字母組成的字串 s ,以及一個整數 k 。 首先,用英文字母順序的位置替換每個字母,將 s 轉換 為整數 並且計算digits sum,反覆迭代k次。
給定一個長度為 n,而且索引從 0 開始的整數陣列 chalk 和參數 k 。一開始粉筆盒裡總共有 k 支粉筆。 當編號為 i 的學生回答問題時,會消耗 chalk[i] 支粉筆。 如果剩餘粉筆數量小於 chalk[i] ,那麼學生 i 需要 補充 粉筆。 請找出需要補充粉筆的學生的學生編號。
Convert 1D Array Into 2D Array 給定一個一維輸入陣列,請轉換成高度為m*寬度為n的二維陣列, 以二維陣列的形式輸出。 如果無法轉換,請輸出空陣列。
題目敘述 624. Maximum Distance in Arrays 給定一個輸入二維陣列arrays。 請計算的陣列距離是多少? 陣列距離的定義 = max | a - b | 其中 a, b 來自不同的一維陣列
你可能也想看
Google News 追蹤
Thumbnail
本專欄將提供給您最新的市場資訊、產業研究、交易心法、精選公司介紹,以上內容並非個股分析,還請各位依據自身狀況作出交易決策。歡迎訂閱支持我,獲得相關內容,也祝您的投資之路順遂! 每年 $990 訂閱方案👉 https://reurl.cc/VNYVxZ 每月 $99 訂閱方案👉https://re
Thumbnail
分享一個猜數字的遊戲題目,給予提示讓玩家找出正確的四位數密碼。
Thumbnail
題目敘述 Minimum Deletions to Make String Balanced 給定一個只會有包含'a'b或'b'的輸入字串s。 每次操作可以任選一個字元刪除。 請問最少需要多少次操作,才會使得所有的'b'都在'a'後面? 測試範例 Example 1: Input: s
Thumbnail
題目敘述: Reverse Bits 給定一個32bit的整數,請逆序翻轉其二進位表達式,輸出翻轉過後的數字。 例如輸入是二進位1010111 逆序翻轉後是 1110101,對應的十進位數值是117 測試範例 Example 1: Input: n = 00000010100101000
Thumbnail
題目敘述: Minimum Cost to Convert String I 給定字元轉換映射表original, changes和對硬的成本陣列cost。 請問字串source轉換到字串destination的最小成本是多少? 如果無解,請返回-1 如果有解,請返回整體的轉換最小成本。
Thumbnail
題目敘述 Merge Nodes in Between Zeros 給定一個鏈結串列,合併非零區間的節點(以加總的方式合併),輸出合併後的鏈結串列。
Thumbnail
題目敘述 Patching Array 題目給定一個整數陣列, 請問還要補上多少個數字,才能用這些數字的和拼湊出所有1~n的整數。
Thumbnail
題目敘述 Minimum Increment to Make Array Unique 給定一個整數陣列,每回合可以任意挑一個數字進行+1的加法操作。 請問最少需要多少次的+1加法操作,才能讓每個數字都相異?
Thumbnail
題目敘述 題目的情境是設計並且實現一個包含所有正整數的數據流,以set集合的方式存在。 數據流 = {1, 2, 3, 4, ..., ∞} 要求我們去實現定義好的function介面: SmallestInfiniteSet()建構子,初始化這個包含所有正整數的數據流。 int po
Thumbnail
題目敘述 題目會給定我們兩個字串word1 和 word2。 允許我們不限制次數進行下列兩種操作: 任意調換其中兩個字元的位置。 把字串中的某個字元全部置換成另一個字元,同時把另一個字元同時置換成某個字元。(例如把字串中原本的a都換成b,把原本的b都換成a) 問我們能不能通過上述兩項操作,
Thumbnail
題目敘述 題目會給我們一個整數陣列,裡面包含各種正整數,每回合可以消去兩個相同的數字,或者消去三個相同的數字。問最少需要幾次消去,才能讓陣列為空? 如果無解,則返回-1 詳細的題目可在這裡看到 測試範例 Example 1: Input: nums = [2,3,3,2,2,4,2,3,
Thumbnail
本專欄將提供給您最新的市場資訊、產業研究、交易心法、精選公司介紹,以上內容並非個股分析,還請各位依據自身狀況作出交易決策。歡迎訂閱支持我,獲得相關內容,也祝您的投資之路順遂! 每年 $990 訂閱方案👉 https://reurl.cc/VNYVxZ 每月 $99 訂閱方案👉https://re
Thumbnail
分享一個猜數字的遊戲題目,給予提示讓玩家找出正確的四位數密碼。
Thumbnail
題目敘述 Minimum Deletions to Make String Balanced 給定一個只會有包含'a'b或'b'的輸入字串s。 每次操作可以任選一個字元刪除。 請問最少需要多少次操作,才會使得所有的'b'都在'a'後面? 測試範例 Example 1: Input: s
Thumbnail
題目敘述: Reverse Bits 給定一個32bit的整數,請逆序翻轉其二進位表達式,輸出翻轉過後的數字。 例如輸入是二進位1010111 逆序翻轉後是 1110101,對應的十進位數值是117 測試範例 Example 1: Input: n = 00000010100101000
Thumbnail
題目敘述: Minimum Cost to Convert String I 給定字元轉換映射表original, changes和對硬的成本陣列cost。 請問字串source轉換到字串destination的最小成本是多少? 如果無解,請返回-1 如果有解,請返回整體的轉換最小成本。
Thumbnail
題目敘述 Merge Nodes in Between Zeros 給定一個鏈結串列,合併非零區間的節點(以加總的方式合併),輸出合併後的鏈結串列。
Thumbnail
題目敘述 Patching Array 題目給定一個整數陣列, 請問還要補上多少個數字,才能用這些數字的和拼湊出所有1~n的整數。
Thumbnail
題目敘述 Minimum Increment to Make Array Unique 給定一個整數陣列,每回合可以任意挑一個數字進行+1的加法操作。 請問最少需要多少次的+1加法操作,才能讓每個數字都相異?
Thumbnail
題目敘述 題目的情境是設計並且實現一個包含所有正整數的數據流,以set集合的方式存在。 數據流 = {1, 2, 3, 4, ..., ∞} 要求我們去實現定義好的function介面: SmallestInfiniteSet()建構子,初始化這個包含所有正整數的數據流。 int po
Thumbnail
題目敘述 題目會給定我們兩個字串word1 和 word2。 允許我們不限制次數進行下列兩種操作: 任意調換其中兩個字元的位置。 把字串中的某個字元全部置換成另一個字元,同時把另一個字元同時置換成某個字元。(例如把字串中原本的a都換成b,把原本的b都換成a) 問我們能不能通過上述兩項操作,
Thumbnail
題目敘述 題目會給我們一個整數陣列,裡面包含各種正整數,每回合可以消去兩個相同的數字,或者消去三個相同的數字。問最少需要幾次消去,才能讓陣列為空? 如果無解,則返回-1 詳細的題目可在這裡看到 測試範例 Example 1: Input: nums = [2,3,3,2,2,4,2,3,