1、3074. 重新分装苹果

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

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

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

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

示例 1：

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

示例 2：

1
2
3
输入：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
输入数据保证可以将包裹中的苹果重新分装到箱子中。

傻瓜题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int minimumBoxes(int[] apple, int[] capacity) {
        int res=0;
        int sum=0;
        for(int num:apple){
            sum+=num;
        }
        Arrays.sort(capacity);
        for(int i=capacity.length-1;i>=0&&sum>0;i--){
            sum-=capacity[i];
            res++;
        }
        return res;
    }
}

rust

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
impl Solution {
    pub fn minimum_boxes(apple: Vec<i32>, mut capacity: Vec<i32>) -> i32 {
        capacity.sort_unstable_by_key(|x| -x);
        capacity
            .into_iter()
            .scan(0, |s, x| { *s += x; Some(*s) })
            .collect::<Vec<_>>()
            .partition_point(|x| *x < apple.iter().sum()) as i32 + 1
    }   
}

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

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

1
2
3
4
5
输入：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

也是一个简单题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public long maximumHappinessSum(int[] happiness, int k) {
        long res=0;
        Arrays.sort(happiness);
        for(int i=0;i<k&&happiness[happiness.length-1-i]-i>0;i++){
            res+=happiness[happiness.length-1-i]-i;
        }
        return res;
    }
}

rust：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
impl Solution {
    pub fn maximum_happiness_sum(happiness: Vec<i32>, k: i32) -> i64 {
        let mut h = happiness;
        h.sort_unstable_by(|a, b| b.cmp(&a));

        let mut ans = 0i64;
        let mut s = 0i64;
        for i in 0..k {
            if i > h[i as usize] {
                break;
            }
            
            ans += (h[i as usize] as i64 - i as i64).max(0);
        }

        ans
    }
}

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

中等

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

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

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

请你返回数组 answer 。

示例 1：

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

示例 2：

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

提示：

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

就是一道单纯的暴力题，虽然题目暴力，但是考验代码功底，初学者很容易写的又臭又长

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public String[] shortestSubstrings(String[] arr) {
        // 茶神简洁写法
        int n=arr.length;
        String[] ans=new String[n];
        for(int i=0;i<n;i++){
            int m=arr[i].length();
            String res="";
            for(int size=1;size<=m&&res.isEmpty();size++){
                for(int j=size;j<=m;j++){
                    String t=arr[i].substring(j-size,j);
                    if((res.isEmpty()||t.compareTo(res)<0)&&check(arr,i,t)){
                        res=t;
                    }
                }
            }

            ans[i]=res;
        }
        return ans;
    }

    private boolean check(String[] arr,int i,String sub){
        for(int j=0;j<arr.length;j++){
            if(j!=i&&arr[j].contains(sub)){
                return false;
            }
        }
        return true;
    }
}

4、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：

1
2
3
输入：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：

1
2
3
输入：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：

1
2
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 是奇数。