744. Find Smallest Letter Greater Than Target
題目網址:https://leetcode.cn/problems/find-smallest-letter-greater-than-target/
題意:給一 sorted char array letters, 在其中找到比 target 大的最小 char。
注意:letters 是循環的
e.g. target == 'z' 且 letters == ['a', 'b'], 則返回 'a'
Solution:
想法:利用 binary search
letters[mid] > target 時, 往左查找, 看是否有比 mid 更小的
letters[mid] <= target 時, 往右查找
最後記得檢查是否 > target, 如果不滿足(代表 letters 中沒有 > target 的 char), 則返回 letters[0]
class Solution {public: char nextGreatestLetter(vector<c ...
22. Generate Parentheses
題目網址:https://leetcode.cn/problems/generate-parentheses/
題意:數字 n 代表生成括號的對數, 生成所有可能的且有效的括號組合。
Solution:
想法:利用 DFS + Backtracking
當 左括號個數 < n 時, 可以加入左括號
當 右括號個數 < 左括號個數 時, 可以加入右括號
class Solution {public: vector<string> generateParenthesis(int n) { dfs(0, 0, n); return res; }private: string cur; vector<string> res; void dfs(const int left, const int right, const int n){ if (left == n && right == n) { ...
15. 3Sum
題目網址:https://leetcode.cn/problems/3sum/
題意:給一整數 array nums, 返回 nums 是否存在 [nums[i], nums[j], nums[k]], 使得 nums[i] + nums[j] + nums[k] == 0, 其中 i != j, i != k 且 j != k。
注意:答案中不可包含重複的 tuple。
Solution:
想法:利用 Two Pointers
首先, 將 nums 由小到大做排序
用來避免取重複的 tuple, 並可使用 two pointer 來移動 ptr
用 i 遍歷 index = [0, n - 3], 得到 nums[i]
為了避免第一次取到與上一輪相同的元素,我們需要在這裡進行一次判斷並跳過
使用 Two pointer left = i + 1, right = n - 1 尋找滿足條件的 pair
若 sum < 0 : 則 left + 1
若 sum > 0 : 則 right - 1
若 sum == 0 : 則將 tuple 加入到 res 中, ...
11. Container With Most Water
題目網址:https://leetcode.cn/problems/container-with-most-water/
題意:給一整數 array height 和一整數 n。有 n 條線其高度為 height[i], 找出其中的兩條線,使得它們與 x 軸組成的容器可以容納最多的水。
Solution:
想法:利用 Two Pointers
當前 area = 兩條線中較短的高度 * 彼此間的距離
移動較短那端的 ptr, 盡量保留較長的線
為何是移動較短那端的 ptr? 因為 area 是用下限計算的, 我們希望下限越高越好, 但是下限會受限於上限 ➔ 因此我們採取的策略為「維持上限、提升下限」
e.g. height = [1, 3, 5, 7]
最一開始 left = 0, right = 3 ➔ nums[left] = 1, nums[right] = 7此時 area = min(1, 7) * (3 - 0) = 1 * 3 = 3
若移動 right : left = 0, right = 2 ➔ nums[left] = 1, nums[ri ...
217. Contains Duplicate
題目網址:https://leetcode.cn/problems/contains-duplicate/
題意:給一整數 array nums, 判斷當中是否有重複數字。
Solution 1:
想法:先排序, 再用 loop 兩兩比較 nums[i - 1] 和 nums[i] 是否相等
class Solution {public: bool containsDuplicate(vector<int>& nums) { sort(nums.begin(), nums.end()); for (int i = 1; i < nums.size(); i++) { if (nums[i] == nums[i - 1]) { return true; } } return false; }};
time:$O(n \cdot lo ...