欢迎大家加QQ群：623375442，可以方便群里面交流。这周题目还是有点难度，但是比昨天双周赛那一堆数学操作好。
100548. Sum of Variable Length Subarrays
给你一个长度为 n 的整数数组 nums 。对于 每个 下标 i（0 <= i < n），定义对应的子数组 nums[start ... i]（start = max(0, i - nums[i])）。
返回为数组中每个下标定义的子数组中所有元素的总和。
子数组 是数组中的一个连续、非空 的元素序列。
测试样例：
输入：nums = [2,3,1]
输出：11
解释：总和为 11 。因此，输出 11 。
解答：按照题意，暴力计算。
class Solution {
public int subarraySum(int[] nums) {
int res = 0;
for (int i = 0; i < nums.length; ++i) {
int st = Math.max(0, i - nums[i]);
for (int j = st; j <= i; ++j) {
res += nums[j];
}
}
return res;
}
}100534. Maximum and Minimum Sums of at Most Size K Subsequences
给你一个整数数组 nums 和一个正整数 k，返回所有长度最多为 k 的 子序列 中 最大值 与 最小值 之和的总和。
非空子序列 是指从另一个数组中删除一些或不删除任何元素（且不改变剩余元素的顺序）得到的数组。
由于答案可能非常大，请返回对 10^9 + 7 取余数的结果。
测试样例：
输入：nums = [1,2,3], k = 2
输出：2
解释：数组 nums 中所有长度最多为 2 的子序列。因此，输出为 24。
解答：没想到啥好办法，利用组合的特性。
class Solution {
private static final int mod = 1_000_000_007;
public int minMaxSums(int[] nums, int k) {
Arrays.sort(nums);
long res = 0;
long[] dp = new long[k];
dp[0] = 1;
for (int i = 0; i < nums.length; ++i) {
long sum = 1;
// 前i - 1个数中挑选0 到 k - 1个数字
for (int j = Math.min(i, k - 1); j >= 1; --j) {
dp[j] = (dp[j] + dp[j - 1]) % mod;
sum += dp[j];
sum %= mod;
}
res += sum * nums[i] % mod;
res %= mod;
}
dp = new long[k + 1];
dp[0] = 1;
for (int i = nums.length - 1; i >= 0; --i) {
long sum = 1;
for (int j = Math.min(nums.length - i - 1, k - 1); j >= 1; --j) {
dp[j] = (dp[j] + dp[j - 1]) % mod;
sum += dp[j];
sum %= mod;
}
res += sum * nums[i] % mod;
res %= mod;
}
return (int) res;
}
}100553. Paint House IV
给你一个 偶数 整数 n，表示沿直线排列的房屋数量，以及一个大小为 n x 3 的二维数组 cost，其中 cost[i][j] 表示将第 i 个房屋涂成颜色 j + 1 的成本。
如果房屋满足以下条件，则认为它们看起来 漂亮：
- 不存在 两个 涂成相同颜色的相邻房屋。
- 距离行两端 等距 的房屋不能涂成相同的颜色。例如，如果 n = 6，则位置 (0, 5)、(1, 4) 和 (2, 3) 的房屋被认为是等距的。
返回使房屋看起来 漂亮 的 最低 涂色成本。
测试样例：
输入：n = 4, cost = [[3,5,7],[6,2,9],[4,8,1],[7,3,5]]
输出：9
解释：最佳涂色顺序为 [1, 2, 3, 2]，对应的成本为 [3, 2, 1, 3]。满足以下条件：
- 不存在涂成相同颜色的相邻房屋。
- 位置 0 和 3 的房屋（等距于两端）涂成不同的颜色 (1 != 2)。
- 位置 1 和 2 的房屋（等距于两端）涂成不同的颜色 (2 != 3)。
使房屋看起来漂亮的最低涂色成本为 3 + 2 + 1 + 3 = 9。
解答：动态规划题。感谢都是偶数。我们把距离两端等距的房屋看成一堆。一共3种颜色，那么2件房间的组合一共是9种（有几种不可行，等距房间不能同色）。同时要注意相邻房间不能同色。
class Solution {
private static final int[][] map = {{0,0},{0,1},{0,2},{1,0},{1,1},{1,2},{2,0},{2,1},{2,2}};
public long minCost(int n, int[][] cost) {
int st = 0, ed = n - 1;
long[] dp = new long[9];
while (st < ed) {
long[] nextDp = new long[9];
Arrays.fill(nextDp, Long.MAX_VALUE / 2);
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
// 动态规划
if (isValid(map[i], map[j])) {
nextDp[i] = Math.min(nextDp[i], dp[j] + cost[st][map[i][0]] + cost[ed][map[i][1]]);
}
}
}
dp = nextDp;
++st;
--ed;
}
long res = Long.MAX_VALUE;
for (long t : dp) {
res = Math.min(res, t);
}
return res;
}
private boolean isValid(int[] n1, int[] n2) {
// 两端房间不能同色 + 相邻不能同色
return n1[0] != n1[1] && n2[0] != n2[1] && n1[0] != n2[0] && n1[1] != n2[1];
}
}100543. Maximum and Minimum Sums of at Most Size K Subarrays
给你一个整数数组 nums 和一个 正 整数 k 。 返回 最多 有 k 个元素的所有子数组的 最大 和 最小 元素之和。
子数组 是数组中的一个连续、非空 的元素序列。
测试样例：
输入：nums = [1,2,3], k = 2
输出：20
解释：最多 2 个元素的 nums 的子数组, 输出为 20 。
解答：利用队列来模拟，查看每个数字影响范围。然后类和。
class Solution {
public long minMaxSubarraySum(int[] nums, int k) {
Deque<long[]> min = new LinkedList<>(), max = new LinkedList<>();
long minSum = 0, maxSum = 0;
long res = 0;
for (int i = 0; i < nums.length; ++i) {
// min的范围
while (!min.isEmpty() && nums[(int) min.peekLast()[0]] >= nums[i]) {
minSum -= min.removeLast()[1];
}
long[] minAdd = {i, (min.isEmpty() ? ((long) Math.min(i + 1, k)) : (i - min.peekLast()[0])) * nums[i]};
minSum += minAdd[1];
min.addLast(minAdd);
res += minSum;
// max的范围
while (!max.isEmpty() && nums[(int) max.peekLast()[0]] <= nums[i]) {
maxSum -= max.removeLast()[1];
}
long[] maxAdd = {i, (max.isEmpty() ? ((long) Math.min(i + 1, k)) : (i - max.peekLast()[0])) * nums[i]};
maxSum += maxAdd[1];
max.addLast(maxAdd);
res += maxSum;
// 当超过k个元素之后，需要考虑到出栈
if (i >= k - 1) {
long[] firstMin = min.getFirst();
minSum -= nums[(int) firstMin[0]];
if (firstMin[0] == i - k + 1) {
min.removeFirst();
} else {
firstMin[1] -= nums[(int) firstMin[0]];
}
long[] firstMax = max.getFirst();
maxSum -= nums[(int) firstMax[0]];
if (firstMax[0] == i - k + 1) {
max.removeFirst();
} else {
firstMax[1] -= nums[(int) firstMax[0]];
}
}
}
return res;
}
}