128. Longest Consecutive Sequence
題目網址：https://leetcode.cn/problems/longest-consecutive-sequence/
題意：給一未排序的 array nums, 找出數字連續的最長 sequence（sequence 元素不需在 nums 中位置連續）。
注意：請設計 $O(n)$ time 的演算法
Solution：
想法：將 nums 視覺化發現, 每個 sequence 形成的首要條件就是開頭的數左邊沒有數, 結尾的數右邊沒有數
class Solution {public: int longestConsecutive(vector<int>& nums) { int res = 0; unordered_set<int> s(nums.begin(), nums.end()); for (const auto& num : nums) { // 判斷左邊的數有無在 hash table 中 if ...
424. Longest Repeating Character Replacement
題目網址：https://leetcode.cn/problems/longest-repeating-character-replacement/
題意：給一 string s 和一整數 k, 你可以選擇將 s 中的任意字元變成其他大寫英文字母, 該操作最多執行 k 次。
經上述操作後, 返回僅包含相同字元的最大 substring 長度。
s 由大寫英文字母所組成。
Solution 1：
想法：利用 Sliding Window, 將 window 中的元素分成兩部分
出現頻率最多的元素
扣掉出現頻率最多的元素後，所剩餘的元素
若剩餘的元素個數 ≤ k, 代表剩餘的元素可全部替換為頻率最多的元素。反之, 則不行。做完後, 更新 res
class Solution {public: int characterReplacement(string s, int k) { int left = 0, right = 0, res = 0; vector<int> window(26, 0); ...
169. Majority Element
題目網址：https://leetcode.cn/problems/majority-element/
題意：給一大小為 n 的 array nums, 找出當中個數大於 $⌊ \dfrac{n}{2} ⌋$ 的數字(保證存在一個數滿足此條件)。
進階：試著用 $O(n)$ time, $O(1)$ space 的演算法解決此問題
Solution 1：
想法：利用 hash table 紀錄 {num: count}
class Solution {public: int majorityElement(vector<int>& nums) { int res = 0, maxCount = 0; unordered_map<int, int> umap; for (const auto& n : nums) { ++umap[n]; if (umap[n] > maxCount) ...
3. Longest Substring Without Repeating Characters
題目網址：https://leetcode.cn/problems/longest-substring-without-repeating-characters/
題意：給一 string s, 返回一沒有重複 char 的最長 substring 的長度。
Solution：
想法：利用 Sliding Window, 類似 424. Longest Repeating Character Replacement, 每次檢查 s[right] 是否已經在 visited 中
若是, 則移除 s[left], 且 left + 1, 直到 visited 中不存在 s[right]
將 s[right] 加入到 visited 中
更新 res
class Solution {public: int lengthOfLongestSubstring(string s) { int left = 0, res = 0; unordered_set<char> visited; for (int r ...
104. Maximum Depth of Binary Tree
題目網址：https://leetcode.cn/problems/maximum-depth-of-binary-tree/
題意：給一 BT, 求 root-to-leaf 的 path 之最大長度(tree 的最大深度)。
最大長度：path 上的 node 數
Solution 1：
想法：利用 DFS
class Solution {public: int maxDepth(TreeNode* root) { if (!root) { return 0; } return 1 + max(maxDepth(root->left), maxDepth(root->right)); }};
time：$O(n)$ ➔ 遍歷整個 BT
space：$O(n)$ ➔ worse case : skew tree, 遞迴深度為 n
Solution 2：
想法：利用 BFS
class Solution {pu ...