Leetcode 刷題 pattern - Bitwise XOR


Posted by Po-Jen on 2020-06-07

前言

身在大 CS 時代,有越來越多人投入刷題的行列,在眼花撩亂的題海中,要想有效率地刷題,就需要掌握題目解法中,可以在許多地方應用的觀念,才能以簡禦繁。 Huli 寫的 程式解題新手入門注意事項當我們在學程式時,要學的到底是什麼? 講得很好,寫題目是為了學會解題的思考法,確保自己掌握重要的資料結構跟演算法。這也是我寫這系列文章的原因,我想把多個散落在各處的題目銜接起來,以後看到相似的問題就可以舉一反三,而不是去背各題目的解法。

另外,這系列文章提供的做法雖然可以讓面試準備事半功倍,但不一定適合你。如果你比較喜歡透過刷很多題來鍛鍊演算法跟資料結構的直覺,那你可以參考 這篇短文,踏上刷遍一千題、融會貫通 computational thinking。

接著就讓我們進入今天的主題 - Bitwise XOR。

Bitwise XOR 簡介

Bitwise XOR 應該算是很基本的觀念,不熟的話就自己去 Google 一下吧,就不浪費時間多說了,直接從範例題目看看可以怎麼運用 Bitwise XOR 來解題。

Bitwise XOR 的第一個範例 - Leetcode #268 - Missing Number

題目

img

暴力法

最簡單的方法之一就是用一個 set 儲存 nums 裡面所有的數字,然後從 0 檢查到 n,看哪個數字不在 set 裡。之所以用 set 是因為搜尋某個數字在不在裡面的效率比 array 高很多。簡單的實作如下:

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());

        int n = nums.size();
        for(int i = 0; i <= n; ++i) {
            if(s.count(i) == 0) {
                return i;
            }
        }

        return -1;
    }
};

雖然時間複雜度是 O(n),但空間複雜度也是 O(n),我們能否用 O(1) 的空間複雜度解決這題呢?

Sum 解法

這個 nums 有一個很重要的特性,就是裡面的數字落在 0 到 n 之間,也就是說,假設沒有 missing number,總和就應該是 1 + 2 + ... + n。所以我們可以先把 1 到 n 的總和算出來,然後減掉所有 nums 裡面的 element,剩下的數字就是 missing number 啦。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int target_sum = 0, n = nums.size();
        for(int i = 0; i <= n; ++i) {
            target_sum += i;
        }

        for(int idx = 0; idx < n; ++idx) {
            target_sum -= nums[idx];
        }

        return target_sum;
    }
};

這個解法就只用 O(1) 的空間複雜度,比剛剛的解法有效率。可惜,這個解法有個缺點,你能想得出來是什麼缺點嗎?

Bitwise XOR 解法

上一個解法的缺點是,如果 n 很大(例如 n 是 INT_MAX),那 sum 就會 overflow,要特別注意。所以我們可以用另一個 Bitwise XOR 解法,這個解法利用的概念是 x ^ x = 0。所以我們可以先把 1 到 n 的所有數字都 XOR 起來,然後再跟 nums 裡面所有的數字 XOR,剩下沒被消掉的數字就是 missing number。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ans = 0, n = nums.size();
        for(int i = 0; i <= n; ++i) {
            ans ^= i;
        }

        for(int idx = 0; idx < n; ++idx) {
            ans ^= nums[idx];
        }

        return ans;
    }
};

這題寫完,大家可以再去寫寫看 Leetcode #136 - Single Number,應該可以輕鬆解出。

Cyclic Sort 解法

這題雖然簡單,不過可以用的解法滿多元的,之前我們在 Leetcode 刷題 pattern - Cyclic Sort 的第一個範例中也有介紹過這題,大家可以再去複習一下,看看你比較喜歡哪個解法。

Bitwise XOR 的第二個範例 - Leetcode #260 - Single Number III

題目

暴力法

最簡單的方法之一就是用一個 set 紀錄 nums 裡面所有的數字,如果出現兩次就從 set 裡面移除掉,最後剩下的兩個就是要找的目標,實作如下:

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unordered_set<int> s;
        for(int i = 0; i < nums.size(); ++i) {
            if(s.count(nums[i]) != 0) {
                s.erase( s.find(nums[i]) );
            }
            else {
                s.insert(nums[i]);
            }
        }

        vector<int> ans;
        while(!s.empty()) {
            ans.push_back(*s.begin());
            s.erase ( s.begin() );
        }

        return ans;
    }
};

