[LeetCode] 20. Valid Parentheses

20. Valid Parentheses Hardness: \(\color{green}\textsf{Easy}\) Ralated Topics: String、Stack 一、題目 Given a string s containing just the characters (, ), {, }, [ and ], determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type. Example 1: ...

November 1, 2022 · 1 分鐘 · Rain Hu

[LeetCode] 2779. Maximum Beauty of an Array After Applying Operation

將陣列經過排序後,就變成一個簡單的 sliding window 問題 class Solution { public: int maximumBeauty(vector<int>& nums, int k) { sort(nums.begin(), nums.end()); int res = 0, left = 0, right = 0, n = nums.size(); while (right < n) { int num = nums[right++]; while (num - nums[left] > 2 * k) left++; res = max(res, right - left); } return res; } };

November 1, 2022 · 1 分鐘 · Rain Hu

[LeetCode] 2958. Length of Longest Subarray With at Most K Frequency

套不定長的 Sliding Window pattern class IWindow { public: virtual void add(int& num) = 0; virtual void erase(int& num) = 0; virtual bool check(int& num) = 0; virtual ~IWindow() {} }; class Window: public IWindow { private: int _t; unordered_map<int,int> _map; public: Window(int threshold): _t(threshold) {} void add(int& num) override { _map[num]++; } void erase(int& num) override { _map[num]--; } bool check(int& num) override { return _map[num] == _t; } }; class Solution { private: unique_ptr<IWindow> _w; public: int maxSubarrayLength(vector<int>& nums, int k) { _w = make_unique<Window>(k); int n = nums.size(); int left = 0, right = 0, res = 0; while (right < n) { int num = nums[right++]; while (_w->check(num)) _w->erase(nums[left++]); _w->add(num); res = max(res, right-left); } return res; } }; 不囉嗦版 class Solution { private: unordered_map<int,int> cnt; public: int maxSubarrayLength(vector<int>& nums, int k) { int n = nums.size(), left = 0, right = 0, res = 0; while (right < n) { int num = nums[right++]; while (cnt[num] == k) { cnt[nums[left++]]--; } cnt[num]++; res = max(res, right - left); } return res; } };

November 1, 2022 · 1 分鐘 · Rain Hu

[LeetCode] 1706. Where Will the Ball Fall

1706. Where Will the Ball Fall Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Array、Dynamic Programming、Depth-First Search、Matrix、Simulation 一、題目 You have a 2-D grid of size m x n representing a box, and you have n balls. The box is open on the top and bottom sides. Each cell in the box has a diagonal board spanning two corners of the cell that can redirect a ball to the right or to the left. A board that redirects the ball to the right spans the top-left corner to the bottom-right corner and is represented in the grid as 1. A board that redirects the ball to the left spans the top-right corner to the bottom-left corner and is represented in the grid as -1. We drop one ball at the top of each column of the box. Each ball can get stuck in the box or fall out of the bottom. A ball get stuck if it hits a “V” shaped pattern between two boards or if a board redirects the ball into either wall of the box. Return an array answer of size n where answer[i] is the column that the ball falls out of at the bottom after dropping the ball from the ith column at the top, or -1 if the ball gets stuck in the box. Example 1: ...

November 1, 2022 · 4 分鐘 · Rain Hu

[LeetCode] 1695. Maximum Erasure Value

套不定長的 Sliding Window pattern class IWindow { public: virtual void add(int& num) = 0; virtual void erase(int& num) = 0; virtual bool check(int& num) = 0; virtual int sum() = 0; virtual ~IWindow() {} }; class Window: public IWindow { private: unordered_map<int,int> _cnt; int curr = 0; public: void add(int& num) override { curr += num; _cnt[num]++; } void erase(int& num) override { curr -= num; _cnt[num]--; } bool check(int& num) override { return _cnt[num] == 1; } int sum() override { return curr; } }; class Solution { private: unique_ptr<IWindow> _w; public: Solution(): _w(make_unique<Window>()) {} int maximumUniqueSubarray(vector<int>& nums) { int n = nums.size(); int left = 0, right = 0; int res = 0; unordered_map<int,int> map; while (right < n) { int num = nums[right++]; while (_w->check(num)) { _w->erase(nums[left++]); } _w->add(num); res = max(res, _w->sum()); } return res; } }; 不囉嗦版 class Solution { public: int maximumUniqueSubarray(vector<int>& nums) { int n = nums.size(); int left = 0, right = 0; int res = 0; int curr = 0; unordered_map<int,int> map; while (right < n) { int num = nums[right++]; while (map[num] == 1) { int num2 = nums[left++]; map[num2]--; curr -= num2; } map[num]++; curr += num; res = max(res, curr); } return res; } };

