75. Sort Colors
題目網址：https://leetcode.cn/problems/sort-colors/
題意：給一包含紅色、白色和藍色, 總共 n 個元素的 array nums, 原地對 nums 進行排序, 使得相同顏色的元素相鄰, 並按照紅、白、藍的順序排列。
分別使用 0、1、2 代表紅、白、藍。
注意：不能使用 library 中的 sort 函式。
進階：設計 $O(1)$ space 的一次掃描演算法。
Solution 1：
想法：第一次掃描先計算 0、1、2 的個數, 第二次掃描則按照個數填充 nums
class Solution {public: void sortColors(vector<int>& nums) { vector<int> colors(3, 0); for (const auto& num : nums) { ++colors[num]; } int cur = 0; ...
421. Maximum XOR of Two Numbers in an Array
題目網址：https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/
題意：給一整數 array nums, 返回 nums[i] XOR nums[j] 的最大值, 其中 0 ≤ i ≤ j < n。
進階：設計 $O(n)$ time 的演算法。
Solution：
想法：利用 Greedy + Trie
Greedy：若今天有一數 x = 5, 其 binary 形式為 0101
若跟其 bit 完全相反的 1010 存在, 則 XOR 值最大
若 1010 不存在, 我們也希望能挑選最左 bit = 1 (因為此時 5 的最左 bit = 0)的數, 並將最左 bit = 0 的數給剔除掉, 然後往下一個 bit 重複此步驟
透過逐步篩選, 最後挑出所有數中 XOR 值最大的數
首先, 將所有 num 的 binary 形式(由左至右) insert 到 trie 中
e.g. num = 4 則 insert 到 trie 中會是下圖的樣子
...
720. Longest Word in Dictionary
題目網址：https://leetcode.cn/problems/longest-word-in-dictionary/
題意：給一 string array words 組成的字典。返回 words 中最長的單字, 且該單字是由字典中其他單字逐步添加一個 char 而成的。
若其中有多個可行的答案, 則返回答案中順序最小的單字。若無答案, 則返回 empty string。
注意：words[i] 僅由小寫字母所組成。
Solution：
想法：利用 Sorting + Trie
首先, 對 words 進行 sorting, 分成兩種情況:
string 越長的放越前面
若兩 string 長度相同, 則將字母順序小的放前面 e.g. "apple" 和 "apply"：兩者都有 "appl", 但是因為 "e" 在字母的順序中比 "y" 前面, 故 "apple" 應排在 "apply" 前面
建立 Trie, 並將 word ...
76. Minimum Window Substring
題目網址：https://leetcode.cn/problems/minimum-window-substring/
題意：給兩 string s 和 t, 返回 s 中包含 t 所有 character 的最小 substring。若不存在這樣的 substring, 則返回 empty string ""。
s 和 t 由英文字母組成。
進階：設計 $O(n)$ time 的演算法。
Solution：
想法：利用 Sliding Window, 用兩個 pointer left 和 right, 其中 right 用來擴充 window, 而 left 用來收縮 window
若 window 中的元素不包含 t, 則 right 不斷向右移動, 直到 window 中每種元素的個數 ≥ t 中對應元素的個數
left 會不斷收縮, 並更新 res, 直到當 window 中某種元素的個數 < t 中該種元素的個數
have 用來記錄符合 window 中某一種元素的個數 == t 中該種元素的個數 之元素個數
need 則是記錄 t 中有多少 ...
239. Sliding Window Maximum
題目網址：https://leetcode.cn/problems/sliding-window-maximum/
題意：給一整數 array nums, 有一個大小為 k 的 sliding window 從 nums 的最左側移動到最右側。你只能看到 sliding window 中的 k 個數字, 且 sliding window 每次只向右移一位, 返回 sliding window 中的最大值。
Solution：
想法：利用 deque。因為 window 移除元素後, 有可能會改變最大值, 故也要記錄最大值之外的值。
首先, 建立遞減 Queue（Monotonic Queue）, 把當前 window 中最大值的 index 放在 deque 的最前面。
nums[i] 加入前, 要先不斷地和 deque.back() 比較
若 nums[i] > nums[deque.back()], 則 deque.pop_back()
若 nums[i] ≤ nums[deque.back()], 則將 i 放入 deque 最後面
若 window 的起始位置 ...