Li Kou - 298th weekly match

Power button —— The first 298 Weekly match

5242. The best English letters with both upper and lower case

Give you a string of English letters s , Please find out and return to s Medium best English letter . The returned letters must be in upper case . If there is no letter that meets the condition , Then return an empty string .

best The upper and lower case forms of English letters must be all stay s It appears that .

English letter b Than another English letter a Better The premise is ： In the English alphabet ,b stay a And after appear .

Example 1：

 Input ：s = "lEeTcOdE"
 Output ："E"
 explain ：
 Letter  'E'  Is the only letter that appears in both uppercase and lowercase .

Tips ：

• 1 <= s.length <= 1000
• s It consists of lowercase and uppercase English letters

Problem analysis

Hash table records traversed characters , Find out the characters with both upper and lower case , Take one of the biggest .

AC Code

class Solution {
public:
    string greatestLetter(string s) {
        unordered_map<char,int>mymap;
        string str;
        for(auto i:s)
        {
            if(i>='a'&&i<='z')
            {
                if(mymap[i-32]==1)
                {
                    str+=i-32;
                }
                else mymap[i]=1;
            }
            else 
            {
                if(mymap[i+32]==1)
                {
                    str+=i;
                }
                else mymap[i]=1;
            }
        }
        sort(str.begin(),str.end());
        string str2;
        if(str.size()>0)
            str2+=str.back();
        
        return str2;
    }
};

5218. The number of digits is K The sum of the integers of

Here are two integers num and k , Consider a positive integer multiset with the following properties ：

Every integer digit is k .
The sum of all integers is num .
Returns the minimum size of the multiset , If there are no such multiple sets , return -1 .

Be careful ：

A multiset is similar to a set , But a multiset can contain more than one integer , The sum of empty multisets is 0 .
One digit number Is the rightmost digit of the number .

Example 1：

 Input ：num = 58, k = 9
 Output ：2
 explain ：
 Multiple sets  [9,49]  Meet the conditions of the topic , And for  58  And the number of bits of each integer is  9 .
 Another conditional multiple set is  [19,39] .
 Can prove that  2  Is the minimum length of a multiple set that satisfies the problem condition .

Tips ：

• 0 <= num <= 3000
• 0 <= k <= 9

Problem analysis

Judge how many k Add to get the sum of single digits num The same number , We use a variable cnt When the counter comes to calculate , That is, at least cnt individual k Add to get the sum of single digits num The same number , If cnt*k Greater than num 了 , It means that we cannot form num, return -1, for example ：num=12,k=8, At the very least 4 individual 8 Add to get the ending 2 Number of numbers , but 32 Greater than 12, So no . If not greater than num, So in fact, the answer is cnt 了 , as for num and cnt *k The difference between the , Anyway, it won't affect the single digits , Let's just add any number in the set , for example ：num=22,k=4, Then the set is {4,4,4,14}. If num by 0 Go straight back 0 that will do .

Another thing is that you can't get a single digit sum anyway num The same thing , for example ：num=15,k=2. To this end, we add a judgment , If cnt Greater than 100 I haven't found it yet , We'll go back to -1.

AC Code

class Solution {
public:
    int minimumNumbers(int num, int k) {
        if(num==0)return 0;
        int cnt=0,res=-1;
        while(res%10!=num%10)
        {
            if(res==-1)res=0;
            res+=k;
            cnt++;
            if(cnt>100)return -1;
        }
        if(res>num)return -1;
        return cnt;
    }
};

6099. Less than or equal to K The longest binary subsequence of

Give you a binary string s And a positive integer k .

Please return s Of The longest Subsequence , And the subsequence corresponds to Binary system The number is less than or equal to k .

Be careful ：

Subsequences can have Leading 0 .
An empty string is treated as 0 .
Subsequence It refers to deleting zero or more characters from a string , The sequence of remaining characters obtained without changing the order .

Example 1：

 Input ：s = "1001010", k = 5
 Output ：5
 explain ：s  Less than equal to  5  The longest subsequence of is  "00010" , The corresponding decimal number is  2 .
 Be careful  "00100"  and  "00101"  It is also the longest possible subsequence , The decimal system corresponds to  4  and  5 .
 The length of the longest subsequence is  5 , So back  5 .