Bitwise XOR 解法

如果我們用上一個範例的思維,會覺得這題有點難,因為只把所有的數字都 XOR 起來沒有辦法分出兩個只出現一次的數字。假設這兩個都只出現一次的數字是 num1 跟 num2。當我們把所有的數字 XOR 起來,我們就得到了 num1 ^ num2。

雖然這並不是我們要的答案,但我們如果仔細觀察 num1 ^ num2,會發現裡面一定有一個 bit 是 1,因為 num1 不等於 num2,我們把這個 bit 的位置稱為 diff。

這時候,我們可以把 nums 裡所有的數字分成兩群,一群是在第 diff 位 bit 是 1 的數字,另一群是在第 diff 位 bit 是 0 的數字,然後我們只需要分別把這兩群的數字 XOR 起來就可以得到答案!

實作如下:

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        // bitmask 最後會等於 num1 ^ num2
        int bitmask = 0;
        for(const int& num: nums) {
            bitmask ^= num;
        }

        // 取得 num1 ^ num2 是 1 的那個 bit
        int diff = bitmask & (~bitmask + 1);

        // num1 儲存在 diff 位 bit 是 1 的所有數字的 XOR 結果
        int num1 = 0;
        for(const int& num: nums) {
            if((num & diff) != 0) {
                num1 ^= num;
            }
        }

        // 因為 bitmask 是 num1^num2,bitmask^num1 == num2
        return {num1, bitmask^num1};
    }
};

Bitwise XOR 的第三個範例 - Leetcode #1009 - Complement of Base 10 Integer

題目

Bitwise XOR 解法

假設 number 是 101,那 complement 就是 010,因為他們的 bit 完全相反,所以:

number ^ complement = all_bits_set

all_bits_set 表示所有的 bit 都是 1。

如果兩邊都多 XOR 一次 number,就會變成:

number ^ number ^ complement = number ^ all_bits_set

而因為 number ^ number == 0,所以:

complement = number ^ all_bits_set

所以我們只需要先弄出 all_bits_set,再跟 number XOR 就好。

class Solution {
public:
    int bitwiseComplement(int N) {
        int mask = 1;

        while (mask < N) {
            mask = (mask << 1) + 1;
        }

        return N ^ mask;
    }
};

這題跟 Leetcode #476 - Number Complement 一模一樣,一次寫兩題!值回票價XD

總結

今天跟大家介紹了一個新的 pattern - Bitwise XOR,這 pattern 實作不難,但如果你不熟,要自己想出來可不太容易。希望大家在刷題的時候也能多掌握解題的 pattern,用一個 pattern 打掉多題,體會到隱藏在這些 pattern 後的演算法和資料結構的優美之處。

延伸閱讀

  1. Leetcode 刷題 pattern - Two Pointer
  2. Leetcode 刷題 pattern - Sliding Window
  3. Leetcode 刷題 pattern - Next Greater Element
  4. Leetcode 刷題 pattern - Fast & Slow Pointer
  5. Leetcode 刷題 pattern - Breadth-First Search
  6. Leetcode 刷題 pattern - Merge Intervals
  7. Leetcode 刷題 pattern - Cyclic Sort
  8. Leetcode 刷題 pattern - Two Heaps
  9. Leetcode 刷題 pattern - Top K elements
  10. Leetcode 刷題 pattern - Topological Sort

關於作者:
@pojenlai 演算法工程師,希望活在當下,看到本質


#Leetcode









Related Posts

Day01:從變數看 bytecode

Day01:從變數看 bytecode

MTR04_0619

MTR04_0619

Day 5 -教惠惠說話,以及使用 Firebase 資料庫

Day 5 -教惠惠說話,以及使用 Firebase 資料庫

[ week 1 ] Vim 編輯器 筆記

[ week 1 ] Vim 編輯器 筆記

Go起手式之三

Go起手式之三

Android 時間格式轉換筆記

Android 時間格式轉換筆記



Newsletter




Comments