leetcode contest 388

T4 题目确实不错的题目，值得好好思考的题目。

3074. 重新分装苹果

给你一个长度为 n 的数组 apple 和另一个长度为 m 的数组 capacity 。

一共有 n 个包裹，其中第 i 个包裹中装着 apple[i] 个苹果。同时，还有 m 个箱子，第 i 个箱子的容量为 capacity[i] 个苹果。

请你选择一些箱子来将这 n 个包裹中的苹果重新分装到箱子中，返回你需要选择的箱子的最小数量。

注意，同一个包裹中的苹果可以分装到不同的箱子中。

示例 1：

输入：apple = [1,3,2], capacity = [4,3,1,5,2]
输出：2
解释：使用容量为 4 和 5 的箱子。
总容量大于或等于苹果的总数，所以可以完成重新分装。

示例 2：

输入：apple = [5,5,5], capacity = [2,4,2,7]
输出：4
解释：需要使用所有箱子。

提示：

1 <= n == apple.length <= 50
1 <= m == capacity.length <= 50
1 <= apple[i], capacity[i] <= 50
输入数据保证可以将包裹中的苹果重新分装到箱子中。

地址

https://leetcode.cn/contest/weekly-contest-388/problems/apple-redistribution-into-boxes/

题意

贪心

思路

题目要求最少的箱子，则我们应该尽量选择容量最大的箱子即可，知道箱子的总容量能够满足装满所有的苹果即可。
复杂度分析：

时间复杂度：$O(n \log n)$，其中 $n$ 表示给定数组的长度。
空间复杂度：$O(\log n)$，其中 $n$ 表示给定数组的长度。

代码

class Solution:
    def minimumBoxes(self, apple: List[int], capacity: List[int]) -> int:
        capacity.sort()
        tot = sum(apple)
        now = 0
        res = 0
        for i in range(len(capacity) - 1, -1, -1):
            now += capacity[i]
            res += 1
            if now >= tot:
                return res
        return res

use std::cmp::Reverse;

impl Solution {
    pub fn minimum_boxes(apple: Vec<i32>, capacity: Vec<i32>) -> i32 {
        let mut arr = capacity.to_vec();
        arr.sort_by_key(|&x| Reverse(x));
        let tot: i32 = apple.iter().sum();
        let mut now = 0;
        let mut res = 0;
        for &i in arr.iter() {
            now += i;
            res += 1;
            if now >= tot {
                return res;
            }
        }
        res
    }
}

3075. 幸福值最大化的选择方案

给你一个长度为 n 的数组 happiness ，以及一个 正整数 k 。

n 个孩子站成一队，其中第 i 个孩子的 幸福值 是 happiness[i] 。你计划组织 k 轮筛选从这 n 个孩子中选出 k 个孩子。

在每一轮选择一个孩子时，所有尚未被选中的孩子的 幸福值 将减少 1 。注意，幸福值不能变成负数，且只有在它是正数的情况下才会减少。

选择 k 个孩子，并使你选中的孩子幸福值之和最大，返回你能够得到的 最大值 。

示例 1：

输入：happiness = [1,2,3], k = 2
输出：4
解释：按以下方式选择 2 个孩子：
- 选择幸福值为 3 的孩子。剩余孩子的幸福值变为 [0,1] 。
- 选择幸福值为 1 的孩子。剩余孩子的幸福值变为 [0] 。注意幸福值不能小于 0 。
所选孩子的幸福值之和为 3 + 1 = 4 。

示例 2：

输入：happiness = [1,1,1,1], k = 2
输出：1
解释：按以下方式选择 2 个孩子：
- 选择幸福值为 1 的任意一个孩子。剩余孩子的幸福值变为 [0,0,0] 。
- 选择幸福值为 0 的孩子。剩余孩子的幸福值变为 [0,0] 。
所选孩子的幸福值之和为 1 + 0 = 1 。

示例 3：

输入：happiness = [2,3,4,5], k = 1
输出：5
解释：按以下方式选择 1 个孩子：
- 选择幸福值为 5 的孩子。剩余孩子的幸福值变为 [1,2,3] 。
所选孩子的幸福值之和为 5 。

