LeetCode 1450 - 1453

The number of students doing homework at a given time

 

 

Give two arrays to represent the start time and end time , Give an integer queryTime Indicates the time to ask

Given integer queryTime In how many closed intervals , Each closed interval is a start time and an end time

Enumerate all intervals , Judge whether the time to ask is in the interval

Example 1： Yes 3 Intervals ,[ 1,3 ]  [ 2,2 ]  [ 3,7 ], The time to ask is 4, see 4 In which interval

                                       ×            ×           √

Final 4 Only in one interval , Answer back 1

Judge 4 Is it greater than or equal to the start time of the interval , Less than or equal to the end time of the interval , If so , answer + 1, The time complexity is O(n)

class Solution {
public:
    int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {
        // Record answer 
        int res = 0;
        // Enumerate all intervals 
        for(int i = 0;i < startTime.size();i++ ) 
            // Meet the conditions 
            if(queryTime >= startTime[i] && queryTime <= endTime[i])
                res ++;
        return res;
         
    }
};

Rearrange the words in the sentence

 

 

Defines what a sentence is ： A string of words separated by spaces , The sentence satisfies certain conditions , You need to press... For all the words in the sentence Sort words in ascending order of length , If two words are the same length , Keep its relative position in the original sentence

① How to find all the words separated by spaces in a sentence ：stringstream

② How to sort ： Double keyword sorting ： One 、 Length of string   Two 、 Its relative subscript in the original sequence ( special )

stable_sort()： Stable sequencing , Just sort by length

First take all the words out of the sentence , Put it in vector in , Reuse stable_sort Sort according to the length of each word from small to large

First, you need to change the first letter of the first word of a sentence into lowercase , Then turn the initial letter of the final sentence into capital

C++ stable_sort() Usage details

class Solution {
public:
    string arrangeWords(string text) {
        // Usage and  cin  equally 
        stringstream ssin(text);
        vector<string> words;
        string word;
        // hold  ssin  Put all the words in  words  in 
        while(ssin >>  word) words.push_back(word);
        // Turn the first letter of a word into lowercase  tolower  Change capital letters to lowercase   If it's other characters, it doesn't change   perhaps  +32
        words[0][0] = tolower(words[0][0]);
        // Ascending sort 
        stable_sort(words.begin(),words.end(),[](string a,string b) {
            return a.size() < b.size();
        });
        // Then capitalize the initial of the result 
        words[0][0] = toupper(words[0][0]);
        // Put all the words in the answer 
        string res;
        for(auto word : words) res += word + ' ';
        // Delete the last space 
        res.pop_back();
        return res;
    }
};

Collection list

 

 

 

 

Give an array favoriteCompanies, among favoriteCompanies[ i ] It's No i List of companies collected by users

favoriteCompanies[ i ] It's a string A list of , See which lists are not a subset of any other list 、 Which lists contain company names that are not fully included in any other list

Example 1： First look at the first list , None of the following lists LeetCode, So the first list must not be a subset of any of the following lists , So the first list needs to output , The third list can be completely included by the first list , So the third list cannot output , And so on . . .

Number of lists ≤ 100, The length of each list ≤ 500, Each string ( company ) The length of ≤ 20, There will be no duplicate elements in a user's favorite list

Give two lists , How to determine A Is it right? B Subset ( A Is it completely B contain )？

First sort all the words in the list ,A and B It's orderly , The time complexity of sorting O( 100 × 500 × log500 × 20( Every comparison 、 The exchange is two strings ))   O( 10^7 )

Why order ？

The order of all words in a list can be out of order , The same set , The number of sequences is n The factorial

To avoid dealing with redundancy ： aggregate 1：1  2  3  aggregate 2：3  2  1, The set is the same , But the list is different , After sorting, ensure that there is only one sequence corresponding to the set

Sort and then judge A Is it right? B Subset , Scan from front to back B Every string in , Take a pointer from A Every word of begins to point back , Scanning B When , If B String and A The corresponding string is the same , Move the pointer back one bit , When the scan is complete B after , If A All the words in the are scanned , Just explain A It can be completely B contain , Otherwise, it doesn't work

Enumerate each string , Enumerate all other strings , Compare the current string with other strings O(100 × 99 × (500 + 500))   O( 10^7 )

because A、B Has been sorted in dictionary order , If A yes B Subset , that A It must be B A subsequence of ; If A No B Subset ,A Inevitable inclusion B String not in

class Solution {
public:
    vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {
        // use  n  To represent the length of the list 
        int n = favoriteCompanies.size();
        // Enumerate each list from front to back and sort 
        for(auto &l : favoriteCompanies) sort(l.begin(),l.end());
        // Record the list that meets the requirements ->  Enumerate each list from front to back 
        vector<int> res;
        for(int i = 0;i < n;i++ ) {
            // Used to determine whether the current list is a subset of other lists 
            bool is_subset = false;
            // Enumerate all other lists 
            for(int j = 0;j < n;j++ )
                if(i != j) 
                {
                    // Judge  favoriteCompanies[i]  Is it right?  favoriteCompanies[j]  Subset 
                    auto &A = favoriteCompanies[i],&B = favoriteCompanies[j];
                    //a The subscript 
                    int a = 0;
                    //b from 0 Start 
                    for(int b = 0;b < B.size() && a < A.size();b++ ) 
                        if(A[a] == B[b])
                            a++;
                    // explain  A  yes  B  Subset 
                    if(a == A.size())
                    {
                        is_subset =true;
                        break;
                    }
                }
                // If the current string is not a subset of any string 
                if(!is_subset) res.push_back(i);
        }
        return res;
    }
};

Maximum number of darts in a circular target