November 1, 2022 · 1 分鐘 · Rain Hu

[LeetCode] 904. Fruit Into Baskets

套不定長的 Sliding Window pattern class IWindow { public: virtual void add(int& num) = 0; virtual void erase(int& num) = 0; virtual bool check(int& num) = 0; virtual ~IWindow() {} }; class Window: public IWindow { private: int _types; unordered_map<int,int> _map; int _curr; public: Window(int types): _types(types) { _curr = 0; } void add(int& num) override { if (_map[num]++ == 0) { _curr++; } } void erase(int& num) override { if (--_map[num] == 0) { _map.erase(num); _curr--; } } bool check(int& num) override { return !_map.count(num) && _curr == _types; } }; class Solution { private: unique_ptr<IWindow> _w; public: Solution(): _w(make_unique<Window>(2)) {} int totalFruit(vector<int>& fruits) { int n = fruits.size(); int left = 0; int right = 0; int res = 0; while (right < n) { int num = fruits[right++]; while (_w->check(num)) _w->erase(fruits[left++]); _w->add(num); res = max(res, right-left); } return res; } }; 不囉嗦版 class Solution { public: int totalFruit(vector<int>& fruits) { int n = fruits.size(); int left = 0, right = 0; int res = 0; int curr = 0; unordered_map<int,int> map; while (right < n) { int num = fruits[right++]; while (curr == 2 && !map.count(num)) { int num2 = fruits[left++]; if (--map[num2] == 0) { map.erase(num2); curr--; } } if (map[num]++ == 0) { curr++; } res = max(res, right-left); } return res; } };

November 1, 2022 · 2 分鐘 · Rain Hu

[LeetCode] 2730. Find the Longest Semi-Repetitive Substring

先將 s 轉成 prefix 再套不定長的 Sliding Window 套 pattern class Solution { public: int longestSemiRepetitiveSubstring(string s) { int n = s.size(); auto trans = [&](string& s) -> vector<int> { vector<int> res{0}; for (int i = 1; i < n; i++) { res.push_back(s[i-1] == s[i] ? res.back() + 1 : res.back()); } return res; }; auto nums = trans(s); int left = 0, right = 0, res = 0; while (right < n) { int num = nums[right++]; while (num - nums[left] > 1) left++; res = max(res, right-left); } return res; } }; 不用先轉直接處理 class Solution { public: int longestSemiRepetitiveSubstring(string s) { int n = s.size(); auto check = [&](int i) -> bool { if (i == 0) return false; return s[i] == s[i-1]; }; int left = 0, right = 0, res = 0; int curr = 0; while (right < n) { if (check(right++)) curr++; while (curr > 1) { if (check(++left)) curr--; } res = max(res, right-left); } return res; } }; 左指針快進版 class Solution { public: int longestSemiRepetitiveSubstring(string s) { int n = s.size(); auto check = [&](int i) -> bool { if (i == 0) return false; return s[i] == s[i-1]; }; int left = 0, right = 0, res = 0; int last = 0; while (right < n) { bool flag = check(right++); if (flag) { left = last; last = right-1; } res = max(res, right-left); } return res; } };

November 1, 2022 · 2 分鐘 · Rain Hu

[LeetCode] 1208. Get Equal Substrings Within Budget

