🎎改頭換面 二進位操作 用最少的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

留言
avatar-img
留言分享你的想法!
avatar-img
小松鼠的演算法樂園
96會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/10/06
題目敘述 Rank Transform of an Array 給定一個陣列arr,請根據數字的大小給予序號,序號值介於1~len( set(arr) )之間。 最大的數字給予最大的序號。 次大的數字給予次大的序號。 ...依此類推 最小的數字給予最小的序號1。
Thumbnail
2024/10/06
題目敘述 Rank Transform of an Array 給定一個陣列arr,請根據數字的大小給予序號,序號值介於1~len( set(arr) )之間。 最大的數字給予最大的序號。 次大的數字給予次大的序號。 ...依此類推 最小的數字給予最小的序號1。
Thumbnail
2024/10/01
題目敘述 Check If Array Pairs Are Divisible by k 給定一個長度為偶數的整數陣列arr,和一個整數k 。 我們想把陣列元素兩兩一組組成pair,使得每個pair的總和可以被k整除。 如果做得到,返回True。 如果不行,返回False。
Thumbnail
2024/10/01
題目敘述 Check If Array Pairs Are Divisible by k 給定一個長度為偶數的整數陣列arr,和一個整數k 。 我們想把陣列元素兩兩一組組成pair,使得每個pair的總和可以被k整除。 如果做得到,返回True。 如果不行,返回False。
Thumbnail
2024/09/29
My Calendar II 給定一個行事曆的class定義和行程安排的介面。 請完成下列function 1.建構子MyCalendarTwo() 2.boolean book(int start, int end) 在行事曆加入一項新行程,起始時間為start, 結束時間為end。
Thumbnail
2024/09/29
My Calendar II 給定一個行事曆的class定義和行程安排的介面。 請完成下列function 1.建構子MyCalendarTwo() 2.boolean book(int start, int end) 在行事曆加入一項新行程,起始時間為start, 結束時間為end。
Thumbnail
看更多
你可能也想看
Thumbnail
孩子寫功課時瞇眼?小心近視!這款喜光全光譜TIONE⁺光健康智慧檯燈,獲眼科院長推薦,網路好評不斷!全光譜LED、180cm大照明範圍、5段亮度及色溫調整、350度萬向旋轉,讓孩子學習更舒適、保護眼睛!
Thumbnail
孩子寫功課時瞇眼?小心近視!這款喜光全光譜TIONE⁺光健康智慧檯燈,獲眼科院長推薦,網路好評不斷!全光譜LED、180cm大照明範圍、5段亮度及色溫調整、350度萬向旋轉,讓孩子學習更舒適、保護眼睛!
Thumbnail
創作者營運專員/經理(Operations Specialist/Manager)將負責對平台成長及收入至關重要的 Partnership 夥伴創作者開發及營運。你將發揮對知識與內容變現、影響力變現的精準判斷力,找到你心中的潛力新星或有聲量的中大型創作者加入 vocus。
Thumbnail
創作者營運專員/經理(Operations Specialist/Manager)將負責對平台成長及收入至關重要的 Partnership 夥伴創作者開發及營運。你將發揮對知識與內容變現、影響力變現的精準判斷力,找到你心中的潛力新星或有聲量的中大型創作者加入 vocus。
Thumbnail
Minimum Bit Flips to Convert Number 給定兩個整數start 和 goal,請問最少需要幾次bit翻轉,使得start等於goal? 註: bit翻轉的定義就是0->1 或者1->0
Thumbnail
Minimum Bit Flips to Convert Number 給定兩個整數start 和 goal,請問最少需要幾次bit翻轉,使得start等於goal? 註: bit翻轉的定義就是0->1 或者1->0
Thumbnail
題目敘述 Minimum Deletions to Make String Balanced 給定一個只會有包含'a'b或'b'的輸入字串s。 每次操作可以任選一個字元刪除。 請問最少需要多少次操作,才會使得所有的'b'都在'a'後面? 測試範例 Example 1: Input: s
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
題目敘述: Reverse Bits 給定一個32bit的整數,請逆序翻轉其二進位表達式,輸出翻轉過後的數字。 例如輸入是二進位1010111 逆序翻轉後是 1110101,對應的十進位數值是117 測試範例 Example 1: Input: n = 00000010100101000
Thumbnail
題目敘述 Minimum Increment to Make Array Unique 給定一個整數陣列,每回合可以任意挑一個數字進行+1的加法操作。 請問最少需要多少次的+1加法操作,才能讓每個數字都相異?
Thumbnail
題目敘述 Minimum Increment to Make Array Unique 給定一個整數陣列,每回合可以任意挑一個數字進行+1的加法操作。 請問最少需要多少次的+1加法操作,才能讓每個數字都相異?
Thumbnail
題目敘述 輸入給定一個二元的二維矩陣grid 每次可以翻轉一條row,讓每個元素的01反相。 也可以翻轉一條column,讓每個元素的01反相。 可以操作任意多次。 最後把每條row視為一條二進位表達式的數字,並且進行加總,得到最後的分數。 請問分數的最大值是多少? 原本的英文題目敘
Thumbnail
題目敘述 輸入給定一個二元的二維矩陣grid 每次可以翻轉一條row,讓每個元素的01反相。 也可以翻轉一條column,讓每個元素的01反相。 可以操作任意多次。 最後把每條row視為一條二進位表達式的數字,並且進行加總,得到最後的分數。 請問分數的最大值是多少? 原本的英文題目敘
Thumbnail
這篇文章,會帶著大家複習以前學過的二進位DP框架, 並且以0~N的整數有幾個bit1,有幾個bit0的概念為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 常見的考法 請問整數k有幾個bit1? 有幾個bit0? 請問整數0到整數N分別各有幾個bit1? 有幾個
Thumbnail
這篇文章,會帶著大家複習以前學過的二進位DP框架, 並且以0~N的整數有幾個bit1,有幾個bit0的概念為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 常見的考法 請問整數k有幾個bit1? 有幾個bit0? 請問整數0到整數N分別各有幾個bit1? 有幾個
Thumbnail
題目會給定一個陣列nums和一個目標值goal。計算子陣列總和=goal的數目有多少。演算法包含前綴和和字典的技巧,時間複雜度為O(n),空間複雜度為O(n)。
Thumbnail
題目會給定一個陣列nums和一個目標值goal。計算子陣列總和=goal的數目有多少。演算法包含前綴和和字典的技巧,時間複雜度為O(n),空間複雜度為O(n)。
Thumbnail
題目敘述 題目會給定我們一個整數陣列nums,要求我們把裡面的0做元素交換,把0都搬到陣列的右邊。題目要求必須in-place在原本的陣列裡面做操作,不可以額外建立新的陣列。 題目的原文敘述 測試範例 Example 1: Input: nums = [0,1,0,3,12] Outpu
Thumbnail
題目敘述 題目會給定我們一個整數陣列nums,要求我們把裡面的0做元素交換,把0都搬到陣列的右邊。題目要求必須in-place在原本的陣列裡面做操作,不可以額外建立新的陣列。 題目的原文敘述 測試範例 Example 1: Input: nums = [0,1,0,3,12] Outpu
Thumbnail
題目敘述 題目會給定三個參數a, b, c。 請問透過bit flip a 或 b 的binary bits,讓 a OR b = c 最少需要幾次bit flip? 題目的原文敘述 測試範例 Example 1: Input: a = 2, b = 6, c = 5 Output:
Thumbnail
題目敘述 題目會給定三個參數a, b, c。 請問透過bit flip a 或 b 的binary bits,讓 a OR b = c 最少需要幾次bit flip? 題目的原文敘述 測試範例 Example 1: Input: a = 2, b = 6, c = 5 Output:
Thumbnail
題目敘述 題目會給定我們一個n值,要求我們列出從0 ~ n 之間,每個整數有幾個bit1,以陣列的形式返回答案。 例如n=3時 因為 0 = 0b 0 1 = 0b 1 2 = 0b 10 3 = 0b 11 輸出答案為[0, 1, 1, 2] 題目的原文敘述 測試範例 E
Thumbnail
題目敘述 題目會給定我們一個n值,要求我們列出從0 ~ n 之間,每個整數有幾個bit1,以陣列的形式返回答案。 例如n=3時 因為 0 = 0b 0 1 = 0b 1 2 = 0b 10 3 = 0b 11 輸出答案為[0, 1, 1, 2] 題目的原文敘述 測試範例 E
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News