🏆 第 298 场力扣周赛

没想太明白，瞎搞肯定有问题

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

给你一个由英文字母组成的字符串 s ，请你找出并返回 s 中的 最好 英文字母。返回的字母必须为大写形式。如果不存在满足条件的字母，则返回一个空字符串。
最好 英文字母的大写和小写形式必须 都 在 s 中出现。
英文字母 b 比另一个英文字母 a 更好 的前提是：英文字母表中，b 在 a 之 后 出现。

示例 1：
输入：s = “lEe_TcOdE“ 输出：“E” 解释： 字母 ‘E’ 是唯一一个大写和小写形式都出现的字母。
示例 2：
输入：s = “arR_AzFif” 输出：“R” 解释： 字母 ‘R’ 是大写和小写形式都出现的最好英文字母。 注意 ‘A’ 和 ‘F’ 的大写和小写形式也都出现了，但是 ‘R’ 比 ‘F’ 和 ‘A’ 更好。
示例 3：
输入：s = “AbCdEfGhIjK” 输出：“” 解释： 不存在大写和小写形式都出现的字母。

提示：

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

思路：
模拟

class Solution {
    public String greatestLetter(String s) {
        boolean[] b1 = new boolean[26];
        boolean[] b2 = new boolean[26];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= 'a' && c <= 'z')
                b1[c - 'a'] = true;
            else
                b2[c - 'A'] = true;
        }
        int idx = -1;
        for (int i = 0; i < 26; i++) {
            if (b1[i] && b2[i])
                idx = i;
        }
        if (idx == -1) return "";
        else return (char)('A' + idx) + "";
    }
}

// 更容易的写法
class Solution {
    public String greatestLetter(String s) {
        for (char a = 'Z'; a >= 'A'; a--) {
            if (s.indexOf(a) >= 0 && s.indexOf(a - 'A' + 'a') >= 0)
                return a + "";
        }
        return "";
    }
}

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

思路：
个位数均相同，考虑[0 - 9]个k是否能凑出num的个位数

class Solution {
    public int minimumNumbers(int num, int k) {
        if (num == 0) return 0;
        for (int i = 1; i <= 10; i++) {
            if (k * i % 10 == num % 10 && 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

思路：
贪心
统计0的次数，倒着考虑哪些1可以加入
时间复杂度：O(n)

class Solution {
    public int longestSubsequence(String s, int k) {
        int cnt = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '0')
                cnt++;
        }
        long val = 0;
        int res = cnt;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == '1') {
                if (n - i > 30 || val + (1 << n - i - 1) > k)
                    break;
                else {
                    res++;
                    val |= 1 << (n - i - 1);
                }
            }
        }
        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) 互不相同 。

思路：
DP
状态表示：f[i][j]表示高为i，宽为j的木块的最大收益
状态转移：考虑最后一步按行切还是按列切
f[i][j] = Math.max(f[i][j], Math.max(f[i - h][j] + a[h][j], f[i - h][j] + f[h][j]))
f[i][j] = Math.max(f[i][j], Math.max(f[i][j - w] + a[i][w], f[i][j - w] + f[i][w]))

class Solution {
    public long sellingWood(int n, int m, int[][] prices) {
        final int N = 200;
        int[][] a = new int[N + 1][N + 1];
        for (int[] p : prices) {
            int h = p[0], w = p[1], c = p[2];
            a[h][w] = c;
        }
        long[][] f = new long[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int h = 1; h <= i; h++)
                    f[i][j] = Math.max(f[i][j], Math.max(f[i - h][j] + a[h][j], f[i - h][j] + f[h][j]));
                for (int w = 1; w <= j; w++)
                    f[i][j] = Math.max(f[i][j], Math.max(f[i][j - w] + a[i][w], f[i][j - w] + f[i][w]));
            }
        }
        return f[n][m];
    }
}

// 记忆化
class Solution {
    int[][] a = new int[201][201];
    long[][] f = new long[201][201];
    public long sellingWood(int n, int m, int[][] prices) {
        for (int[] p : prices) {
            int h = p[0], w = p[1], c = p[2];
            a[h][w] = c;
        }
        for (int i = 1; i <= 200; i++) {
            Arrays.fill(f[i], -1);
            f[i][0] = 0;
        }
        return dfs(n, m);
    }
    long dfs(int n, int m) {
        if (f[n][m] != -1)
            return f[n][m];
        long max = a[n][m];
        for (int i = 1; i < n; i++) {
            max = Math.max(dfs(i, m) + dfs(n - i, m), max);
            max = Math.max(a[i][m] + dfs(n - i, m), max);
        }
        for (int j = 1; j < m; j++) {
            max = Math.max(dfs(n, j) + dfs(n, m - j), max);
            max = Math.max(a[n][j] + dfs(n, m - j), max);
        }
        return (f[n][m] = max);
    }
}