力扣——第298场周赛

5242. 兼具大小写的最好英文字母

给你一个由英文字母组成的字符串 s ，请你找出并返回 s 中的 最好 英文字母。返回的字母必须为大写形式。如果不存在满足条件的字母，则返回一个空字符串。

最好 英文字母的大写和小写形式必须 都 在 s 中出现。

英文字母 b 比另一个英文字母 a 更好 的前提是：英文字母表中，b 在 a 之 后 出现。

示例 1：

输入：s = "lEeTcOdE"
输出："E"
解释：
字母 'E' 是唯一一个大写和小写形式都出现的字母。

提示：

• 1 <= s.length <= 1000
• s 由小写和大写英文字母组成

问题解析

哈希表记录遍历过的字符，把大小写同时出现的字符都找出来，取最大的。

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 <= 3000
• 0 <= 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];
    }
};