Re: [閒聊] 每日LeetCode

[Rushia (みけねこ的鼻屎)]

※ 引述《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

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1708534754.A.848.html
推 oin1104: 這題蠻微妙的 我一開始一直在想差多少的話要把那些數字
→ oin1104: 弄成0
→ oin1104: 然後看了提示就直接懂了
→ Rushia: 這題沒提示我只好抄答案
→ Rushia: bitwise沒看過這種用法就想不太到
推 oin1104: 留言區蠻多提示的 然後直接寫解答的我都恨恨的給他倒讚
推 JIWP: 大師
推 leafff: 大師