【Leetcode C++ 解題筆記】Divide & Conquer - part 2
===
[TOC]
本筆記僅供個人學習用途，內容斟酌參考。
## 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 就結束。
範例程式碼：
```cpp=
/**
* 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 共出現幾次：
```cpp=
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;
```
範例程式碼：
```cpp=
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。
```
Index :7 6 5 4 3 2 1 0
0 0 0 1 0 1 1 0
```
所謂反轉位元的意思就是把索引顛倒：
```
Index :0 1 2 3 4 5 6 7
0 1 1 0 1 0 0 0
```
就這樣。
範例程式碼：
```cpp=
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：
```
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。
完整範例程式碼：
```cpp=
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()` 函數去判斷，如：
```cpp=
char toggleCase(char c){
if (islower(c)) return toupper(c);
else return tolower(c);
}
```
如果 `seen.find()` 沒有找到，則回傳 `end()` 這個 iterator。
沒找到的話我們就要做遞迴去找了，這邊用分治法的概念將字串切兩半去找：
```cpp=
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`。
完整範例程式碼：
```cpp=
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);
}
};
```
Sign in with Wallet
Connect another wallet