Leetcode

難度分: 1553 定長度的 sliding window，搭配對 window 檢查是否滿足條件 class Solution { public: long long maximumSubarraySum(vector<int>& nums, int k) { int n = nums.size(); unordered_map<int, int> cnt; long long sum = 0; int valid = 0; for (int i = 0; i < k; i++) { sum += nums[i]; if (cnt[nums[i]]++ == 0) valid++; } long long res = valid == k ? sum : 0; for (int i = k; i < n; i++) { sum += (nums[i] - nums[i-k]); if (cnt[nums[i]]++ == 0) valid++; if (--cnt[nums[i-k]] == 0) valid--; if (valid == k) res = max(res, sum); } return res; } };

難度分: 1546 定長度的 sliding window，搭配對 window 檢查是否滿足條件 class Solution { public: long long maxSum(vector<int>& nums, int m, int k) { int n = nums.size(); unordered_map<int,int> cnt; long long sum = 0; long long res = 0; int valid = 0; for (int i = 0; i < k; i++) { sum += nums[i]; if (cnt[nums[i]]++ == 0) valid++; } if (valid >= m) res = sum; for (int i = k; i < n; i++) { sum += (nums[i] - nums[i-k]); if (cnt[nums[i]]++ == 0) valid++; if (--cnt[nums[i-k]] == 0) valid--; if (valid >= m) res = max(res, sum); } return res; } };

難度分: 1504 比較簡單的解法，使用 unordered_set class Solution { public: bool hasAllCodes(string s, int k) { unordered_set<string> set; for (int i = 0; i + k <= s.size(); i++) { set.insert(s.substr(i, k)); } return set.size() == pow(2, k); } }; 使用 sliding window，並運用移位運算子 class Solution { public: bool hasAllCodes(string s, int k) { if (s.size() < k) return false; int n = pow(2, k); vector<bool> used(n, false); int curr = 0; for (int i = 0; i < k; i++) { curr <<= 1; curr += (s[i] - '0'); } used[curr] = true; for (int i = k; i < s.size(); i++) { curr <<= 1; curr += (s[i] - '0'); curr %= n; used[curr] = true; } return all_of(used.begin(), used.end(), [](int x) { return x; }); } };

難度分: 1418 定長度的 sliding window，秒殺 class Solution { public: int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int k) { int n = customers.size(); int sum = 0; for (int i = 0; i < n; i++) { if (!grumpy[i]) { sum += customers[i]; customers[i] = 0; } } for (int i = 0; i < k; i++) { sum += customers[i]; } int res = sum; for (int i = k; i < n; i++) { sum += (customers[i] - customers[i-k]); res = max(res, sum); } return res; } };

難度分: 1360 定長度的 sliding window，秒殺 class Solution { public: int minimumRecolors(string blocks, int k) { int cnt = 0; for (int i = 0; i < k; i++) { if (blocks[i] == 'B') cnt++; } int res = k-cnt; for (int i = k; i < blocks.size(); i++) { if (blocks[i] == 'B') cnt++; if (blocks[i-k] == 'B') cnt--; res = min(res, k-cnt); } return res; } };

難度分: 1358 這題一樣是定長度的 sliding window，但要做一下轉換，半徑為 k，代表 window_size 為 2k+1。 class Solution { public: vector<int> getAverages(vector<int>& nums, int k) { int n = nums.size(); int m = 2*k+1; vector<int> res(n, -1); if (m > n) return res; long long sum = 0; for (int i = 0; i < m; i++) { sum += nums[i]; } res[k] = sum / m; for (int i = m, j = k+1; i < n; i++, j++) { sum += (nums[i] - nums[i-m]); res[j] = sum / m; } return res; } };

難度分: 1317 定長度的 sliding window，秒殺 class Solution { public: int numOfSubarrays(vector<int>& arr, int k, int threshold) { threshold *= k; int sum = 0; for (int i = 0; i < k; i++) { sum += arr[i]; } int res = 0; if (sum >= threshold) res++; for (int i = k; i < arr.size(); i++) { sum += (arr[i] - arr[i-k]); if (sum >= threshold) res++; } return res; } };

定長度的 sliding window，秒殺 class Solution { public: double findMaxAverage(vector<int>& nums, int k) { int sum = 0; for (int i = 0; i < k; i++) { sum += nums[i]; } int res = sum; for (int i = k; i < nums.size(); i++) { sum += nums[i]; sum -= nums[i-k]; res = max(res, sum); } return res/(double)k; } };

難度分: 1263 定長度的 sliding window，秒殺 class Solution { public: int maxVowels(string s, int k) { int cnt = 0; unordered_set<char> set = {'a','e','i','o','u'}; for (int i = 0; i < k; i++) { if (set.count(s[i])) cnt++; } int res = cnt; for (int i = k; i < s.size(); i++) { if (set.count(s[i])) cnt++; if (set.count(s[i-k])) cnt--; res = max(res, cnt); } return res; } };

定長度的 sliding window pattern 步驟 construct sliding window + check condition move sliding window (1) remove item (2) check condition (3) add item 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: bool solve(vector<int>& nums, int k) { _w = make_unique<WindowImpl>(k); int n = nums.size(); for (int i = 0; i < n; i++) { if (i >= k) _w->erase(nums[i-k]); if (_w->check(nums[i])) return true; _w->add(nums[i]); } return false; } };