34. Find First and Last Position of Element in Sorted Array
題目網址：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
題意：給一按照非遞減順序排列的整數array nums, 和一個整數 target。請找出給定 target 在 nums 中的開始位置和結束位置。
如果 nums 中不存在 target, 則返回 [-1, -1]。
設計 $O(log(n))$ time 的演算法。
Solution：
想法：利用 Binary Search
class Solution {public: vector<int> searchRange(vector<int>& nums, int target) { const int lower = firstPos(nums, target); const int upper = lastPos(nums, target); return {lower, uppe ...
151. Reverse Words in a String
題目網址：https://leetcode.cn/problems/reverse-words-in-a-string/
題意：給一 string s, 請你反轉 s 中單字的順序。
單字是由非空格 char 所組成的 string, s 中至少使用一空格將 string 中的單字分開。
注意：s 中可能會存在前導空格、尾隨空格 or 單字間的多個空格。返回的 output 中, 單字間應當僅用單個空格分隔, 且不包含任何額外的空格。
進階：如果 s 在你使用的語言中是可變的, 設計 $O(1)$ space 的演算法。
Solution 1：
想法：利用 Stack, 先將分割出每個 word, 並把 word 加到 stack 中, 然後再一一 pop 出來, 要注意最後一個 word 後面不能有空格
class Solution {public: string reverseWords(string s) { const int n = s.size(); stack<string> stk; // 讓後面 ...
701. Insert into a Binary Search Tree
題目網址：https://leetcode.cn/problems/insert-into-a-binary-search-tree/
題意：給一 BST 的 root 和要插入的值 val, 返回插入後 BST 的 root, BST 中所有的 node.val 皆為獨一無二的。
注意：可能存在多種有效的插入方式, 返回任意一種即可。
Solution 1：
想法：利用 DFS
class Solution {public: TreeNode* insertIntoBST(TreeNode* root, int val) { if (!root) { return new TreeNode(val); } if (val > root->val) { root->right = insertIntoBST(root->right, val); } else { ...
450. Delete Node in a BST
題目網址：https://leetcode.cn/problems/delete-node-in-a-bst/
題意：給一 BST 的 root 和一個值 key, 刪除 BST 中的 key 對應的 node, 並保證 BST 的性質不變。返回刪除後 BST 的 root。
一般來說，刪除 node 可分為兩個步驟：
首先找到需要刪除的 node
如果找到了, 則刪除它
Solution：
想法：利用 DFS
若 key > root->val, 則去右子樹中刪除
若 key < root->val, 則去左子樹中刪除
若 key == root->val, 則分為以下三種情況：
若 root 無左子, 則 root 的右子頂替其位置
若 root 無右子, 則 root 的左子頂替其的位置
若 root 左右子都有, 則將其左子樹轉移到其右子樹的最左 node (也就是右子樹中最小的 node) 的左子樹上, 然後 root 的右子樹頂替其位置
class Solution {public: TreeN ...
189. Rotate Array
題目網址：https://leetcode.cn/problems/rotate-array/
題意：給一 array nums, 將其往右旋轉 k 次, 其中 k 為非負整數。
Solution 1：
想法：用額外的 array 來記住原本的 nums 來進行旋轉, 由於 k 有可能會大於 n, 所以先將 k 做 mod 運算
e.g. nums = [1, 2, 3], k = 4, 其實 k 等價於 4 % 3 = 1
class Solution {public: void rotate(vector<int>& nums, int k) { const int n = nums.size(); const vector<int> tmp = nums; k %= n; for (int i = 0; i < n; ++i) { nums[(i + k) % n] = tmp[i]; } & ...