靈神題單

code c++ algo

滑動窗口

定長滑窗題目

  1. 入:下標為i的算進入窗口,更新相關的統計量,如果i<k-1則重複第一步不繼續
  2. 更新:更新答案,一般是更新最大值or最小值
  3. 出:下標為i-k+1的算離開窗口,更新相關統計量

Leetcode 1456

  • 統計值到k窗口大小的母音次數
  • 不到k窗口大小繼續塞值統計,超過的話紀錄最大值
  • 超過窗口大小將最舊的移出,如果是母音要減掉一次統計
class Solution {
public:
    int maxVowels(string s, int k) {
        int ans=0;
        int r=0;
        for(int i=0;i<s.size();i++){
            if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u')
                r++;
            if(i < k-1)
                continue;
            ans = max(ans,r);
            char out = s[i-k+1];
            if(out == 'a' || out == 'e' || out == 'i' || out == 'o' || out == 'u')
                r--;
        }
        return ans;
    }
};

Leetcode 643

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
       double sum = 0;
       double max_sum = INT_MIN;
       for(int i=0;i<nums.size();i++){
            sum += nums[i];
            if(i < k-1)
                continue;
            max_sum = max(max_sum,sum);
            int out = nums[i-k+1];
            sum -= out;
       }
       return max_sum/k;
    }
};

Leetcode 1343

class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        int sum = 0;
        int n = 0;
        for(int i=0;i<arr.size();i++){
            sum += arr[i];
            if(i < k-1)
                continue;
            if(sum/k >= threshold)
                n++;
            int out = arr[i-k+1];
            sum -= out;
        }
        return n;
    }
};

Leetcode 2090

class Solution {
public:
    vector<int> getAverages(vector<int>& nums, int k) {
        vector<int> ans(nums.size(),-1);
        long long sum = 0;
        for(int i=0;i<nums.size();i++){
            sum += nums[i];
            if(i < (2*k))
                continue;
            
            ans[i-k]=sum/(2*k+1);
            sum -= nums[i-(2*k)];
        }
        return ans;
    }
};

Leetcode 2379

class Solution {
public:
    int minimumRecolors(string blocks, int k) {
        int cnt = 0;
        int max_cnt = 0;
        for(int i=0;i<blocks.size();i++){
            if(blocks[i] == 'B')
                cnt++;
            if(i < k-1)
                continue;
            max_cnt = max(max_cnt,cnt);
            if(blocks[i-k+1] == 'B')
                cnt--;
        }
        return k-max_cnt;
    }
};

Leetcode 1052

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int c =  customers.size();
        int ans = 0;
        for(int i=0;i<c;i++){
            if(grumpy[i] == 0){
                ans+=customers[i];
                customers[i] = 0;
            }
        }
        int sum = 0;
        int cur = 0;
 
        for(int i=0;i<c;i++){
            cur += customers[i];
            if(i >= minutes)
                cur -= customers[i-minutes];
            sum = max(sum,cur);
        }
 
        return ans+sum;
    }
};

Leetcode 2461

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
       unordered_map<int, int> count; 
        long long currentSum = 0, maxSum = 0; 
        int left = 0; 
 
        for (int right = 0; right < nums.size(); ++right) {
            count[nums[right]]++;
            currentSum += nums[right]; 
 
            while (count[nums[right]] > 1 || (right - left + 1 > k)) {
                currentSum -= nums[left];
                count[nums[left]]--;
                if (count[nums[left]] == 0) {
                    count.erase(nums[left]); 
                }
                left++; 
            }
            if (right - left + 1 == k) {
                maxSum = max(maxSum, currentSum);
            }
        }
 
        return maxSum;
    }
};

Leetcode1423

思考

  • 先拿k張牌
  • 後續往右移動窗口等同於拿k+1張牌
  • 縮減窗口相當於丟去k-1張牌
  • 等同於原先拿k張牌的總和加上k+1張牌減去k-1張牌的值
  • 後續更新ans即可
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int s = accumulate(cardPoints.begin(),cardPoints.begin()+k,0);
        int ans = s;
        int n = cardPoints.size();
        for(int i=1;i<=k;i++){
            s += (cardPoints[n-i]-cardPoints[k-i]);
            ans = max(ans,s);
        }
        return ans;
    }
};