leetcode contest biweekly 298
周末太匆忙，没有时间细想，打卡补题解。感觉第三题比第四题难。
5242. 兼具大小写的最好英文字母
题目
给你一个由英文字母组成的字符串 s ，请你找出并返回 s 中的 最好 英文字母。返回的字母必须为大写形式。如果不存在满足条件的字母，则返回一个空字符串。
最好 英文字母的大写和小写形式必须 都 在 s 中出现。
英文字母 b 比另一个英文字母 a 更好 的前提是：英文字母表中，b 在 a 之 后 出现。
示例 1：
输入：s = "lEeTcOdE" |
示例 2：
输入：s = "arRAzFif" |
示例 3：
输入：s = "AbCdEfGhIjK" |
提示：
1 <= s.length <= 1000s由小写和大写英文字母组成
地址
https://leetcode.cn/problems/greatest-english-letter-in-upper-and-lower-case
题意
直接遍历
思路
- 我们依次遍历数组即可，找到所有同时出现大写和小写形式，找到字典序最大的字母即可。
- 复杂度分析：
- 时间复杂度：$O(n + \Sigma)$, 其中 $n$ 为字符串的长度。
- 空间复杂度：$O(\Sigma)$。
代码
class Solution { |
5218. 个位数字为 K 的整数之和
题目
给你两个整数 num 和 k ，考虑具有以下属性的正整数多重集：
- 每个整数个位数字都是
k。 - 所有整数之和是
num。 - 返回该多重集的最小大小，如果不存在这样的多重集，返回
-1。
注意：
多重集与集合类似，但多重集可以包含多个同一整数，空多重集的和为 0 。
个位数字 是数字最右边的数位。
示例 1：
输入：num = 58, k = 9 |
示例 2：
输入：num = 37, k = 2 |
示例 3：
输入：num = 0, k = 7 |
提示：
0 <= num <= 30000 <= k <= 9
地址
https://leetcode.cn/problems/sum-of-numbers-with-units-digit-k
题意
数学问题
思路
- 简单的数学问题，分析如下:
- 如果 $num = 0$ 此时我们应该直接返回 $0$.
- 假设最小长度为 $n$，则可以知道 $n \times k$ 的个位数一定与 $num$ 的个位数相等，且必须满足 $ n \times k \le num$.
- 由于题目中允许重复的元素，且满足长度最小，则假设我们已经找到最小的 $n$ 满足上述条件，则可以知道 $num$ 一定可以被拆解成 $n$ 个个位数字为 $k$ 的正整数，已知 $num = (n-1) * k + (num - n*k) + k$，则可以拆分如下 :
$[k,k,k,\cdots, (num - (n-1)*k)]$，且满足 $num - (n-1) \times k$ 的个位数字一定为 $k$。
- 复杂度分析：
- 时间复杂度：$O(C)$，其中 $C = 10$。
- 空间复杂度：$O(1)$。
代码
class Solution { |
6099. 小于等于 K 的最长二进制子序列
题目
给你一个二进制字符串 s 和一个正整数 k 。
请你返回 s 的 最长 子序列，且该子序列对应的 二进制 数字小于等于 k 。
注意：
- 子序列可以有 前导
0。 - 空字符串视为
0。 - 子序列 是指从一个字符串中删除零个或者多个字符后，不改变顺序得到的剩余字符序列。
示例 1：
输入：s = "1001010", k = 5 |
示例 2：
输入：s = "00101001", k = 1 |
提示：
1 <= s.length <= 1000s[i]要么是'0'，要么是'1'。1 <= k <= 109
地址
https://leetcode.cn/problems/longest-binary-subsequence-less-than-or-equal-to-k
题意
动态规划
思路
- 典型的动态规划思路，为了方便计算，我们首先将字符串进行逆序处理。设 $dp[i]$ 表示字符串前 $i$ 个字符中所构成的小于等于 $k$ 的最长子串的长度，$val[i]$ 则表示当前最长长度时的值。当遍历到第 $i$ 个字符时，此时我们依次尝试是否添加 $s[i]$。
- 如果此时不添加第 $i$ 个字符到最终的字符串中，则满足 $dp[i] = dp[i-1],val[i] = val[i-1]$。
- 如果满足 $s[i] = ‘0’$, 此时肯定可以添加 $s[i]$, 则此时 $dp[i] = dp[i-1] + 1,val[i] = val[i-1]$。
- 如果满足 $s[i] = ‘1’$, 此时判段 $s[i]$ 加入到哪个子串后面, 假设 $s[i]$ 加在 第 $j$ 个字符后，则此时一定需要满足 $val[j] + 2^{dp[j]} \le k$ 才能合法加入，如果加入的后满足 $dp[j] + 1 > dp[i-1] $ 或者 $dp[j] + 1 = dp[i-1]，val[j] + 2^{dp[j]} < val[i-1]$ 时，此时更新 $dp[i]$ 与 $val[i]$。
- 当然上述解法还可以进一步优化，优化到 $O(n)$，仔细思考一下，加入了 $s[i]$ 后实际上我们只增加了一位，此时我们应该只需要检测长度为 $dp[i-1] - 1$ 时的最小值即可，不需要遍历所有的前 $i-1$ 个可能的字符串长度，优化后可以将时间复杂度优化到 $O(n)$。
- 贪心法，解法比较巧妙，可以参考题解，只用 $O(n)$ 的复杂度即可。
- 动态规划二:
- 设 $dp[i]$ 表示子字符串长度为 $i$ 时的最小值，设当前已经知道的最大长度为 $m$，此时当我们遍历第 $j$ 个字符时，可以得到以下结论:
- 如果 $s[i] =
0$，此时我们肯定可以将0直接加入到最长长度为 $m$ 的字符串的末尾，此时最大长度变为 $m + 1$, 且最大长度为 $k + 1$ 的最小值为 $dp[m + 1] = dp[m]$; - 如果 $s[i] =
1$，此时我们先检测是否可以将1直接加入到最长长度为 $m$ 的字符串的末尾，如果满足加入后的值仍然小于等于 $k$，此时最大长度变为 $k + 1$，且最大长度为 $m + 1$ 的最小值为 $dp[m + 1] = dp[m] | (1<<m)$;如果不能满足加入后的值小于等于 $k$, 则此时我们尝试将其加入到长度为 $m-1$ 的字符串末尾，如果满足加入后的值小于 $dp[m]$，则此时我们应当加入到 $m-1$ 的字符串末尾，此时需要更新 $dp[m]$。
- 如果 $s[i] =
- 复杂度分析：
- 时间复杂度：$O(k \times 3 ^ n)$, 其中 $k$ 人数，$n$ 表示饼干的数目。
- 空间复杂度：$O(k \times 2 ^ n)$，其中 $k$ 人数，$n$ 表示饼干的数目, 可以进行滚动数组优化空间为 $2^n$。
代码
dp:class Solution {
public:
int longestSubsequence(string s, int k) {
int n = s.size();
vector<pair<int, int>> dp(n + 1);
reverse(s.begin(), s.end());
dp[0].first = 0;
dp[0].second = 0;
for (int i = 1; i <= n; i++) {
dp[i].first = dp[i-1].first;
dp[i].second = dp[i-1].second;
if (s[i - 1] == '0') {
dp[i].first = dp[i-1].first + 1;
dp[i].second = dp[i-1].second;
} else {
for (int j = i - 1; j >= 0; j--) {
if (dp[j].first < 30) {
long long curr = (1LL << dp[j].first)|dp[j].second;
if (curr <= k) {
if (dp[j].first + 1 > dp[i].first ||
(dp[j].first + 1 == dp[i].first &&
dp[i].second > curr)) {
dp[i].first = dp[j].first + 1;
dp[i].second = curr;
}
}
}
}
}
}
return dp[n].first;
}
};dp:class Solution {
public:
int longestSubsequence(string s, int k) {
int n = s.size();
int res = 0;
vector<int> dp(n + 1, -1);
reverse(s.begin(), s.end());
dp[0] = 0;
for (int i = 1; i <= n; i++) {
if (s[i - 1] == '0') {
dp[res + 1] = dp[res];
res++;
} else {
if (res < 31) {
long long curr = dp[res] | (1 << res);
if (curr <= k) {
dp[res + 1] = curr;
res++;
} else {
if (res > 1) {
curr = dp[res - 1] | (1 << (res - 1));
if (curr <= dp[res]) {
dp[res] = curr;
}
}
}
}
}
}
return res;
}
};
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]] |
示例 2：
输入：m = 4, n = 6, prices = [[3,2,10],[1,4,2],[4,1,3]] |
提示：
1 <= m, n <= 2001 <= prices.length <= 2 * 104prices[i].length == 31 <= hi <= m1 <= wi <= n1 <= pricei <= 106- 所有
(hi, wi)互不相同 。
地址
https://leetcode.cn/problems/selling-pieces-of-wood
题意
动态规划或者记忆化搜索
思路
- 题目出的比较新颖，比较有意思的题目。分析题目可以知道相同的 $m \times n$ 的木块所能得到最大值应该是相同的，且他们之间是独立的互不影响。对于 $m \times n$ 的木块一共有 $m + n - 2$ 种不同的切法，比如依次沿着垂直方向可以切 $n-1$ 次，依次沿着水平方向可以有 $m-1$ 次切法，因此设 $dp[m][n]$ 表示 $m \times n$ 大小的木块所能获取的最大值，则根据上述推论可以知道:
- 一共有 $m + n - 2$ 种不同的切法:
- 假设沿着水平方向切，则有 $m - 1$ 种不同的切法，假设从第 $k$ 行切开，则可以得到 $k \times n, (m - k) \times n $ 两块不同的木块，则可以知道此时 $dp[m][n] = \max(dp[k][n] + dp[m-k][n]) \quad k \in [1,m-1]$。
- 假设沿着垂直方向切，则有 $n - 1$ 种不同的切法，假设从第 $k$ 列切开，则可以得到 $ m \times k, m \times (n - k) $ 两块不同的木块，则可以知道此时 $dp[m][n] = \max(dp[m][k] + dp[m][n-k]) \quad k \in [1,n-1]$。
- 复杂度分析：
- 时间复杂度：$m \times n \times (m + n) $，其中 $m$ 行数， $n$ 表示列数。
- 空间复杂度：$m \times n$, 其中 $m$ 行数， $n$ 表示列数。
代码
class Solution { |
欢迎关注和打赏，感谢支持！
- 关注我的博客: http://mikemeng.org/
- 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
- 关注我的微信公众号: 公务程序猿
扫描二维码，分享此文章