changed 2 years ago  
Published Linked with GitHub

Leetcode刷題學習筆記–Bit Manipulation

Code Snippet

  1. 把left most的1切換成0
val = val & (val - 1);
  1. 把left mode的1取出來
mask = val & -val;

Problems

137. Single Number II(Medium)

給你一個數列vector<int> nums，其中每個數都會出現3次，只有一個數出現一次。找出出現一次的數字。

  1. 我一開始使用hash map來統計，雖然tc為\(O(N)\)，但是sc也是\(O(N)\)
  2. 官方解答有數學解，即
    \(sum = 3(x_1+x_2+...+x_n) + k\)
    \(sum = 3(setsum - k) + k\)
    \(k = (3setsum - sum) / 2\)
  3. 另一種是看數字的bit，只要分別統計每個bit的個數，因為都出現3次，所以mod 3 == 0，如果不為0，表示這個bit是因為出現一次的數字。











int singleNumber(vector<int>& nums) {
    int ans{};
    for(int i = 0; i < 32; ++i) {
        int sum{};
        for(auto& n : nums)
            sum += (n >> i) & 1;
        sum %= 3;
        if(sum) ans |= 1 << i;
    }
    return ans;
}

260. Single Number III(Medium)

給你一個數列nums，找出其中只有兩個沒重複的數字。例如：[1,2,1,3,2,5]，答案是[3, 5]因為只有這兩個只有重複一次。

解題思路：

  1. 如果這題只有一個沒重複，那就是把全部XOR起來就可以得到答案。但現在是兩個沒重複的數字。所以全部XOR起來回得到兩個數字的XOR。例如上面的例子就是3^5。
  2. 這邊的關鍵是XOR，如果XOR為1的bit即為不相同的bit。
  3. 3(11b)^5(101b) = 110b，意味3和5中第二和第三個bit不相同。
  4. mask = diff & -diff; 取出最後一個不相同的bit。
  5. 所以我可以使用這個當成mask把數字分成兩邊，分成兩邊後，每一邊的數列只會有一個不重複的數字，就可以使用XOR把不重複的數字找出來。


















vector<int> singleNumber(vector<int>& nums) {
    auto n = nums.size();
    if(n == 2) return nums;
        
    unsigned long diff = accumulate(nums.begin(), nums.end(), 0, bit_xor());
        
    int mask = diff & -diff;   // get the last difference bit
    
    vector<int> rtn{0, 0};
    for(auto& n : nums) {
        if(n & mask)
            rtn[0] ^= n;
        else
            rtn[1] ^= n;
    }
        
    return rtn;
}

這邊有幾個關鍵：

  1. nums的size從2開始，因為只有兩個不重複數字，所以size==2可以直接return。
  2. diff須告為unsigned long，因為diff宣告為unsigned int且為整數最大值的時候，-diff會超出可以表示的範圍，

287. Find the Duplicate Number[Medium]

同樣題目使用fast slow pointer的解法請參考連結。
這邊是參考這個部落格。這個解法非常漂亮，值得學習。

解題思路:

  1. 題目說有N+1個數，全部都在[1, N]的範圍裏面。
  2. 重複的數字會出現兩次或多次。其他數字只會一次。
  3. 假設重複的數字出現兩次，也就是其他數字[1, N]都會出現一次。=> 統計[1, N]的數字每個bit有幾個bit 1。=> cnt1。
  4. 計算所有nums相同bit位置的1有幾個。=> cnt2。
  5. 如果cnt2 > cnt2表示重複的數字在這個位置上的bit為1。
  6. 如果重複的數字出現兩次以上，cnt2會比出現兩次還大，所以還是成立。













int findDuplicate(vector<int>& nums) {
    int res = 0, n = nums.size();
    for (int i = 0; i < 32; ++i) {
        int bit = (1 << i), cnt1 = 0, cnt2 = 0;
        for (int k = 0; k < n; ++k) {
            if ((k & bit) > 0) ++cnt1;
            if ((nums[k] & bit) > 0) ++cnt2;
        }
        if (cnt2 > cnt1) res += bit;
    }
    return res;
}

201. Bitwise AND of Numbers Range(Medium)

給你一個範圍的整數[left, right]，求出這個範圍裏面所有整數的AND。

  1. 把這個範圍內所有的數字都AND，如果有一個0就一定為0，所以等於是求範圍內，左邊都一樣的部分。











int rangeBitwiseAnd(int left, int right) {
    int i{0};
    while(left != right) {
        left >>= 1;
        right >>= 1;
        i++;
    }
        
    return left << i;
}

2022/12/6

  1. 另一個找出common prefix的方法是，逐步把right的leftmost關掉，直到right <= left。
  2. 因為 right & right - 1 就是把left most的1變成0，如果比left還小表示找到了common prefix。






int rangeBitwiseAnd(int left, int right) {
    while(right > left) {
        right &= right - 1;
    }
    return left & right;
}
tags: leetcode 刷題
Select a repo