Re: [閒聊] 每日LeetCode

看板Marginalman作者Rushia (みけねこ的鼻屎)時間3月前 (2024/02/22 00:59)推噓4(4推 0噓 4→)

留言8則, 4人參與討論串706/719 (看更多)

※ 引述《SecondRun (南爹摳打)》之銘言： : 201. Bitwise AND of Numbers Range : 給你left跟right兩個整數 : 回傳left AND left+1 AND left+2 AND ... AND right 解1 TLE class Solution: def rangeBitwiseAnd(self, left: int, right: int) -> int: res = left for i in range(left, right + 1): res &= i return res 解2 WA class Solution: def rangeBitwiseAnd(self, left: int, right: int) -> int: res = left for i in range(left, right + 1): res &= i if res == 0: break return res https://i.imgur.com/8ZXLj1O.jpg

只好看答案。思路： 1.因為 left <= right所以 left 轉成二進制只有兩種可能： right的位數比left多，例如： 1000 比 10 right的位數和left一樣多，例如：1001 比 1000 2.參考下圖，如果right的位數比left多 l: 1xxx r:1xxxxxxx 因為l會不斷遞增直到等於r，所以最後一定會碰到除了最高位元以外全為0的狀況 l:10000000 r:1xxxxxxx 10000000（做and一定會變最高位元以外全0）又因為l位數小於r，所以把上面的結果和l做AND： 10000000 l:00001xxx 我們可以得到如果right的位數比left多，那麼必定AND起來為0。 3.參考下圖，如果right的位數和left一樣多 l:1xxxxxxxx r:1xxxxxxxx 很明顯的，左半邊的and結果就是l和r全為1的部份（因為前面2提到的補0特性），所以我們只要找出左半邊有幾個連續的1，再把右半邊補0，就是全部AND在一起的結果了， AKA從右邊開始找幾個位元範圍的0和1不同，然後把左半邊相同的位數右邊全補0。 pycode： class Solution: def rangeBitwiseAnd(self, left: int, right: int) -> int: shift = 0 while left < right: left = left >> 1 right = right >> 1 shift += 1 return left << shift 恨bitwise -- https://i.imgur.com/PIoxddO.jpg