704. Binary Search
題目網址：https://leetcode.cn/problems/binary-search/
題意：給一已排序的整數 array nums, 用 binary search 找出 nums 中是否存在 target。若存在, 則返回該元素的 idx；否則, 返回 -1。
Solution：
想法：利用 Binary Search, 找到 left 為第一個 ≥ target 的數。若 left 越界 or nums[left] != target, 則代表 target 不存在於 nums 中
class Solution {public: int search(vector<int>& nums, int target) { const int n = nums.size(); int left = 0, right = n; while (left < right) { const int mid = left + (right - left) ...
70. Climbing Stairs
題目網址：https://leetcode.cn/problems/climbing-stairs/
題意：今天有 n 階樓梯要爬, 每一次你可以選擇要爬 1階 or 2階, 求總共有幾種不同的爬法。
Solution 1：（TLE 無法通過）
想法：利用遞迴求解
class Solution {public: int climbStairs(int n) { if (n <= 2) { return n; } return climbStairs(n - 1) + climbStairs(n - 2); }};
time complexity 證明：
T(n) = T(n - 1) + T(n - 2) + c <= 2T(n - 1) + c, 取 upper bound T(n - 2) <= T(n - 1) = 2*(2T(n - 2) + 1) + (1 * c) = 4T(n - 2 ...
543. Diameter of Binary Tree
題目網址：https://leetcode.cn/problems/diameter-of-binary-tree/
題意：給一 BT, 求任兩點的 path 之最大長度。
最大長度：最長 path 上的 edge 數
Solution：
想法：利用 DFS, LP(node) 返回以 node 為 root 的 subtree 之最長路徑, 只有當前 node 可以同時使用左子樹和右子樹（由左至右分別是 1, 2, 1）, 也就是計算 res 時可用, 但返回時只能 return 單邊路徑。由於 path 不一定要經過 root, 因此可用 global 變數 res 來記錄最長 path 之長度
class Solution {public: int diameterOfBinaryTree(TreeNode* root) { res = 0; LP(root); return res; }private: int res; int LP(TreeNode* root)&# ...
150. Evaluate Reverse Polish Notation
題目網址：https://leetcode.cn/problems/evaluate-reverse-polish-notation/
題意：給一 postorder, 返回 inorder 的運算結果。
保證 postorder 運算式皆為有效的, 不會有除數為 0 的情況。
Solution：
想法：利用 Stack, 一旦當前 token 為數字, 則 push 到 stack 中; 否則, 取出 stack 中最上面的兩個 top 元素出來做運算, 並把運算結果 push 到 stack 中。重複以上步驟, 最後 stack 會剩下一個元素, 也就是最終的運算結果
class Solution {public: int evalRPN(vector<string>& tokens) { for (const auto& token : tokens) { if (isdigit(token)) { stk.emplace(stoi( ...
448. Find All Numbers Disappeared in an Array
題目網址：https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array/
題意：原本有一包含 [1, n] 總共 n 個數的 array, 今給一個 n 個數的 array (含重複數) nums, 找出所有缺失的數。
Solution：
想法：將數字設為 負數 來標記我們看到的數字的 index, 然後遍歷 nums 元素, 若 nums[i] > 0, 代表數字 i + 1 沒出現過
e.g. [1, 2, 2] ➔ [-1, -2, 2], 其中 nums[0] 紀錄數字 1 是否出現
因為數字 1 有出現, 所以 nums[0] 被設為負數, 依此類推
class Solution {public: vector<int> findDisappearedNumbers(vector<int>& nums) { // 將數字設為負數來標記我們看到的數字的index for (const auto& ...