Leetcode

不定長的 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: ...

1293. Shortest Path in a Grid with Obstacles Elimination Hardness: \(\color{red}\textsf{Hard}\) Ralated Topics: Array、Breadth-First Search、Matrix 一、題目 You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacles). You can move up, down, left, or right from and to an empty cell in one step. Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right conrer m-1, n-1 given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1. ...

難度分: 2449 這題是一個定長的 sliding window，比較難想的是 window size 是 k * 1, k * 2, … 到 k * 26，因為只有 26 個英文字母，所以最多只可能到 26 * k 的長度。 額外需要檢查相鄰的字母是否距離 <= 2，我使用的方法是找到一個 j 記錄最大的不符合的索引值，所以直要 window 不包含該 j，window 內的所字元都會滿足。 所以 pesudo code 會是 for (int c = 1; c <= 26; i++) { // window size int windowSize = c * k; // construct window for (int i = 0; i < windowSize; i++) { // 處理 j // 計算進入 window } // 確認初始的 window 是否滿足 // rolling windo for (int i = windowSize; i < n; i++) { // 處理 j // 計算進入 window // 計算離開 window // 確認 window 是否滿足 } } class Solution { public: int countCompleteSubstrings(string s, int k) { int n = s.size(); int res = 0; for (int idx = 1; idx <= 26 && idx * k <= n; idx++) { int len = idx * k; int j = -1; vector<int> cnt(26, 0); int valid = 0; for (int i = 0; i < len; i++) { if (i > 0 && abs(s[i] - s[i-1]) > 2) { j = i-1; } if (++cnt[s[i]-'a'] == k) valid++; } if (valid == idx && j < 0) { res++; } for (int i = len; i < n; i++) { if (abs(s[i] - s[i-1]) > 2) { j = i-1; } if (++cnt[s[i]-'a'] == k) valid++; if (cnt[s[i-len]-'a']-- == k) valid--; if (valid == idx && i-len >= j) { res++; } } } return res; } };