LeetCode-位運算相關題解

今日得到: 位運算真的是 666, 計算機基礎還有數學知識都很重要.

LeetCode-191 二進制位1的個數

LeetCode上第 191 號問題:編寫一個函數,輸入是一個無符號整數,返回其二進制表達式中數字位數為 ‘1’ 的個數。

觀察一下 n 與 n-1 這兩個數的二進制表示:對于 n-1 這個數的二進制來說,相對于 n 的二進制,它的最末位的一個 1 會變成 0,最末位一個 1 之后的 0 會全部變成 1,其它位相同不變。

比如 n = 8888,其二進制為 10001010111000

則 n - 1 = 8887 ,其二進制為 10001010110111

通過按位與操作后:n & (n-1) = 10001010110000

也就是說:通過 n&(n-1)這個操作,可以起到消除最后一個1的作用。

所以可以通過執行 n&(n-1) 操作來消除 n 末尾的 1 ,消除了多少次,就說明有多少個 1 。

class Solution:
    def hammingWeight(self, n):
        res = 0
        while n != 0:
            res += 1
            n &= (n - 1)
        return res

    def hammingWeight2(self, n):
        res = 0
        while n != 0:
            res += (n & 1)
            n = n >> 1
        return res

算法-求二進制數中1的個數 多種解法

LeetCode-231 2的冪

給定一個整數,編寫一個函數來判斷它是否是 2 的冪次方。

仔細觀察,可以看出 2 的次方數都只有一個 1 ,剩下的都是 0 。根據這個特點,只需要每次判斷最低位是否為 1 ,然后向右移位,最后統計 1 的個數即可判斷是否是 2 的次方數, 可以使用上一個問題的解法

def isPowerOfTwo(n):
        res = 0
        while n != 0:
            res += (n & 1)
            n >>= 1
        return res == 1

該題還有一種巧妙的解法。再觀察上面的表格,如果一個數是 2 的次方數的話,那么它的二進數必然是最高位為1,其它都為 0 ,那么如果此時我們減 1 的話,則最高位會降一位,其余為 0 的位現在都為變為 1,那么我們把兩數相與,就會得到 0.

圖片來源

比如 2 的 3 次方為 8,二進制位 1000 ,那么 8 - 1 = 7,其中 7 的二進制位 0111

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return (n > 0) and ((n & (n - 1)) == 0)

LeetCode-201. 閉區間范圍內數字按位與

給定范圍 [m, n],其中 0 <= m <= n <= 2147483647,返回此范圍內所有數字的按位與(包含 m, n 兩端點)

在這里插入圖片描述

所有這些位字符串的公共前綴也是指定范圍的起始和結束編號的公共前綴(即在上面的示例中分別為 9 和 12),因此,我們可以將問題重新表述為:給定兩個整數,要求我們找到她們二進制字符串的公共前綴

  1. 使用191的方法 Brian Kernighan 算法 n & (n-1)
class Solution:
    def rangeBitwiseAnd(self, m: int, n: int) -> int:
        while m < n:
            # turn off rightmost 1-bit
            n = n & (n - 1)
        return m & n
  1. 找m, n 的最高位1出現的位置 , 如果不相等,則返回0,如果相等,則找公共前綴。B站視頻-位運算練習【LeetCode】

LeetCode-187.重復的DNA序列

所有 DNA 都由一系列縮寫為 A,C,G 和 T 的核苷酸組成,例如:“ACGAATTCCG”。在研究 DNA 時,識別 DNA 中的重復序列有時會對研究非常有幫助。

編寫一個函數來查找目標子串,目標子串的長度為 10,且在 DNA 字符串 s 中出現次數超過一次。差點沒看懂題 QAQ!

輸入:s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
輸出:["AAAAACCCCC", "CCCCCAAAAA"]
# 普通解法
class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        d = {}
        for i in range(len(s) - 9):
            k = s[i: i+10]
            if k in d:
                d[k] = True
            else:
                d[k] = False

        return [*filter(lambda x: d[x], d)]

該的位運算解法暫時沒看懂,先記錄著,有點暈了,后面繼續看

題解

LeetCode-36.只出現一次的數字

給定一個非空整數數組,除了某個元素只出現一次以外,其余每個元素均出現兩次。找出那個只出現了一次的元素。

要求: 你的算法應該具有線性時間復雜度。 你可以不使用額外空間來實現嗎?

輸入: [2,2,1]
輸出: 1
輸入: [4,1,2,1,2]
輸出: 4

這題比較簡單,想到異或運算,相同為0,不同為1的規則就可以很快求解了

a b a⊕b
1 0 1
1 1 0
0 0 0
0 1 1
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # 非空數組暫時不用判斷
		from functools import reduce
    	return reduce(lambda a, b: a ^ b, nums)

LeetCode-137.只出現一次的數字 II

給定一個非空整數數組,除了某個元素只出現一次以外,其余每個元素均出現了三次。找出那個只出現了一次的元素。

要求: 你的算法應該具有線性時間復雜度。 你可以不使用額外空間來實現嗎?

輸入: [2,2,3,2]
輸出: 3
輸入: [0,1,0,1,0,1,99]
輸出: 99

Picture1.png

3×(a+b+c)?(a+a+a+b+b+b+c)=2c 也可以應用在上一題

## 普通解法
class Solution:
    def singleNumber(self, nums):
        return (3 * sum(set(nums)) - sum(nums)) // 2

推廣到一般情況:

如果其他數都出現了 k 次,一個數出現了一次。那么如果 k 是偶數,還是把所有的數異或起來就行了。如果 k 是奇數,那么統計每一位是 1 的個數,然后模 k 取余數就能得到那個單獨的數了 。其中有sum = kn + 1

