当前位置:网站首页>Li Kou - 298th weekly match
Li Kou - 298th weekly match
2022-07-06 16:15:00 【Hello_ Ä】
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];
}
};
边栏推荐
- Penetration test 2 --- XSS, CSRF, file upload, file inclusion, deserialization vulnerability
- Specify the format time, and fill in zero before the month and days
- QWidget代码设置样式表探讨
- 1323. Maximum number of 6 and 9
- Opencv learning log 27 -- chip positioning
- Shell Scripting
- Frida hook so layer, protobuf data analysis
- 1855. Maximum distance of subscript alignment
- [exercise-7] (UVA 10976) fractions again?! (fraction split)
- Nodejs crawler
猜你喜欢
(POJ - 3579) median (two points)
Flag framework configures loguru logstore
Luogu P1102 A-B number pair (dichotomy, map, double pointer)
Basic Q & A of introductory C language
Maximum product (greedy)
pytorch提取骨架(可微)
1005. Maximized array sum after K negations
Codeforces Round #801 (Div. 2)A~C
力扣——第298场周赛
b站 实时弹幕和历史弹幕 Protobuf 格式解析
随机推荐
2027. Minimum number of operations to convert strings
Penetration test (7) -- vulnerability scanning tool Nessus
树莓派4B安装opencv3.4.0
Analysis of protobuf format of real-time barrage and historical barrage at station B
Suffix expression (greed + thinking)
图图的学习笔记-进程
Auto.js入门
Pyside6 signal, slot
(POJ - 3258) River hopper (two points)
[exercise-1] (UVA 673) parentheses balance/ balanced brackets (stack)
Common configuration files of SSM framework
Openwrt source code generation image
树莓派CSI/USB摄像头使用mjpg实现网页摄像头监控
1005. Maximized array sum after K negations
(POJ - 2739) sum of constructive prime numbers (ruler or two points)
Nodejs+vue online fresh flower shop sales information system express+mysql
生成随机密码/验证码
F - birthday cake (Shandong race)
Flag framework configures loguru logstore
pytorch提取骨架(可微)