欢迎大家加QQ群：623375442，可以方便群里面交流。
100484. Minimum Positive Sum Subarray
给你一个整数数组 nums 和 两个 整数 l 和 r。你的任务是找到一个长度在 l 和 r 之间（包含）且和大于 0 的 子数组 的 最小 和。
返回满足条件的子数组的 最小 和。如果不存在这样的子数组，则返回 -1。
子数组 是数组中的一个连续 非空 元素序列。
测试样例：
输入：nums = [3, -2, 1, 4], l = 2, r = 3
输出：1
解释：长度在 l = 2 和 r = 3 之间且和大于 0 的子数组有：
- [3, -2] 和为 1
- [1, 4] 和为 5
- [3, -2, 1] 和为 2
- [-2, 1, 4] 和为 3
其中，子数组 [3, -2] 的和为 1，是所有正和中最小的。因此，答案为 1。
解答：范围不大，直接暴力枚举。
class Solution {
public int minimumSumSubarray(List<Integer> _nums, int l, int r) {
int[] nums = new int[_nums.size()];
int o = 0;
for (int n : _nums) {
nums[o++] = n;
}
int res = Integer.MAX_VALUE;
for (int st = 0; st < nums.length; ++st) {
int ed = st, d = 0, sum = 0;
while (ed < nums.length && d < r) {
++d;
sum += nums[ed++];
if (d >= l && d <= r && sum > 0) {
res = Math.min(res, sum);
}
}
}
return res == Integer.MAX_VALUE ? -1 : res;
}
}100445. Rearrange K Substrings to Form Target String
给你两个字符串 s 和 t（它们互为字母异位词），以及一个整数 k。
你的任务是判断是否可以将字符串 s 分割成 k 个等长的子字符串，然后重新排列这些子字符串，并以任意顺序连接它们，使得最终得到的新字符串与给定的字符串 t 相匹配。
如果可以做到，返回 true；否则，返回 false。
字母异位词 是指由另一个单词或短语的所有字母重新排列形成的单词或短语，使用所有原始字母恰好一次。
子字符串 是字符串中的一个连续 非空 字符序列。
测试样例：
输入：s = "abcd", t = "cdab", k = 2
输出：true
解释：
- 将 s 分割成 2 个长度为 2 的子字符串：["ab", "cd"]。
- 重新排列这些子字符串为 ["cd", "ab"]，然后连接它们得到 "cdab"，与 t 相匹配。
解答：利用哈希表储存一下s拆分后的字符串，然后相同逻辑拆分一下t，看看能不能组装上。
class Solution {
public boolean isPossibleToRearrange(String s, String t, int k) {
HashMap<String, Integer> map = new HashMap<>();
int j = s.length() / k;
for (int i = 0; i < s.length(); i = i + j) {
String sub = s.substring(i, i + j);
map.put(sub, map.getOrDefault(sub, 0) + 1);
}
for (int i = 0; i < t.length(); i = i + j) {
String sub = t.substring(i, i + j);
int c = map.getOrDefault(sub, 0);
if (c == 0) {
return false;
}
map.put(sub, c - 1);
}
return true;
}
}100493. Minimum Array Sum
给你一个整数数组 nums 和三个整数 k、op1 和 op2。
你可以对 nums 执行以下操作：
- 操作 1：选择一个下标 i，将 nums[i] 除以 2，并 向上取整 到最接近的整数。你最多可以执行此操作 op1 次，并且每个下标最多只能执行一次。
- 操作 2：选择一个下标 i，仅当 nums[i] 大于或等于 k 时，从 nums[i] 中减去 k。你最多可以执行此操作 op2 次，并且每个下标最多只能执行一次。
注意： 两种操作可以应用于同一下标，但每种操作最多只能应用一次。
返回在执行任意次数的操作后，nums 中所有元素的 最小 可能 和 。
测试样例：
输入：nums = [2,8,3,19,3], k = 3, op1 = 1, op2 = 1
输出：23
解释：
- 对 nums[1] = 8 应用操作 2，使 nums[1] = 5。
- 对 nums[3] = 19 应用操作 1，使 nums[3] = 10。
- 结果数组变为 [2, 5, 3, 10, 3]，在应用操作后具有最小可能和 23。
解答：这题范围太小了。nums.length <= 100。每一种操作对于每一个下标也只能执行一次。利用一下动态规划的思维，快速计算。
class Solution {
public int minArraySum(int[] nums, int k, int op1, int op2) {
Integer[][] dp = new Integer[op1 + 1][op2 + 1];
dp[op1][op2] = 0;
for (int n : nums) {
Integer[][] nextDp = new Integer[op1 + 1][op2 + 1];
for (int i = 0; i <= op1; ++i) {
for (int j = 0; j <= op2; ++j) {
if (dp[i][j] == null) continue;
// 枚举一下可能
// 1. 不执行
// 2. 执行操作1
// 3. 执行操作2
// 4. 执行操作1和操作2
nextDp[i][j] = min(nextDp[i][j], dp[i][j] + n);
if (i >= 1) {
nextDp[i - 1][j] = min(nextDp[i - 1][j], dp[i][j] + round(n));
}
if (j >= 1) {
nextDp[i][j - 1] = min(nextDp[i][j - 1], dp[i][j] + remove(n, k));
}
if (i >= 1 && j >= 1) {
nextDp[i - 1][j - 1] = min(nextDp[i - 1][j - 1],
dp[i][j] + Math.min(remove(round(n), k), round(remove(n, k))));
}
}
}
dp = nextDp;
}
int res = Integer.MAX_VALUE;
for (Integer[] r : dp) {
for (Integer n : r) {
res = min(n, res);
}
}
return res;
}
private Integer min(Integer cur, int next) {
if (cur == null) {
return next;
} else if (cur <= next) {
return cur;
} else {
return next;
}
}
private int round(int n) {
return n / 2 + n % 2;
}
private int remove(int n, int k) {
if (n >= k) {
return n - k;
} else {
return n;
}
}
}100500. Maximize Sum of Weights after Edge Removals
存在一棵具有 n 个节点的无向树，节点编号为 0 到 n - 1。给你一个长度为 n - 1 的二维整数数组 edges，其中 edges[i] = [ui, vi, wi] 表示在树中节点 ui 和 vi 之间有一条权重为 wi 的边。
你的任务是移除零条或多条边，使得：
- 每个节点与至多 k 个其他节点有边直接相连，其中 k 是给定的输入。
- 剩余边的权重之和 最大化 。
返回在进行必要的移除后，剩余边的权重的 最大 可能和。
测试样例：
输入：edges = [[0,1,4],[0,2,2],[2,3,12],[2,4,6]], k = 2
输出：22
解释：
- 节点 2 与其他 3 个节点相连。我们移除边 [0, 2, 2]，确保没有节点与超过 k = 2 个节点相连。
- 权重之和为 22，无法获得更大的和。因此，答案是 22。
解答：也有一点动态规划的逻辑在。我们假设0是根结点。每个节点分成2种可能：一种是与父节点断开（这个时候最多k个子节点），另一种是与父节点连着（这个时候最多k-1个子节点）。那遍历的逻辑就比较简单的了。对于每个节点，类和一下子节点全部断开的场景。然后选择(k - 1) or (k) 个最优节点连接上。
class Solution {
private class Data {
List<int[]>[] edges;
int k;
public Data(int[][] _edges, int k) {
this.k = k;
int n = _edges.length + 1;
edges = new List[n];
for (int i = 0; i < edges.length; ++i) {
edges[i] = new ArrayList<>();
}
for (int[] e : _edges) {
edges[e[0]].add(new int[]{e[1], e[2]});
edges[e[1]].add(new int[]{e[0], e[2]});
}
}
}
private static final long[] empty = new long[2];
public long maximizeSumOfWeights(int[][] edges, int k) {
Data data = new Data(edges, k);
return helper(0, -1, data)[0];
}
private long[] helper(int node, int pre, Data data) {
PriorityQueue<Long> topDiff = new PriorityQueue<>();
long disconnectSum = 0;
for (int[] next : data.edges[node]) {
if (next[0] != pre) {
long[] tmp = helper(next[0], node, data);
// 假设与所有子节点全部断开
disconnectSum += tmp[0];
// 寻找到最大的k个链接奖励
long connectBenefit = next[1] + tmp[1] - tmp[0];
topDiff.add(connectBenefit);
if (topDiff.size() > data.k) {
topDiff.poll();
}
}
}
long[] res = {disconnectSum, disconnectSum};
if (!topDiff.isEmpty()) {
if (topDiff.size() == data.k) {
// 如果链接带来的收益小于0，那就不链接
res[0] += Math.max(topDiff.poll(), 0);
}
for (long n : topDiff) {
res[0] += Math.max(n, 0);
res[1] += Math.max(n, 0);
}
}
return res;
}
}