【Leetcode C++ 解題筆記】Divide & Conquer - part 2

本筆記僅供個人學習用途，內容斟酌參考。

1. Convert Sorted Array to Binary Search Tree

Problem Source：https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/?envType=problem-list-v2&envId=divide-and-conquer

難度：Easy

題意大致上就是要你把一般常見的陣列轉換成 BST。

補充一下 BST 特性：

  • 左子樹的 Nodes 都比 Root 還小；反之，右子樹都比 Root 還大。
  • 子樹必須都是 BST。

解題思路：

用到 Divide & Conquer 的概念，每次把「目前」陣列片段選中間元素作為 root。

對 root 左側遞迴呼叫產生左子樹，右側也一樣，直到子陣列長度為 0 就結束。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return buildBST(nums, 0, nums.size() - 1);
    }
private:
    TreeNode* buildBST(vector <int>& nums, int left, int right){
        if (left > right) return nullptr;
        int mid = left + (right - left) / 2;
        TreeNode* node = new TreeNode(nums[mid]); // root
        node -> left = buildBST(nums, left, mid - 1);
        node -> right = buildBST(nums, mid + 1, right);
        return node;
    }
};

2. Majority Element

Problem Source：https://leetcode.com/problems/majority-element/description/?envType=problem-list-v2&envId=divide-and-conquer

難度：Easy

題目敘述：

給定長度為 n 的陣列 nums，回傳多數元素（the majority element）。

所謂多數元素就是元素出現超過 [n / 2] 次。你可以假設它都會出現在陣列中。

解題思路：

用 Divide & Conquer 做這題，一樣是二分法去做，主要處理 [left, mid] 和 [mid + 1, right] 這兩段區間。

終止條件是 if (left == right) return nums[left]; 表示元素個數剩一個，該元素必為多數元素，故回傳此值。

遞迴處理 lm 和 rm 的部分（左右區間）。

之後做合併動作，也直接做判斷：if (lm == rm) return lm; 表示左右多數元素相同。

如果不同，就需要去數 lm 跟 rm 共出現幾次：

1
2
3
int c1 = count(nums.begin() + left, nums.begin() + right + 1, lm);
int c2 = count(nums.begin() + left, nums.begin() + right + 1, rm);
return c1 > c2 ? lm : rm;

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        return majority(nums, 0, nums.size() - 1);
    }
    int majority(vector <int>& nums, int left, int right){
        if (left == right) return nums[left];
        int mid = left + (right - left) / 2;
        int lm = majority(nums, left, mid);
        int rm = majority(nums, mid + 1, right);
        if (lm == rm) return lm;
        int c1 = count(nums.begin() + left, nums.begin() + right + 1, lm);
        int c2 = count(nums.begin() + left, nums.begin() + right + 1, rm);
        return c1 > c2 ? lm : rm; 
    }
};

3. Reverse Bits

Problem Source：https://leetcode.com/problems/reverse-bits/description/?envType=problem-list-v2&envId=divide-and-conquer

難度：Easy

題目敘述：

反轉 32 位元的偶數有號整數（uint）。

先以 8 位元舉例比較好懂，32 位元太長了。

假設原本數字是 0 0 0 1 0 1 1 0，二進位是從右開始為起始索引，最左邊是最終索引 7。

1
2
Index :7 6 5 4 3 2 1 0
       0 0 0 1 0 1 1 0

所謂反轉位元的意思就是把索引顛倒：

1
2
Index :0 1 2 3 4 5 6 7
       0 1 1 0 1 0 0 0

就這樣。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        n = (n >> 16) | (n << 16);
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
        return n;
    }
};

基本上這段程式碼就是不斷將 n 切割成兩部分，並且作互換（用 | OR 運算子互換）的動作，以此來達到反轉位元的效果。

4. Number of 1 Bits

Problem Source：https://leetcode.com/problems/number-of-1-bits/description/?envType=problem-list-v2&envId=divide-and-conquer

難度：Easy

題目敘述：

給定一個正整數 n，寫一個函數回傳其二進位表示法中的設定位數（也稱為漢明權重）。

set bits 指的是有 1 的位元數量，如 1011 就有 3 個 set bits，這個也稱為 Hamming weight。

範例程式碼講解：

雖然有 std::popcount（C++ 20） 或 __builtin_popcount()（看編譯器支不支援）可以用，但上述兩種方法若在某些競賽上使用可能不切實際。

所以我們來手刻一下 popcount。

在細講這個演算法之前，我們要先知道幾個 bitmasks：