提示：

1 <= n == happiness.length <= 2 * 105
1 <= happiness[i] <= 108
1 <= k <= n

地址

https://leetcode.cn/contest/weekly-contest-388/problems/maximize-happiness-of-selected-children/

题意

排序

思路

根据题目要求，首先将数组按照从大到小排序，每次取出最大的元素，由于题目每次所有元素都会减 $1$，所有元素的大小关系不会变，我们直接取 $k$ 个最大的元素即可。
复杂度分析：

时间复杂度：$O(n \log n)$，其中 $n$ 表示给定数组的长度。
空间复杂度：$O(\log n)$, 其中 $n$ 表示给定数组的长度。

代码

class Solution:
    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
        n = len(happiness)
        res = 0
        happiness.sort(reverse = True)
        for i, x in enumerate(happiness[:k]):
            res += max(x - i, 0)
        return res

impl Solution {
    pub fn maximum_happiness_sum(happiness: Vec<i32>, k: i32) -> i64 {
        let mut happiness = happiness.to_vec();
        let n = happiness.len();
        let mut res = 0;
        happiness.sort_by(|a, b| b.cmp(a)); // sort in descending order
        for (i, &x) in happiness.iter().enumerate().take(k as usize) {
            res += std::cmp::max(x - (i as i32), 0) as i64;
        }
        res
    }
}

3076. 数组中的最短非公共子字符串

给你一个数组 arr ，数组中有 n 个非空字符串。

请你求出一个长度为 n 的字符串 answer ，满足：

answer[i] 是 arr[i] 最短的子字符串，且它不是 arr 中其他任何字符串的子字符串。如果有多个这样的子字符串存在，answer[i] 应该是它们中字典序最小的一个。如果不存在这样的子字符串，answer[i] 为空字符串。

请你返回数组 answer 。

示例 1：

输入：arr = ["cab","ad","bad","c"]
输出：["ab","","ba",""]
解释：求解过程如下：
- 对于字符串 "cab" ，最短没有在其他字符串中出现过的子字符串是 "ca" 或者 "ab" ，我们选择字典序更小的子字符串，也就是 "ab" 。
- 对于字符串 "ad" ，不存在没有在其他字符串中出现过的子字符串。
- 对于字符串 "bad" ，最短没有在其他字符串中出现过的子字符串是 "ba" 。
- 对于字符串 "c" ，不存在没有在其他字符串中出现过的子字符串。

示例 2：

输入：arr = ["abc","bcd","abcd"]
输出：["","","abcd"]
解释：求解过程如下：
- 对于字符串 "abc" ，不存在没有在其他字符串中出现过的子字符串。
- 对于字符串 "bcd" ，不存在没有在其他字符串中出现过的子字符串。
- 对于字符串 "abcd" ，最短没有在其他字符串中出现过的子字符串是 "abcd" 。

提示：

n == arr.length
2 <= n <= 100
1 <= arr[i].length <= 20
arr[i] 只包含小写英文字母。

地址

https://leetcode.cn/contest/weekly-contest-388/problems/shortest-uncommon-substring-in-an-array/

题意

模拟

思路

题目非常简单的暴力即可，枚举每个字符的所有的子字符串，并检测该字符串是否在其他字符串中出现过，找到最短且字典序最小的即可。
复杂度分析：

时间复杂度：$O(n^2m^4)$, $n$ 表示给定字符串数组的长度， $m$ 表示字符串的长度；
空间复杂度：$O(n)$,, $n$ 表示给定节点的数目;

代码

class Solution:
    def shortestSubstrings(self, arr: List[str]) -> List[str]:
        def check(i, sub) -> bool:
            for j, s in enumerate(arr):
                if j != i and sub in s:
                    return False
            return True
        
        ans = []
        for i, s in enumerate(arr):
            cur = ""
            for j in range(len(s)):
                for k in range(j, len(s)):
                    t = s[j : k + 1]
                    if check(i, t):
                        if not cur or len(cur) > len(t) or (len(cur) == len(t) and t < cur):
                            cur = t 
            ans.append(cur)
        return ans

