leetcode contest biweekly 298

leetcode contest biweekly 298

周末太匆忙，没有时间细想，打卡补题解。感觉第三题比第四题难。

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

题目

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

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

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

示例 1：

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

示例 2：

输入：s = "arRAzFif"
输出："R"
解释：
字母 'R' 是大写和小写形式都出现的最好英文字母。
注意 'A' 和 'F' 的大写和小写形式也都出现了，但是 'R' 比 'F' 和 'A' 更好。

示例 3：

输入：s = "AbCdEfGhIjK"
输出：""
解释：
不存在大写和小写形式都出现的字母。

提示：

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

地址

https://leetcode.cn/problems/greatest-english-letter-in-upper-and-lower-case

题意

直接遍历

思路

1. 我们依次遍历数组即可，找到所有同时出现大写和小写形式，找到字典序最大的字母即可。
2. 复杂度分析：

• 时间复杂度：$O(n + \Sigma)$, 其中 $n$ 为字符串的长度。
• 空间复杂度：$O(\Sigma)$。

  代码

  class Solution {
  public:
      string greatestLetter(string s) {
          vector<vector<bool>> cnt(26, vector<bool>(2));
          string res = " ";
          for (auto & c : s) {
              int x = tolower(c) - 'a';
              if (islower(c)) {
                  cnt[x][0] = true;
              } else {
                  cnt[x][1] = true;
              }
          }
          for (int i = 0; i < 26; i++) {
              if (cnt[i][0] && cnt[i][1]) {
                  res[0] = 'A' + i;
              }
          }
          return res[0] == ' ' ? "" : res;
      }
  };

5218. 个位数字为 K 的整数之和

题目

给你两个整数 num 和 k，考虑具有以下属性的正整数多重集：

• 每个整数个位数字都是 k 。
• 所有整数之和是 num 。
• 返回该多重集的最小大小，如果不存在这样的多重集，返回 -1 。

注意：
多重集与集合类似，但多重集可以包含多个同一整数，空多重集的和为 0 。
个位数字 是数字最右边的数位。

示例 1：

输入：num = 58, k = 9
输出：2
解释：
多重集 [9,49] 满足题目条件，和为 58 且每个整数的个位数字是 9 。
另一个满足条件的多重集是 [19,39] 。
可以证明 2 是满足题目条件的多重集的最小长度。

示例 2：

输入：num = 37, k = 2
输出：-1
解释：个位数字为 2 的整数无法相加得到 37 。

示例 3：

输入：num = 0, k = 7
输出：0
解释：空多重集的和为 0 。

提示：

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

地址

https://leetcode.cn/problems/sum-of-numbers-with-units-digit-k

题意

数学问题

思路

1. 简单的数学问题，分析如下:

• 如果 $num = 0$ 此时我们应该直接返回 $0$.
• 假设最小长度为 $n$，则可以知道 $n \times k$ 的个位数一定与 $num$ 的个位数相等，且必须满足 $ n \times k \le num$.
• 由于题目中允许重复的元素，且满足长度最小，则假设我们已经找到最小的 $n$ 满足上述条件，则可以知道 $num$ 一定可以被拆解成 $n$ 个个位数字为 $k$ 的正整数，已知 $num = (n-1) k + (num - nk) + k$，则可以拆分如下 :
  $[k,k,k,\cdots, (num - (n-1)*k)]$，且满足 $num - (n-1) \times k$ 的个位数字一定为 $k$。

1. 复杂度分析：

• 时间复杂度：$O(C)$，其中 $C = 10$。
• 空间复杂度：$O(1)$。

  代码

  class Solution {
  public:
      int minimumNumbers(int num, int k) {
          if (num == 0) {
              return 0;
          }
          int x = num % 10;
          for (int i = 1; i <= 10; i++) {
              if (((k * i) % 10) == x && (k * i <= num)) {
                  return i;
              }
          }
          return -1;
      }
  };

6099. 小于等于 K 的最长二进制子序列

题目

给你一个二进制字符串 s 和一个正整数 k 。

请你返回 s 的 最长 子序列，且该子序列对应的 二进制 数字小于等于 k 。

注意：

• 子序列可以有 前导 0 。
• 空字符串视为 0 。
• 子序列 是指从一个字符串中删除零个或者多个字符后，不改变顺序得到的剩余字符序列。

示例 1：

输入：s = "1001010", k = 5
输出：5
解释：s 中小于等于 5 的最长子序列是 "00010" ，对应的十进制数字是 2 。
注意 "00100" 和 "00101" 也是可行的最长子序列，十进制分别对应 4 和 5 。
最长子序列的长度为 5 ，所以返回 5 。

示例 2：

输入：s = "00101001", k = 1
输出：6
解释："000001" 是 s 中小于等于 1 的最长子序列，对应的十进制数字是 1 。
最长子序列的长度为 6 ，所以返回 6 。

提示：

• 1 <= s.length <= 1000
• s[i] 要么是 '0' ，要么是 '1' 。
• 1 <= k <= 109

地址

https://leetcode.cn/problems/longest-binary-subsequence-less-than-or-equal-to-k

题意

动态规划

思路

1. 典型的动态规划思路，为了方便计算，我们首先将字符串进行逆序处理。设 $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)$。

1. 贪心法，解法比较巧妙，可以参考题解，只用 $O(n)$ 的复杂度即可。
2. 动态规划二:

• 设 $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]$。

1. 复杂度分析：

• 时间复杂度：$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]]
输出：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 元是最多能得到的钱数。

示例 2：

输入：m = 4, n = 6, prices = [[3,2,10],[1,4,2],[4,1,3]]
输出：32
解释：上图展示了一个可行的方案。包括：
- 3 块 3 x 2 的小木块，售出 3 * 10 = 30 元。
- 1 块 1 x 4 的小木块，售出 1 * 2 = 2 元。
总共售出 30 + 2 = 32 元。
32 元是最多能得到的钱数。
注意我们不能旋转 1 x 4 的木块来得到 4 x 1 的木块。

提示：

• 1 <= m, n <= 200
• 1 <= prices.length <= 2 * 104
• prices[i].length == 3
• 1 <= hi <= m
• 1 <= wi <= n
• 1 <= pricei <= 106
• 所有 (hi, wi) 互不相同 。

地址

https://leetcode.cn/problems/selling-pieces-of-wood

题意

动态规划或者记忆化搜索

思路

1. 题目出的比较新颖，比较有意思的题目。分析题目可以知道相同的 $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]$。

1. 复杂度分析：

• 时间复杂度：$m \times n \times (m + n) $，其中 $m$ 行数， $n$ 表示列数。
• 空间复杂度：$m \times n$, 其中 $m$ 行数， $n$ 表示列数。

代码

class Solution {
public:
    long long sellingWood(int m, int n, vector<vector<int>>& prices) {
        long long res = 0;
        int k = prices.size();
        vector<vector<long long>> dp(m + 1, vector<long long>(n + 1));
        for (auto & v : prices) {
            dp[v[0]][v[1]] = v[2];
        }
        for (int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                /* vertical */
                for (int k = 1; k < j; k++) {
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k]);
                }
                /* horizontal */
                for (int k = 1; k < i; k++) {
                    dp[i][j] = max(dp[i][j], dp[k][j] + dp[i - k][j]);
                }
            }
        }
        return dp[m][n];
    }
};

#

欢迎关注和打赏，感谢支持！

• 关注我的博客: http://mikemeng.org/
• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
• 关注我的微信公众号: 公务程序猿