1
2
3
4
0x55 = 01010101
0x33 = 00110011
0x0f = 00001111
0xff = 11111111

第一行（n = (n & 0x55555555) + ((n >> 1) & 0x55555555);）用到 bitmasks 0x55，挑出 n 中所有在奇數位（bit 0, 2, 4, …）的 bit，再把 n 右移 1 位後（偶數位），也用相同遮罩挑出偶數位 bit，最後兩者相加。

這一層分治主要將 32 個 bit 分成 16 組，每組 2bit。

第二行（n = (n & 0x33333333) + ((n >> 2) & 0x33333333);）用到 bitmasks 0x33，將剛才算好的每 2bit 組做累加操作，把相鄰的兩個 2bit 組合成一個 4bit 組並累加 1 的數量。

然後這層分治也將 32bit 分成 8 組，每組 4bit，計算每組內 1 的個數。

第三行（n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);）用到 bitmasks 0x0f，將相鄰的兩個 4bit 組合成一個 8bit 組，同樣使用 bitmasks 分低 4bit 及高 4bit 相加。

該層分治再把 32bit 分成 4 組，每組 8bit，計算每組內 1 的個數。

第四行（n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);）也用到一樣的 bitmasks，只不過多加個 f，在二進位上就多了四個 f。

這層分治把將相鄰兩個 8bit 組合成 1 個 16bit 組，再累加各 8bit 中 1 的個數。

第五行（n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);）用到最後一個 bitmasks 0xff，將兩個 16bit 組合成整個 32bit 的組合，再將前後 16bit 中 1 的個數合併。

最終我們就從 32 bit 裡面得到所有 1 的數量了，為什麼是 32 bit 呢？因為題目要求 int，int 就剛好 32 bit。

完整範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int hammingWeight(int n) {
        n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
        n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
        n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
        n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
        n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);
        return n;
    }
};

5. Longest Nice Substring

Problem Source：https://leetcode.com/problems/longest-nice-substring/description/?envType=problem-list-v2&envId=divide-and-conquer

難度：Easy

題目敘述：

一字串 s 如果是 nice，那對於每個字母表中的每個字母都包含 s，它以大寫和小寫形式出現。

舉例來說，"abABB" 是 nice，因為 'A' 和 'a' 出現，並且 'B' 和 'b' 出現。然而，"abA" 不是 nice，因為 'b' 出現，而 'B' 沒有出現。

給定一個字串 s，回傳 s 中最長的、滿足 nice 條件的子字串。如果有多個，則回傳最早出現的子字串。如果沒有，則傳回空字串。

解題思路：

我們用資料結構 unordered_set <int> seen(s.begin(), s.end()); 來實作這題。

首先跑迴圈，內部判斷一個字串中的字元 c 有沒有其他相反的大小寫，如 A 要找到對應的小寫 a 才是一個 nice substring。（這邊要找他對應相反的大小寫，我們用 seen.find() 去找）

大小寫判斷可以額外寫一個 toggleCase() 函數去判斷，如：

1
2
3
4
char toggleCase(char c){
    if (islower(c)) return toupper(c);
    else return tolower(c);
}

如果 seen.find() 沒有找到，則回傳 end() 這個 iterator。

沒找到的話我們就要做遞迴去找了，這邊用分治法的概念將字串切兩半去找：

1
2
string left = longestNiceSubstring(s.substr(0, i));
string right = longestNiceSubstring(s.substr(i + 1));

substr(0, i) 為從索引 0 開始，擷取長度 i 的子字串（不含索引 i 的字元），形成左半邊的子字串。

substr(i + 1) 從索引 i + 1 開始，擷取到字串尾的子字串，形成右半邊子字串。

最後回傳較長的子字串：return left.size() >= right.size() ? left : right。

最後的最後，如果我們前面判斷都沒有回傳 end() 的話，那就表示說整串字串完美符合 nice substring 的條件，就直接 return s。

完整範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string longestNiceSubstring(string s) {
        if (s.length() < 2) return "";
        
        unordered_set <char> seen(s.begin(), s.end());

        for (int i = 0; i < (int)s.length(); ++i){
            if (seen.find(toggleCase(s[i])) == seen.end()){
                string left = longestNiceSubstring(s.substr(0, i));
                string right = longestNiceSubstring(s.substr(i + 1));
                return left.size() >= right.size() ? left : right;
            }
        }
        return s;
    }
private:
    char toggleCase(char c){
        if (islower(c)) return toupper(c);
        else return tolower(c);
    }
};