簡單的不定長 sliding window 問題。 class Solution { public: int longestOnes(vector<int>& nums, int k) { int res = 0, left = 0, right = 0, n = nums.size(); int curr = 0; int cnt = 0; while (right < n) { int num = nums[right++]; while (cnt == k && num == 0) { if (nums[left++] == 0) cnt--; } if (num == 0) cnt++; res = max(res, right-left); } return res; } };
簡單的不定長 sliding window 問題, 正反各做一遍即可。 class Solution { private: int maxConsecutiveAnswersWith(string keys, int k, char c) { int left = 0, right = 0, res = 0, n = keys.size(); int cnt = 0; while (right < n) { char key = keys[right++]; while (key == c && cnt == k) { if (keys[left++] == c) { cnt--; } } if (key == c) cnt++; res = max(res, right-left); } return res; } public: int maxConsecutiveAnswers(string answerKey, int k) { return max(maxConsecutiveAnswersWith(answerKey, k, 'T'), maxConsecutiveAnswersWith(answerKey, k, 'F')); } };
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: ...
將陣列經過排序後，就變成一個簡單的 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; } };
套不定長的 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; } };
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: ...
套不定長的 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; } };
套不定長的 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; } };
先將 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; } };
不定長的 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; } };