LeetCode-位運算相關題解

2020 年 7 月 17 日
筆記
Python, 每日一題, 每日得到記錄

今日得到：位運算真的是 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）,因此，我們可以將問題重新表述為：給定兩個整數，要求我們找到她們二進位字元串的公共前綴

使用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

找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

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

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

我是先看題解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]

注意：

結果輸出的順序並不重要，對於上面的例子， [5, 3] 也是正確答案。
你的演算法應該具有線性時間複雜度。你能否僅使用常數空間複雜度來實現？

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

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

那麼通過什麼把數組分成兩組呢？

放眼到二進位，我們要找的這兩個數字是不同的，所以它倆至少有一位是不同的，所以我們可以根據這一位，把數組分成這一位都是 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，再取反，再相與。比如 1010 減 1 就是 1001，然後取反 0110，然後和原數 1010 相與，就是 0010 了

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

這裡的做法

參考資料

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

五分鐘學演算法-面試官，別問我 Bit Operation 了！

Tags: Python 每日一題每日得到記錄