Leetcode 刷題 pattern - Bitwise XOR

前言

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

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

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

Bitwise XOR 簡介

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

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

題目

暴力法

最簡單的方法之一就是用一個 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 一模一樣，一次寫兩題！值回票價ＸＤ

總結

今天跟大家介紹了一個新的 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 演算法工程師，希望活在當下，看到本質。