Problem analysis

Greedy strategy . We can s The suffixes of are taken , Take this suffix and turn it into 10 The decimal number will be greater than k until , Then we put the rest 0 Choose all .

Why can we take the suffix directly ？ for instance , such as s yes ”10001001“,k yes 5（ Binary system ：101）, We can only take the suffix 001, Because I got 1001 Time is greater than k 了 , If we take one less 0, To get the subsequence 101, In fact, the length is still 3, That is to say, you want to take 1 There will be less corresponding 0, Sometimes less 0 The number of may also be greater than the number you take one , So let's just get the suffix directly , Then put the rest 0 All taken , these 0 It will not affect our overall value .

AC Code

class Solution {
public:
    int longestSubsequence(string s, int k) {
        reverse(s.begin(),s.end());
        long long cnt=0,ans=1,res=0,n=s.size();
        bool flag=true;
        for(int i=0;i<n;i++)
        {
            if(s[i]=='0')cnt++;
            else if(flag)
            {
                if(res+ans>k)
                {
                    flag=false;
                    continue;
                }
                res+=ans;
                cnt++;
            }
            if(ans<1e9)ans*=2;
        }
        return cnt;
    }
};

5254. Selling wood blocks

Here are two integers m and n , It represents the height and width of a rectangular wooden block . And give you a two-dimensional array of integers prices , among prices[i] = [hi, wi, pricei] It means that you can pricei The price of one yuan is as high as hi Wide for wi Rectangular wooden block .

In every operation , You must perform the cutting operation in one of the following ways , To get two smaller rectangular pieces of wood ：

Press the height in the vertical direction Completely Cut wood blocks , or
Horizontally by width Completely Cut wood blocks
After cutting a piece of wood into small pieces , You can prices Selling wood blocks . You can sell multiple pieces of wood of the same size . You don't have to sell all the little pieces of wood . you You can't Height and width of wood block after rotation and cutting .

Please cut back a piece with a size of m x n After the wooden block , What you can get most Money .

Note that you can cut a piece of wood any number of times .

Example 1：

 Input ：m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]]
 Output ：19
 explain ： The figure above shows a feasible solution . Include ：
- 2  block  2 x 2  A small piece of wood , Sell out  2 * 7 = 14  element .
- 1  block  2 x 1  A small piece of wood , Sell out  1 * 3 = 3  element .
- 1  block  1 x 4  A small piece of wood , Sell out  1 * 2 = 2  element .
 All in all  14 + 3 + 2 = 19  element .
19  Yuan is the most money you can get .

Problem analysis

Section dp.

You can use a two-dimensional array f Deposit price ,f[i] [j] The height is i, Width j The price of the wooden block is f[i] [j].

Another two-dimensional array dp To make dp Array ,dp[i] [j] The height is i, Width is j At most, the wooden blocks of can be sold dp[i] [j] element .

For a piece of wood :

We can enumerate the dividing lines k Let's cut it vertically into two pieces of wood with different widths , State transition is ：

dp[i] [j]=max（dp[i] [j],dp[i] [j-k]+dp[i] [k]）;

We can enumerate the dividing lines k Let's cut it horizontally into two pieces of wood with different heights , State transition is ：

dp[i] [j]=max（dp[i] [j],dp[k] [j]+dp[i-k] [j]）;

Finally back to dp[m] [n] that will do .

AC Code

class Solution {
public:
    long long f[250][250],dp[250][250];
    long long sellingWood(int m, int n, vector<vector<int>>& prices) {
        for(auto i:prices)
        {
            f[i[0]][i[1]]=i[2];
        }
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dp[i][j]=f[i][j];
                for(int k=1;k<=i;k++)
                    dp[i][j]=max(dp[i][j],dp[k][j]+dp[i-k][j]);
                for(int k=1;k<=j;k++)
                    dp[i][j]=max(dp[i][j],dp[i][k]+dp[i][j-k]);
            }
        }
        return dp[m][n];
    }
};