impl Solution {
    pub fn shortest_substrings(arr: Vec<String>) -> Vec<String> {
         fn check(i: usize, sub: &str, arr: &Vec<String>) -> bool {
            for (j, s) in arr.iter().enumerate() {
                if j != i && s.contains(sub) {
                    return false;
                }
            }
            true
        }
        
        let mut ans = Vec::new();
        for (i, s) in arr.iter().enumerate() {
            let mut cur = String::new();
            for j in 0..s.len() {
                for k in j..s.len() {
                    let t = &s[j..=k];
                    if check(i, t, &arr) {
                        if cur.is_empty() || cur.len() > t.len() || (cur.len() == t.len() && t < &cur) {
                            cur = t.to_string();
                        }
                    }
                }
            }
            ans.push(cur);
        }
        ans
    }
}

3077. K 个不相交子数组的最大能量值

给你一个长度为 n 下标从 0 开始的整数数组 nums 和一个 正奇数 整数 k 。

x 个子数组的能量值定义为 strength = sum[1] * x - sum[2] * (x - 1) + sum[3] * (x - 2) - sum[4] * (x - 3) + ... + sum[x] * 1 ，其中 sum[i] 是第 i 个子数组的和。更正式的，能量值是满足 1 <= i <= x 的所有 i 对应的 (-1)i+1 * sum[i] * (x - i + 1) 之和。

你需要在 nums 中选择 k 个 不相交****子数组 ，使得 能量值最大 。

请你返回可以得到的 最大****能量值 。

注意，选出来的所有子数组不需要覆盖整个数组。

示例 1：

输入：nums = [1,2,3,-1,2], k = 3
输出：22
解释：选择 3 个子数组的最好方式是选择：nums[0..2] ，nums[3..3] 和 nums[4..4] 。能量值为 (1 + 2 + 3) * 3 - (-1) * 2 + 2 * 1 = 22 。

示例 2：

输入：nums = [12,-2,-2,-2,-2], k = 5
输出：64
解释：唯一一种选 5 个不相交子数组的方案是：nums[0..0] ，nums[1..1] ，nums[2..2] ，nums[3..3] 和 nums[4..4] 。能量值为 12 * 5 - (-2) * 4 + (-2) * 3 - (-2) * 2 + (-2) * 1 = 64 。

示例 3：

输入：nums = [-1,-2,-3], k = 1
输出：-1
解释：选择 1 个子数组的最优方案是：nums[0..0] 。能量值为 -1 。

提示：

1 <= n <= 104
-109 <= nums[i] <= 109
1 <= k <= n
1 <= n * k <= 106
k 是奇数。

地址

https://leetcode.cn/contest/weekly-contest-388/problems/maximum-strength-of-k-disjoint-subarrays/

题意

动态规划

思路

确实是个不错的动态规划的题目，还是有一点思维难度，但是题目的关键在于如何破题，题目关键提示在于 $0\le n \times k \le 6000$ 是个关键提示的地方，这意味着题目的解法的复杂度为 $nk$，此时如何破解，首先我们可以设 $f(i,j)$ 表示前 $i$ 个元素可以分为 $j$ 组构成的最大值，$g(i,j)$ 表示前 $i$ 个元素可以分组为 $j$ 组构成的最小值，但是似乎我们顺着遍历时，发现转移方程无法写，比如 $f(i,j)$ 转移到 $f(i+1,j)$ 时的转移方程无法写，此时我们可以换一种思路，倒着遍历。$f(i,j), g(i,j)$ 分别表示子数组从 $i$ 到 $n-1$ 范围内挑选 $j$ 个不相交的分组所构成的最大值与最小值，此时假设当前遍历第 $i$ 个元素时，有两种选择:
- $nums[i]$ 作为一个单独的分组，再加区间 $[i+1,n-1]$ 构成的 $j-1$ 个分组，一起构成 $j$ 个分组，此时需要减去 $j-1$ 个分组的最小值，此时可以得到递推公式为:
  
  $$ f[i][j] = \max(f[i][j], nums[i] * j - g[i+1][j-1]), g[i][j] = min(g[i][j], nums[i] * j - f[i+1][j-1])$$
