Sliding window -- leetcode solution

1052. Angry Bookstore owners

Ideas ： First find out the total number of people when they are not angry , Then use the sliding window to find out the maximum number of people who are dissatisfied because of anger in that interval when angry , When you record the maximum value and return , The number of satisfied people plus the maximum value of dissatisfaction is the answer .

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int size = customers.size();
        int l = 0,r = 0;
        int e = 0;
        int tmp = 0;
        int ans = 0;
        while(r<size)
        {
            if(grumpy[r]==0) ans+=customers[r];
            tmp+=grumpy[r]*customers[r];
            r++;
            e = max(e,tmp);

            if(r-l==minutes) tmp-=grumpy[l]*customers[l++];
        }
        return ans+e;
    }
};

643. Maximum average of subarrays I

Ideas ： First floor for Loop to find the average value of the subarray of the initial window , Then cycle the window backwards , Constantly find the average , Finally, leave the maximum value .

double findMaxAverage(int* nums, int numsSize, int k){
    
    double max = 0;
    double sum = 0;
    for(int i = 0;i<k;i++)
    {
    
        sum+=nums[i];
    }
    max = sum;
    for(int i =k;i<numsSize;i++)
    {
    
        sum = sum - nums[i-k] + nums[i];
        max = (max>sum)?max:sum;
    }
    return max/k;
}

718. Longest repeating subarray

Ideas ： The sliding window , The ruler taking method sliding window provided by a great God of the problem solution will have two arrays , First, let the array with smaller length become an array a, And then let a This ruler doesn't move b Ruler , The longest common subarray of the overlapping parts of the ruler is compared every time
The first stage ： for the first time b The last element of the array and a The first element of the array , Then keep moving , know b No bn-an Elements and a After all the arrays are compared , The first phase ends .
The second stage ： hypothesis b Array ratio a Team leader , Then at this time a There is also a part of the length in front of the array b Array , That is to say bn-an Start from this position , Move backward b Array , The length of comparison is still an, until b Array from 0, To an All positions are compared .
The third stage ：b An array with the a The overlap of arrays begins to decrease , Until the last b The first element of the array and a The last element of the array overlaps , This is the last comparison .
Compare the functions used cmplen , The first parameter is a Array ,i Express a Where the array starts comparison , And then there was b Array ,j Express b The starting position of array comparison , Last parameter len Indicates the length of the interval to be compared .

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        return nums1.size()<nums2.size() ? findMax(nums1,nums2) : findMax(nums2,nums1);
    }

    int findMax(vector<int>& a,vector<int>&b)
    {
        int an = a.size(),bn = b.size();
        int maxlen = 0;
        for(int len = 1; len<=an;len++)
            maxlen = max(maxlen,cmplen(a,0,b,bn-len,len));
        for(int j = bn-an;j>=0;j--)
            maxlen = max(maxlen,cmplen(a,0,b,j,an));
        for(int i = 1;i<an;i++)
            maxlen = max(maxlen,cmplen(a,i,b,0,an-i));
        return maxlen;
    }

    int cmplen(vector<int>& a,int i,vector<int>& b,int j,int len)
    {
        int count = 0,maxlen = 0;
        for(int k = 0;k<len;k++)
        {
            if(a[i+k] == b[j+k])
                count++;
            else if(count>0)
            {
                maxlen = max(maxlen,count);
                count = 0;
            }
        }
        return count == 0? maxlen : max(maxlen,count);
    }
};

978. Longest turbulence subarray

Slide window idea ： If an element arr[r] > arr[ r-1 ] && arr[r ] >arr[r+1] Then this point is the legal point , Can be put into sliding window , then ++r, On the contrary, the less than sign is the same . This is greater than and less than alternate .
Judgment of special circumstances , If l==r When you encounter a series of equal times, you need to move backward at the same time l and r Until there is inequality , Move r Form a sliding window , Then judge according to the above conditions .

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        int ans = 1;
        int l = 0,r = 0;
        while(r<n-1)
        {
            if(l==r)
            {
                if(arr[r] == arr[r+1])
                {
                    l++;
                }
                r++;
            }
            else
            {
                if(arr[r]>arr[r-1] && arr[r]>arr[r+1])
                    r++;
                else if(arr[r]<arr[r-1] && arr[r]<arr[r+1])
                    r++;
                else 
                    l = r;
            }
            ans = max(ans,r-l+1);
        }
        return ans;
    }
};