位運算的解法是有限狀態機+位運算,感覺有點難理解,自己推敲一遍勉強可以理解,自己畫一個狀態表,然后推導出響應的公式就比較好了。

Picture4.png

我是先看題解1, 在看題解2,才搞明白了。

  1. 【自動機+位運算】最詳細的推導過程

  2. 圖片來源:有限狀態自動機 + 位運算,清晰圖解-此題解清晰

幾乎每道題都能看到題解2的作者,佩服不已,時而習之,但求甚解。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ones, twos = 0, 0
        for num in nums:
            ones = ones ^ num & ~twos
            twos = twos ^ num & ~ones
        return ones

LeetCode-260. 只出現一次的數字 III

給定一個整數數組 nums,其中恰好有兩個元素只出現一次,其余所有元素均出現兩次。 找出只出現一次的那兩個元素。

輸入: [1,2,1,3,2,5]
輸出: [3,5]

注意:

  1. 結果輸出的順序并不重要,對于上面的例子, [5, 3] 也是正確答案。
  2. 你的算法應該具有線性時間復雜度。你能否僅使用常數空間復雜度來實現?

根據前面找一個不同數的思路算法,在這里把所有元素都異或,那么得到的結果就是那兩個只出現一次的元素異或的結果。

如果我們把原數組分成兩組,只出現過一次的兩個數字分別在兩組里邊,那么問題就轉換成之前的老問題了,只需要這兩組里的數字各自異或,答案就出來了。

那么通過什么把數組分成兩組呢?

放眼到二進制,我們要找的這兩個數字是不同的,所以它倆至少有一位是不同的,所以我們可以根據這一位,把數組分成這一位都是 1 的一類和這一位都是 0 的一類,這樣就把這兩個數分到兩組里了。

那么怎么知道那兩個數字哪一位不同呢?

回到我們異或的結果,如果把數組中的所有數字異或,最后異或的結果,其實就是我們要找的兩個數字的異或。而異或結果如果某一位是 1,也就意味著當前位兩個數字一個是 1 ,一個是 0,也就找到了不同的一位。

以上思路源于作者:windliang

class Solution:
    def FindNumsAppearOnce(self, nums):
        length = len(nums)
        if length <= 0:
            return nums
        result = 0
        # 先將所有數子異或得到一個值
        for num in nums:
            result ^= num
        # 找到這個值最低位二進制位1的位置,根據這個位置來區分兩個數組,分別異或求出只出現一次的數字
        firstBitIndex = self.FindFirstBit(result)
        n1, n2 = 0, 0
        for num in nums:
            if self.IsSameBit(num, firstBitIndex):
                n1 ^= num
            else:
                n2 ^= num
        return n1, n2

    def FindFirstBit(self, num):
        indexBit = 0
        while num & 1 == 0:
            indexBit += 1
            num = num >> 1
        return indexBit

    def IsSameBit(self, num, indexBit):
        num = num >> indexBit
        return num & 1
# 解放2
class Solution2:
    def FindNumsAppearOnce(self, nums):
        length = len(nums)
        if length <= 0:
            return []

        diff = 0
        for i in nums:
            diff ^= i
    
        n1, n2 = 0, 0
        minDiff = self.getMinDiff(diff)
        for num in nums:
            if minDiff & num == 0:
                n1 ^= num
        n2 = diff ^ n1
        return n1, n2

    def getMinDiff(self, num):
        # 保留一個低位是1的數字
        # 取負號其實就是先取反,再加 1,需要 補碼 的知識。最后再和原數相與就會保留最低位的 1。比如 1010,先取反是 0101,再加 1,就是 0110,再和 1010 相與,就是 0010 了
        return num & (-num)

如何得到二進制位只有一個1的數,幾種方法

diff &= -diff ; 這里 的做法。

取負號其實就是先取反,再加 1,需要 補碼 的知識。最后再和原數相與就會保留最低位的 1。比如 1010,先取反是 0101,再加 1,就是 0110,再和 1010 相與,就是 0010 了。

diff = (diff & (diff - 1)) ^ diff; 這里 的做法

n & (n - 1) 的操作在 191 題 用過,它可以將最低位的 1 置為 0。比如 1110,先將最低位的 1 置為 0 就變成 1100,然后再和原數 1110 異或,就得到了 0010

diff = xor & ~(diff - 1) 這里 的做法

先減 1,再取反,再相與。比如 10101 就是 1001,然后取反 0110,然后和原數 1010 相與,就是 0010

mask=1
while((diff & mask)==0):
    mask <<= 1
# mask 就是我們要構造的了

這里 的做法

推到1到N連續自然數的異或值

1 1=1; 1
2 1^2=3; n+1
3 1^2^3=0; 0
4 1^2^3^4=4; n
5 1^2^3^4^5=1; 1
6 1^2^3^4^5^6=7; n+1
7 1^2^3^4^5^6^7=0; 0
8 1^2^3^4^5^6^7^8=8; n
... ... ...

四個數一次循環:1, n+1, 0, n

def main(n):
    k = n % 4
    res = {
        0: n,
        1: 1,
        2: n + 1,
        3: 0
    }

    return res[k]

例題1:給你一個n,求出1^2^3^....^n的值 數據范圍:img

例題2: 求[m, n]之間的連續異或的值

# 根據異或的性質推到可以得到如下結果,則有化簡為1->n之間的異或
f([m, n]) = f([1, n])^f([1, m-1])

參考資料

補碼為什么按位取反再加一認真看完會有收獲的。

五分鐘學算法-面試官,別問我 Bit Operation 了!

posted @ 2020-07-17 23:51  JonPan  閱讀(59)  評論(0編輯  收藏
最新chease0ldman老人