Zako's Blog

題目網址：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 ...

題目網址：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) { ...

題目網址：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 中， ...

題目網址：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 ...

題目網址：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 ...