Leetcode

不定長的 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; } };

不定長的 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; } };

不定長的 Sliding Window 套 pattern class IWindow { public: virtual void add(char& c) = 0; virtual void erase(char& c) = 0; virtual bool check(char& c) = 0; virtual ~IWindow() {} }; class Window: public IWindow{ private: int cnt[26]; public: Window() { memset(cnt, 0, sizeof(cnt)); } void add(char& c) override { cnt[c-'a']++; } void erase(char& c) override { cnt[c-'a']--; } bool check(char& c) override { return cnt[c-'a'] == 2; } }; class Solution { private: unique_ptr<IWindow> _w; public: Solution(): _w(make_unique<Window>()) {} int maximumLengthSubstring(string s) { int n = s.size(), left = 0, right = 0; int res = 0; while (right < n) { char c = s[right++]; while (_w->check(c)) _w->erase(s[left++]); _w->add(c); res = max(res, right-left); } return res; } };

不定長度的 sliding window pattern 步驟 move sliding window (1) 滑動左指標直到 window 有效 (2) 加入右指標 (3) 更新 class Window { public: virtual void add(int num) = 0; virtual void erase(int num) = 0; virtual bool check(int num) = 0; virtual ~Window() {} }; class Solution { private: unique_ptr<Window> _w; public: Solution(): _w() {} int solve(vector<int>& nums, int k) { _w = make_unique<WindowImpl>(k); int len = 0; int n = nums.size(), left = 0, right = 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 len; } };

這是一題是很有趣的一題，會用到 bucket sort 結合 sliding window，時間複雜度是 \(O(n)\) 我把 sliding window 的部分拆分開來，讓邏輯更清楚。 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; } };

這是一題簡單的定長度 sliding window。先排序再用滑動窗口求值。時間複雜度是 \(O(n\log(n))\) class Solution { public: int minimumDifference(vector<int>& nums, int k) { sort(nums.begin(), nums.end()); int res = INT_MAX; for (int i = 0; i < nums.size() - k + 1; i++) { res = min(res, nums[i+k-1] - nums[i]); } return res; } };

這是一題簡單的定長度 sliding window。 class Solution { public: int divisorSubstrings(int num, int k) { int curr = 0; string s = to_string(num); int res = 0; for (int i = 0; i < s.size()-k+1; i++) { int div = stoi(s.substr(i, k)); if (div != 0 && num % div == 0) res++; } return res; } }; 用原本的 pattern 來做，但要注意 1e9 * 10 會爆掉，整數的範圍大概只有 2e9 (2147483647)。可改用先減再 shift 的方式處理。 class Solution { public: int divisorSubstrings(int num, int k) { int curr = 0; string s = to_string(num); int res = 0; int pk = pow(10, k-1); for (int i = 0; i < k; i++) { curr = curr * 10 + (s[i] - '0'); } if (curr != 0 && num % curr == 0) res++; for (int i = k; i < s.size(); i++) { curr = 10 * (curr - (s[i-k] - '0') * pk) + (s[i] - '0'); if (curr != 0 && num % curr == 0) res++; } return res; } };

766. Toeplitz Matrix Hardness: \(\color{green}\textsf{Easy}\) Ralated Topics: Array、Matrix 一、題目 Given an m x n matrix, return true if the matrix is Toeplitz. Otherwise, return false. A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same elements. Example 1: Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]] Output: true Explanation: In the above grid, the diagonals are: “[9]”, “[5, 5]”, “[1, 1, 1]”, “[2, 2, 2]”, “[3, 3]”, “[4]”. In each diagonal all elements are the same, so the answer is True. Example 2: ...

這一題是滿有趣的一題，我的靈感來自於 zkw 的線段樹(但沒有用到線段樹)。 觀察 1 ~ n 的樹，並將它排成 zkw 的線段樹，可以發現以下規則： 滿足樹的子葉，則必定可以滿足其父節點，例如：找到 "1010"，則可以滿足 "101"、"10"、"1"。 所以可以得到一個數學結論是：我們只需要找到 n ~ n/2+1 的數即可。 [1] len = 1 [10] 11 len = 2 100 [101] 110 111 len = 3 1000 1001 [1010] 1011 1100 1101 1110 1111 len = 4 (8) num mask ^ 1<<3 solution: class Solution { public: bool queryString(string s, int n) { if (n > 1979) return false; // 剪枝：當 n 太大時必為 false, 證明在下面 int len = 32 - __builtin_clz(n); // n 的位元長度 if (s.size() < len) return false; // s 長度連 window 都不夠時 return false int mask = (1 << len) - 1; // 遮罩 用來控制 window 長度 unordered_set<int> seen; // 用來記錄數字是否出現過 int valid = n - n/2; // 總共需要收集到的數目 // init int curr = 0; for (int i = 0; i < len; i++) { curr = ((curr << 1) | (s[i] & 1)); if (curr <= n && curr > n/2) seen.insert(curr); if (seen.size() == valid) return true; } // rolling for (int i = len; i < s.size(); i++) { curr = ((curr << 1) | (s[i] & 1)) & mask; if (curr <= n && curr > n/2) seen.insert(curr); if (seen.size() == valid) return true; } return false; } }; 剪枝的證明： 我來說明 1979 這個臨界值的計算過程： 當字串長度 = 1000 時，我們需要找到滿足以下條件的最大 n： ...

19. Remove Nth Node From End of List Hardness: \(\color{orange}\textsf{Medium}\) Ralated Topics: Linked List、Two Pointers 一、題目 Given the head of a linked list, remove the nth node from the end of the list and return its head. Example 1: Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5] Example 2: Input: head = [1], n = 1 Output: [] Example 3: Input: head = [1,2], n = 1 Output: [1] Constraints: ...