June training day 6 - sliding window

Preface

The content of today's algorithm is ： The sliding window

One 、 The minimum difference in student scores

        
To give you one Subscript from 0 Start Of An array of integers nums , among nums[i] It means the first one i A student's grade . Here's another one for you Integers k .
From array choose Out arbitrarily *k A student's grade , Make this k Between scores The highest and Lowest score Of Difference value achieve To minimize the .
Return possible Of Minimum difference .

Example 1：
Input ：nums = [90], k = 1
Output ：0
explain ： elect 1 A student's grade , have only 1 Methods ：

• [90] The difference between the highest score and the lowest score is 90 - 90 = 0
  The smallest possible difference is 0

Example 2：
Input ：nums = [9,4,1,7], k = 2
Output ：2
explain ： elect 2 A student's grade , Yes 6 Methods ：

• [9,4,1,7] The difference between the highest score and the lowest score is 9 - 4 = 5
• [9,4,1,7] The difference between the highest score and the lowest score is 9 - 1 = 8
• [9,4,1,7] The difference between the highest score and the lowest score is 9 - 7 = 2
• [9,4,1,7] The difference between the highest score and the lowest score is 4 - 1 = 3
• [9,4,1,7] The difference between the highest score and the lowest score is 7 - 4 = 3
• [9,4,1,7] The difference between the highest score and the lowest score is 7 - 1 = 6
  The smallest possible difference is 2

One 、 Ideas :

        （1） To facilitate the operation, the array is incrementally sorted
        （2） Define two variables as left and right boundaries i,j,
        （3） Probably k==1, So define j=-1;
        （4） Then proceed to the right boundary j expansion , if j And i A distance of k（j-i+==k）, Then operate , If the distance is greater than k, Left boundary i Expand ;
        （5） Repeat ;

Two 、 Source code

class Solution {
    
public:
    int minimumDifference(vector<int>& nums, int k) {
    
        sort(nums.begin(),nums.end());
        int i=0,j=-1;
        int ans=10000000;
        // This length fetching operation cannot be performed incidentally -1（2022.6.7  For the time being, the cause is unknown ）
        int size=nums.size();
        while(j<size-1){
    
            ++j;
            if(j-i+1>k){
    
                ++i;
            }
            if(j-i+1==k){
    
                ans = min(ans, nums[j] - nums[i]);
            }
        }
        return ans;
    }
};

3、 ... and . Knowledge point

         Sort + Two points search

Two 、 The longest nice substring

         When one character string s The uppercase and lowercase forms of each letter contained meanwhile Appear in the s in , Just call this string s yes happy character string . For example ,“abABB” It's a beautiful string , because ‘A’ and ‘a’ At the same time , And ‘B’ and ‘b’ At the same time . However ,“abA” Not because ‘b’ There is , and ‘B’ There was no .
Give you a string s , Would you please return s Longest Nice substring . If There are multiple answers , Would you please return Earliest The one that appears . If There is no good substring , Would you please Returns an empty string .

Example 1：
Input ：s = “YazaAay”
Output ：“aAa”
explain ：“aAa” It's a beautiful string , Because there is only one letter in this substring , Its lowercase form ‘a’ And capital form ‘A’ At the same time .
“aAa” Is the longest nice substring .

Example 2：
Input ：s = “Bb”
Output ：“Bb”
explain ：“Bb” It's a beautiful string , because ‘B’ and ‘b’ There were . The whole string is also a substring of the original string .

Example 3：
Input ：s = “c”
Output ：“”
explain ： No nice substring .

Example 4：
Input ：s = “dDzeE”
Output ：“dD”
explain ：“dD” and “eE” They're all the longest substrings .
Because there are many nice substrings , return “dD” , Because it first appeared .

One 、 Ideas :

        （1） Purpose ： In one In a string return among Of Any group of eligible String
        （2） therefore Anyone who Less than or equal to s String array length The length of consecutive substrings of （ Continuous interval ） All enumeration , Find the maximum interval that meets the condition , It can be used The sliding window To operate , Find the longest interval , Just start from the maximum length ;
        （3） Hash table can be used to solve , The problem of judging conditions （ namely ： Array subscript storage The number of elements ） Record dynamically in the sliding of each length window The existence of large and small letters , The window length is used to judge the condition （ see （4） in ）, if The length is greater than the window length, and the last boundary record is dynamically subtracted And length ,（ In order to save the big and small letter records in the hash table , Implement an interface that converts numbers ）
        （4）26 In letters , Compliant output , The cycle is over , Not at all , Output ""; ( empty )

Two 、 Source code

class Solution {
    
    int code(char c){
    
        if(c>='a'&&c<='z'){
    
            return c-'a';
        }
        return c-'A'+26;
    }
public:
    string longestNiceSubstring(string s) {
    
        int l,i,j,k;
        int size;
        int hash[52];
        // Here we start from the largest   Write the wrong  l++——————> should l--; I have been looking for it for a long time 
        for(l=s.size();l>0;l--){
    
            i=0;
            j=-1;
            // This length fetching operation cannot be performed incidentally -1（2022.6.7  For the time being, the cause is unknown ）
            size=s.size();
            memset(hash,0,sizeof(hash));
            while(j<size-1){
    
                ++j;
                ++hash[code(s[j])];
                if(j-i+1>l){
    
                    //
                    --hash[code(s[i])];
                    ++i;
                }
                if(j-i+1==l){
    
                    for(k=0;k<26;k++){
    
                        if(!hash[k]&&hash[k+26]){
    
                            break;
                        }
                        if(hash[k]&&!hash[k+26]){
    
                            break;
                        }
                    }
                    if(k==26){
    
                        return s.substr(i,j-i+1);
                    }
                }
            }
        }
        return "";
    }
};

3、 ... and . Knowledge point

         Hash + The sliding window （ The sliding window ： Used to solve fixed interval problems ）（ Hashtable ： To solve Some condition judgment problems of discontinuity ）