100233. Apple Redistribution into Boxes
给你一个长度为 n 的数组 apple 和另一个长度为 m 的数组 capacity 。
一共有 n 个包裹，其中第 i 个包裹中装着 apple[i] 个苹果。同时，还有 m 个箱子，第 i 个箱子的容量为 capacity[i] 个苹果。
请你选择一些箱子来将这 n 个包裹中的苹果重新分装到箱子中，返回你需要选择的箱子的 最小 数量。
注意，同一个包裹中的苹果可以分装到不同的箱子中。
测试样例：
输入：apple = [1,3,2], capacity = [4,3,1,5,2]
输出：2
解释：使用容量为 4 和 5 的箱子。总容量大于或等于苹果的总数，所以可以完成重新分装。
解答：选择最大的capacity装苹果。
class Solution {
public int minimumBoxes(int[] apple, int[] capacity) {
int sum = 0;
for (int n : apple) {
sum += n;
}
Arrays.sort(capacity);
int res = 0;
for (int i = capacity.length - 1; i >= 0; --i) {
sum -= capacity[i];
++res;
if (sum <= 0) {
return res;
}
}
return -1;
}
}100247. Maximize Happiness of Selected Children
给你一个长度为 n 的数组 happiness ，以及一个 正整数 k 。
n 个孩子站成一队，其中第 i 个孩子的 幸福值 是 happiness[i] 。你计划组织 k 轮筛选从这 n 个孩子中选出 k 个孩子。
在每一轮选择一个孩子时，所有 尚未 被选中的孩子的 幸福值 将减少 1 。注意，幸福值 不能 变成负数，且只有在它是正数的情况下才会减少。
选择 k 个孩子，并使你选中的孩子幸福值之和最大，返回你能够得到的 最大值 。
测试样例：
输入：happiness = [1,2,3], k = 2
输出：4
解释：按以下方式选择 2 个孩子：
- 选择幸福值为 3 的孩子。剩余孩子的幸福值变为 [0,1] 。
- 选择幸福值为 1 的孩子。剩余孩子的幸福值变为 [0] 。注意幸福值不能小于 0 。
所选孩子的幸福值之和为 3 + 1 = 4 。
解答：排序之后优先选择最大幸福的小孩，因为幸福值不能变为负数，所以较小的数反而可能幸福下降的少。
class Solution {
public long maximumHappinessSum(int[] happiness, int k) {
Arrays.sort(happiness);
long res = 0;
for (int i = happiness.length - 1, j = 0; i >= 0 && j < k; --i, ++j) {
res += Math.max(happiness[i] - j, 0);
}
return res;
}
}100251. Shortest Uncommon Substring in an Array
给你一个数组 arr ，数组中有 n 个 非空 字符串。
请你求出一个长度为 n 的字符串 answer ，满足：
- answer[i] 是 arr[i] 最短 的子字符串，且它不是 arr 中其他任何字符串的子字符串。如果有多个这样的子字符串存在，answer[i] 应该是它们中字典序最小的一个。如果不存在这样的子字符串，answer[i] 为空字符串。
请你返回数组 answer 。
测试样例：
输入：arr = ["cab","ad","bad","c"]
输出：["ab","","ba",""]
解释：求解过程如下：
- 对于字符串 "cab" ，最短没有在其他字符串中出现过的子字符串是 "ca" 或者 "ab" ，我们选择字典序更小的子字符串，也就是 "ab" 。
- 对于字符串 "ad" ，不存在没有在其他字符串中出现过的子字符串。
- 对于字符串 "bad" ，最短没有在其他字符串中出现过的子字符串是 "ba" 。
- 对于字符串 "c" ，不存在没有在其他字符串中出现过的子字符串。
解答：没想到好的办法，我用了暴力。强行每个字符串从每个位置搜索最长可匹配的字串。那么不可匹配的就是从当前位置的最佳字串。然后寻找最短的。
class Solution {
public String[] shortestSubstrings(String[] arr) {
String[] res = new String[arr.length];
for (int i = 0; i < arr.length; ++i) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < arr[i].length(); ++j) {
sb.append(arr[i].charAt(j));
int[] fail = buildFail(sb);
int minBestMatch = j + 1;
for (int k = 0; k < arr.length; ++k) {
if (k != i) {
int bestMatch = kmp(arr[k], fail, sb);
minBestMatch = Math.min(minBestMatch, bestMatch);
if (bestMatch == 0) {
break;
}
}
}
if (minBestMatch != 0) {
int len = j + 1 - minBestMatch + 1;
if (res[i] == null || len <= res[i].length()) {
String tmp = arr[i].substring(minBestMatch - 1, j + 1);
if (res[i] != null && len == res[i].length()) {
res[i] = tmp.compareTo(res[i]) < 0 ? tmp : res[i];
} else if (res[i] == null || len < res[i].length()){
res[i] = tmp;
}
}
}
}
if (res[i] == null) {
res[i] = "";
}
}
return res;
}
private int[] buildFail(StringBuilder pattern) {
int m = pattern.length();
int[] fail = new int[m];
Arrays.fill(fail, m);
for (int i = m - 2; i >= 0; --i) {
int j = fail[i + 1];
while (j != m && pattern.charAt(j - 1) != pattern.charAt(i)) {
j = fail[j];
}
if (pattern.charAt(j - 1) == pattern.charAt(i)) {
fail[i] = j - 1;
}
}
return fail;
}
public int kmp(String query, int[] fail, StringBuilder pattern) {
int n = query.length();
int m = pattern.length();
int match = m, min = m;
for (int i = n - 1; i >= 0; --i) {
while (match != m && pattern.charAt(match - 1) != query.charAt(i)) {
match = fail[match];
}
if (pattern.charAt(match - 1) == query.charAt(i)) {
--match;
min = Math.min(match, min);
if (match == 0) {
break;
}
}
}
return min;
}
}
100216. Maximum Strength of K Disjoint Subarrays
给你一个长度为 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 个 不相交子数组 ，使得 能量值最大 。
请你返回可以得到的 最大能量值 。
注意，选出来的所有子数组 不 需要覆盖整个数组。
测试样例：
输入：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 。
解答：重点是一个排序，寻找当前位置出发最长子数组，配合上一个dp结果能够到达的最大值。排序思路可以反向，假设所有后面的数字都被计算了，然后加回去。
class Solution {
public long maximumStrength(int[] nums, int k) {
int len = nums.length;
long[] prefixSum = new long[nums.length + 1];
for (int i = 0; i < nums.length; ++i) {
prefixSum[i + 1] = nums[i] + prefixSum[i];
}
long[] dp = new long[len], sort = new long[len];
long mul = 1;
for (int i = k; i >= 1; --i) {
PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> Long.compare(sort[b], sort[a]));
long[] nextDp = new long[len];
for (int j = k - i; j < nums.length; ++j) {
sort[j] = (j == 0 ? 0 : dp[j - 1]) + mul * (prefixSum[len] - prefixSum[j]) * i;
queue.add(j);
int tmp = queue.peek();
nextDp[j] = Math.max(j == k - i ? Long.MIN_VALUE : nextDp[j - 1]
, (tmp == 0 ? 0 : dp[tmp - 1]) + mul * i * (prefixSum[j + 1] - prefixSum[tmp]));
}
dp = nextDp;
mul = -mul;
}
return dp[len - 1];
}
}