不定長的 Sliding Window 套 pattern class IWindow { public: virtual void add(int num) = 0; virtual void erase(int num) = 0; virtual bool check() = 0; virtual ~IWindow() {} }; class Window: public IWindow { private: int _maxCost; int _curr = 0; public: Window(int maxCost): _maxCost(maxCost) {} void add(int num) override { _curr += num; } void erase(int num) override { _curr -= num; } bool check() override { return _curr > _maxCost; } }; class Solution { private: unique_ptr<IWindow> _w; public: int equalSubstring(string s, string t, int maxCost) { auto nums = [&](int i) -> int { return abs(s[i] - t[i]); }; _w = make_unique<Window>(maxCost); int n = s.size(), left = 0, right = 0; int res = 0; while (right < n) { _w->add(nums(right++)); while (_w->check()) _w->erase(nums(left++)); res = max(res, right - left); } return res; } }; 簡易版 class Solution { public: int equalSubstring(string s, string t, int maxCost) { int curr = 0; int n = s.size(), left = 0, right = 0; int res = 0; while (right < n) { curr += abs(s[right] - t[right]); right++; while (curr > maxCost) { curr -= abs(s[left] - t[left]); left++; } res = max(res, right - left); } return res; } };

November 1, 2022 · 1 分鐘 · Rain Hu

[LeetCode] 1493. Longest Subarray of 1's After Deleting One Element

不定長的 Sliding Window 套 pattern class IWindow { public: virtual void add(int& num) = 0; virtual void erase(int& num) = 0; virtual bool check(int& num) = 0; virtual ~IWindow() {} }; class Window : public IWindow { private: int cnt = 0; public: Window() {} void add(int& num) override { if (num == 0) cnt++; } void erase(int& num) override { if (num == 0) cnt--; } bool check(int& num) override { return num == 0 && cnt == 1; } }; class Solution { private: unique_ptr<IWindow> _w; public: Solution(): _w(make_unique<Window>()) {} int longestSubarray(vector<int>& nums) { int n = nums.size(), left = 0, right = 0; int res = 0; while (right < n) { int num = nums[right++]; while (_w->check(num)) _w->erase(nums[left++]); _w->add(num); res = max(res, right-left-1); } return res; } }; 但其實在 check & 移動左指標這一步可以做優化,左指標可以透過記錄一下一個合法的位置來快速移動。 class Solution { private: int last = 0; public: int longestSubarray(vector<int>& nums) { int n = nums.size(), left = 0, right = 0; int res = 0; while (right < n) { int num = nums[right++]; if (num == 0) { left = last; last = right; } res = max(res, right-left-1); } return res; } };

November 1, 2022 · 1 分鐘 · Rain Hu

[LeetCode] 3. Longest Substring Without Repeating Characters

不定長的 Sliding Window 的 pattern 如下 class Window { public: virtual void add(int num) = 0; virtual void erase(int num) = 0; virtual bool find(int num) = 0; virtual ~Window() {} }; class Bucket : public Window { private:c int _bucketSize; int _valueDiff; int index(int num) { return num < 0 ? (num - _valueDiff) / _bucketSize : num / _bucketSize; } unordered_map<int,int> _map; public: Bucket(int valueDiff): _valueDiff(valueDiff), _bucketSize(valueDiff + 1) {} void add(int num) override { int idx = index(num); _map[idx] = num; } void erase(int num) override { int idx = index(num); _map.erase(idx); } bool find(int num) override { int idx = index(num); return _map.count(idx) || (_map.count(idx-1) && num - _map[idx-1] <= _valueDiff) || (_map.count(idx+1) && _map[idx+1] - num <= _valueDiff); } }; class Solution { private: unique_ptr<Window> _w; public: bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) { int n = nums.size(); int k = indexDiff + 1; _w = make_unique<Bucket>(valueDiff); for (int i = 0; i < k && i < n; i++) { if (_w->find(nums[i])) return true; _w->add(nums[i]); } for (int i = k; i < n; i++) { _w->erase(nums[i-k]); if (_w->find(nums[i])) return true; _w->add(nums[i]); } return false; } }; 沒有抽象化的 code class Solution { public: bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { int n = nums.size(); unordered_map<int,int> map; k++; for (int i = 0; i < n; i++) { int idxin = nums[i] / (t+1); if (nums[i] < 0) idxin--; if (i >= k) { int idxout = nums[i-k] / (t+1); if (nums[i-k] < 0) idxout--; map.erase(idxout); } if (map.count(idxin) || (map.count(idxin-1) && nums[i] - map[idxin-1] <= t) || (map.count(idxin+1) && map[idxin+1] - nums[i] <= t)) return true; map[idxin] = nums[i]; } return false; } };

November 1, 2022 · 2 分鐘 · Rain Hu