Leetcode

1. Two Sum Hardness: \(\color{green}\textsf{Easy}\) Ralated Topics: Array、Hash Table 一、題目 Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order. Example 1: Input: nums = [2,7,11,15], taget = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0,1]. Example 2: ...

難度分: 1574 這題同樣是定長度的 sliding window，但要透過一點轉換，變成求 window = n - k 的最小和 class Solution { public: int maxScore(vector<int>& cardPoints, int k) { int n = cardPoints.size(); int m = n-k; int sum = 0; for (int i = 0; i < m; i++) { sum += cardPoints[i]; } int total = sum; int min_window_sum = sum; for (int i = m; i < n; i++) { sum += (cardPoints[i] - cardPoints[i-m]); total += cardPoints[i]; min_window_sum = min(min_window_sum, sum); } return total - min_window_sum; } };

難度分: 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; } };