iT邦幫忙

0

leetcode with python:190. Reverse Bits

題目:

Reverse bits of a given 32 bits unsigned integer.

給定32位的unsigned integer,回傳它反轉後的值(十進位)
ex:input:00000010100101000001111010011100=>output:964176192(00111001011110000010100101000000)

這題就要用到其他我上次在位元運算(Bit Manipulations)一同學到的運算符號了
會用到的有&,>>
AND,即&是對二進位型態的兩數的每一位進行比較
和^不同的是,該位兩數都為1才會回傳1,其餘(0對0,1對0)都回傳0
Right Shift,即>>,是將二進位型態的該數每一位元都往右移,然後在最左端補0
Left Shift,即<<,也是類似的道理

class Solution:
    def reverseBits(self, n: int) -> int:
        ans=0
        for i in range(32):
            if n&1:
                ans=ans+2**(31-i)
            n=n>>1
        return ans

我們從用&1來判斷最右位(第一位)是1還是0,是1會回傳1,是0會回傳0
是1的話我們要回傳的值(ans)就要加2的31-n次方(n表第幾次判斷,即第幾位數)
因為是reverse所以第一位要當最高位來算
每判斷完一次就>>換下一位,總共執行32次(共32位)
最後回傳ans即可
最後執行時間31ms(faster than 95.95%)

只要扯到字串,python永遠不缺新奇解
分享一個我在討論區看到的解法

class Solution:
    def reverseBits(self, n: int) -> int:
        n=bin(n)[2:]
        n=(32-len(n))*"0"+n
        return int(n[::-1],2)

先將unsigned integer變為二進位字串表示(將"0b"去掉)
然後看少了幾個數在前端補0(補償轉換時消失的前端0)
上述兩步驟其實就是快速將unsigned integer轉為字串
之後再reverse轉為int回傳即可
最後執行時間20ms(faster than99.94%)

本題學習到的重點:位元運算(Bit Manipulations)之AND,Right Shift,Left Shift
那我們下題見


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言