- $nums[i]$ 不作为一个单独的分组，再加区间 $[i+1,n-1]$ 的第一个分组一起构成一个分组，一起构成 $j$ 个分组，此时需要减去 $j-1$ 个分组的最小值，此时可以得到递推公式为:
  
  $$ f[i][j] = \max(f[i][j], nums[i] * j + f[i+1][j]), g[i][j] = min(g[i][j], nums[i] * j + g[i+1][j])$$
根据上述的递推公式，我们求出所有可能分组的最大值，此时返回最大的 $f[i][k]$ 即可，题目本身不算很难，可惜的是比赛的时候没有看到题目条件。
复杂度分析：

时间复杂度：$O(nk)$，其中 $n$ 表示给定数组的长度，$k$ 表示给定的整数。
空间复杂度：$O(nk)$，其中 $n$ 表示给定数组的长度，$k$ 表示给定的整数。

代码

class Solution:
    def maximumStrength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp_max = [[-inf] * (n + 1) for _ in range(k + 1)]
        dp_min = [[ inf] * (n + 1) for _ in range(k + 1)]
        dp_max[1][n], dp_min[1][n] = 0, 0
        for i in range(n - 1, -1, -1):
            dp_max[1][i] = nums[i] + max(0, dp_max[1][i + 1])
            dp_min[1][i] = nums[i] + min(0, dp_min[1][i + 1])
        
        for i in range(2, k + 1):
            for j in range(n - i, -1, -1):
                dp_max[i][j] = i * nums[j] - dp_min[i - 1][j + 1]
                dp_min[i][j] = i * nums[j] - dp_max[i - 1][j + 1]
                if n - j != i:
                    dp_max[i][j] = max(dp_max[i][j], i * nums[j] + dp_max[i][j + 1])
                    dp_min[i][j] = min(dp_min[i][j], i * nums[j] + dp_min[i][j + 1])
        res = -inf
        for i in range(n):
            res = max(res, dp_max[k][i])
        return res

use std::cmp::{max, min};

impl Solution {
    pub fn maximum_strength(nums: Vec<i32>, k: i32) -> i64 {
        let n = nums.len();
        let mut dp_max: Vec<Vec<i64>> = vec![vec![-i64::MAX; n + 1 as usize]; k as usize + 1];
        let mut dp_min: Vec<Vec<i64>> = vec![vec![i64::MAX; n + 1 as usize]; k as usize + 1];
        dp_max[1][n as usize] = 0 as i64;
        dp_min[1][n as usize] = 0 as i64;

        for i in (0..n).rev() {
            dp_max[1][i] = nums[i] as i64 + max(0, dp_max[1][i + 1]);
            dp_min[1][i] = nums[i] as i64 + min(0, dp_min[1][i + 1]);
        }

        for i in 2..=k as usize {
            for j in (0..=(n as usize - i)).rev() {
                dp_max[i][j] = i as i64 * nums[j] as i64 - dp_min[i - 1][j + 1];
                dp_min[i][j] = i as i64 * nums[j] as i64 - dp_max[i - 1][j + 1];
                if n - j != i {
                    dp_max[i][j] = max(dp_max[i][j], i as i64 * nums[j] as i64 + dp_max[i][j + 1]);
                    dp_min[i][j] = min(dp_min[i][j], i as i64 * nums[j] as i64 + dp_min[i][j + 1]);
                }
            }
        }

        let mut res = -i64::MAX;
        for i in 0..n {
            res = max(res, dp_max[k as usize][i]);
        }
        res
    }
}

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

关注我的博客: https://mike-box.github.io/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu

Tags: 题解力扣周赛赛

← leetcode biweekly contest 125 leetcode biweekly contest 126 →

扫描二维码，分享此文章