153. Find Minimum in Rotated Sorted Array
題目網址: https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/
題意: 給一長度為 n 的 array, 已照升序排列, 經過 1 到 n 次旋轉後得到 input array。
e.g. nums = [0,1,2,4,5,6,7] 經過變化後可得到:
若旋轉 4 次, 可得到 [4,5,6,7,0,1,2]
若旋轉 7 次, 可得到 [0,1,2,4,5,6,7]
給一元素互不相同的 array nums, 已照升序排列, 並進行多次旋轉, 返回 nums 中最小的元素。
注意: 請設計 $O(log(n))$ time 的演算法
Solution：
想法：利用 Binary Search, 根據比較左、中、右三個位置的值來縮小左邊界 or 右邊界, 有以下幾種情況：
(左 < 中) 且 (中 < 右), e.g. [1,2,3,4,5]。代表沒有旋轉 ➔ min 在左半邊, 故縮小右邊界。
(左 > 中) 且 (中 < 右), e.g. [5,1,2,3,4]。代 ...
637. Average of Levels in Binary Tree
題目網址：https://leetcode.cn/problems/average-of-levels-in-binary-tree/
題意：給一 Binary Tree(BT), 計算每一層的平均值。
Solution：
想法：利用 BFS
class Solution {public: vector<double> averageOfLevels(TreeNode* root) { if (!root) { return {}; } vector<double> res; queue<TreeNode*> q; q.push(root); while (!q.empty()) { const int size = q.size(); double sum = 0; for (int i = 0 ...
844. Backspace String Compare
題目網址：https://leetcode.cn/problems/backspace-string-compare/
題意：給兩個 string s, t, 其中的 # 代表 退格(backspace)字元, 求兩字串是否相等。
Solution：
想法：利用 two pointers, 其中 slowindex 負責 in-place 記錄新的 string, 而 fastindex 負責遍歷整個 string
class Solution {public: bool backspaceCompare(string s, string t) { return build(s) == build(t); }private: string build(string s){ int slowindex = 0; for (int fastindex = 0; fastindex < s.size(); ++fastindex) { if (s[ ...
110. Balanced Binary Tree
題目網址：https://leetcode.cn/problems/balanced-binary-tree/
題意：給一 BT, 判斷它是否 height-balanced。
height-balanced 的定義：BT 中每個 node 的左、右子樹的高度差不超過 1。
Solution：
想法：利用 DFS, 如果當前 node 的左、右子樹的高度差不超過 1, 且左、右子樹皆為 height-balanced, 則返回 true
class Solution {public: bool isBalanced(TreeNode* root) { if (!root) { return true; } const int left = height(root->left); const int right = height(root->right); return abs(left - right) <= 1 & ...
121. Best Time to Buy and Sell Stock
題目網址：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
題意：給一 array prices, 從左到右分別是每天的股票價格, 求如何買賣可以獲得最大的利潤。
注意：買入的天數必須在賣出的天數之前。
Solution：
想法：利用 Greedy, 紀錄前 i - 1 天的最大利潤、最小價格, 然後計算第 i 天的利潤並比較
class Solution {public: int maxProfit(vector<int>& prices) { int res = 0; // 紀錄前 (i - 1) 天的最大利潤 int minPrice = prices[0];// 紀錄前 (i - 1) 天的最小價格 for (int i = 1; i < prices.size(); ++i) { res = max(res, prices[i] - minPrice); ...