力扣——第298场周赛
5242. 兼具大小写的最好英文字母
给你一个由英文字母组成的字符串 s ，请你找出并返回 s 中的 最好 英文字母。返回的字母必须为大写形式。如果不存在满足条件的字母，则返回一个空字符串。
最好 英文字母的大写和小写形式必须 都 在 s 中出现。
英文字母 b 比另一个英文字母 a 更好 的前提是：英文字母表中，b 在 a 之 后 出现。
示例 1：
输入：s = "lEeTcOdE"
输出："E"
解释：
字母 'E' 是唯一一个大写和小写形式都出现的字母。
提示：
1 <= s.length <= 1000s由小写和大写英文字母组成
问题解析
哈希表记录遍历过的字符，把大小写同时出现的字符都找出来，取最大的。
AC代码
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. 个位数字为 K 的整数之和
给你两个整数 num 和 k ，考虑具有以下属性的正整数多重集：
每个整数个位数字都是 k 。
所有整数之和是 num 。
返回该多重集的最小大小，如果不存在这样的多重集，返回 -1 。
注意：
多重集与集合类似，但多重集可以包含多个同一整数，空多重集的和为 0 。
个位数字 是数字最右边的数位。
示例 1：
输入：num = 58, k = 9
输出：2
解释：
多重集 [9,49] 满足题目条件，和为 58 且每个整数的个位数字是 9 。
另一个满足条件的多重集是 [19,39] 。
可以证明 2 是满足题目条件的多重集的最小长度。
提示：
0 <= num <= 30000 <= k <= 9
问题解析
判断一下多少个k相加可以得到个位数和num一样的数，我们用一个变量cnt当计数器来计算，即至少要cnt个k相加才可以得到个位数和num一样的数，如果cnt*k大于num了，说明我们无法组成num，返回-1，例如：num=12，k=8，至少要4个8相加才能得到结尾为2的数，但32大于12，所以不行。如果不大于num，那么实际上答案就是cnt了，至于num和cnt *k的差值，反正不会影响到个位数，我们随便给集合中的一个数加上就行，例如：num=22，k=4，那么集合就是{4，4，4，14}。如果num为0就直接返回0即可。
还有一点就是不管咋算都得不到个位数和num一样的情况，例如：num=15，k=2。为此我们加个判断，如果cnt大于100了还没找到，我们就返回-1。
AC代码
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. 小于等于 K 的最长二进制子序列
给你一个二进制字符串 s 和一个正整数 k 。
请你返回 s 的 最长 子序列，且该子序列对应的 二进制 数字小于等于 k 。
注意：
子序列可以有 前导 0 。
空字符串视为 0 。
子序列 是指从一个字符串中删除零个或者多个字符后，不改变顺序得到的剩余字符序列。
示例 1：
输入：s = "1001010", k = 5
输出：5
解释：s 中小于等于 5 的最长子序列是 "00010" ，对应的十进制数字是 2 。
注意 "00100" 和 "00101" 也是可行的最长子序列，十进制分别对应 4 和 5 。
最长子序列的长度为 5 ，所以返回 5 。
问题解析
贪心策略。我们可以把s的后缀都取了，取到这个后缀转成10进制数会大于k为止，然后我们把剩下的0全部选上。
为什么直接取后缀可以呢？举个例子，比如s是”10001001“，k是5（二进制：101），我们取后缀只能取001，因为取到1001时就大于k了，如果我们少取一个0，来取到子序列101，实际上此时长度还是3，也就是说你想取1就会少对应的0，有时候少0的个数可能还大于你取一的个数，所以我们干脆直接取完后缀，然后把剩下的0全取了，这些0不会影响我们整体的值。
AC代码
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. 卖木头块
给你两个整数 m 和 n ，分别表示一块矩形木块的高和宽。同时给你一个二维整数数组 prices ，其中 prices[i] = [hi, wi, pricei] 表示你可以以 pricei 元的价格卖一块高为 hi 宽为 wi 的矩形木块。
每一次操作中，你必须按下述方式之一执行切割操作，以得到两块更小的矩形木块：
沿垂直方向按高度 完全 切割木块，或
沿水平方向按宽度 完全 切割木块
在将一块木块切成若干小木块后，你可以根据 prices 卖木块。你可以卖多块同样尺寸的木块。你不需要将所有小木块都卖出去。你 不能 旋转切好后木块的高和宽。
请你返回切割一块大小为 m x n 的木块后，能得到的 最多 钱数。
注意你可以切割木块任意次。
示例 1：
输入：m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]]
输出：19
解释：上图展示了一个可行的方案。包括：
- 2 块 2 x 2 的小木块，售出 2 * 7 = 14 元。
- 1 块 2 x 1 的小木块，售出 1 * 3 = 3 元。
- 1 块 1 x 4 的小木块，售出 1 * 2 = 2 元。
总共售出 14 + 3 + 2 = 19 元。
19 元是最多能得到的钱数。
问题解析
区间dp。
可以用一个二维数组f来存价格，f[i] [j]表示高度为i，宽度j的木块价格为f[i] [j]。
另一个二维数组dp来作dp数组，dp[i] [j]表示高度为i，宽度为j的木块最多可以卖出dp[i] [j]元。
对于一个木块:
我们可以枚举分界线k来把它竖着切开宽度不同的两个木块，状态转移就是：
dp[i] [j]=max（dp[i] [j]，dp[i] [j-k]+dp[i] [k]）;
我们可以枚举分界线k来把它横着切开高度不同的两个木块，状态转移就是：
dp[i] [j]=max（dp[i] [j]，dp[k] [j]+dp[i-k] [j]）;
最后返回dp[m] [n]即可。
AC代码
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];
}
};