6901. Total Distance Traveled
卡车有两个油箱。给你两个整数，mainTank 表示主油箱中的燃料（以升为单位），additionalTank 表示副油箱中的燃料（以升为单位）。
该卡车每耗费 1 升燃料都可以行驶 10 km。每当主油箱使用了 5 升燃料时，如果副油箱至少有 1 升燃料，则会将 1 升燃料从副油箱转移到主油箱。
返回卡车可以行驶的最大距离。
注意：从副油箱向主油箱注入燃料不是连续行为。这一事件会在每消耗 5 升燃料时突然且立即发生。
测试样例：
输入：mainTank = 5, additionalTank = 10
输出：60
解释：
在用掉 5 升燃料后，主油箱中燃料还剩下 (5 - 5 + 1) = 1 升，行驶距离为 50km 。在用掉剩下的 1 升燃料后，没有新的燃料注入到主油箱中，主油箱变为空。总行驶距离为 60km 。
解答：暴力模拟
class Solution {
public int distanceTraveled(int mainTank, int additionalTank) {
int res = 0, tmp = 0;
while (mainTank > 0) {
res += 10;
--mainTank;
++tmp;
if (tmp == 5 && additionalTank > 0) {
--additionalTank;
tmp = 0;
++mainTank;
}
}
return res;
}
}6890. Find the Value of the Partition
给你一个 正 整数数组 nums 。
将 nums 分成两个数组：nums1 和 nums2 ，并满足下述条件：
- 数组 nums 中的每个元素都属于数组 nums1 或数组 nums2 。
- 两个数组都非空。
- 分区值最小 。
分区值的计算方法是 |max(nums1) - min(nums2)| 。
其中，max(nums1) 表示数组 nums1 中的最大元素，min(nums2) 表示数组 nums2 中的最小元素。
返回表示分区值的整数。
测试样例：
输入：nums = [1,3,2,4]
输出：1
解释：
可以将数组 nums 分成 nums1 = [1,2] 和 nums2 = [3,4] 。
- 数组 nums1 的最大值等于 2 。
- 数组 nums2 的最小值等于 3 。
分区值等于 |2 - 3| = 1 。可以证明 1 是所有分区方案的最小值。
解答：这道题目其实只考了排序。将数组排序之后，寻找最小的递增值，左边放在arr1，右边放在arr2.
class Solution {
public int findValueOfPartition(int[] nums) {
Arrays.sort(nums);
int res = Integer.MAX_VALUE;
for (int i = 1; i < nums.length; ++i) {
res = Math.min(res, nums[i] - nums[i - 1]);
}
return res;
}
}6893. Special Permutations
给你一个下标从 0 开始的整数数组 nums ，它包含 n 个 互不相同 的正整数。如果 nums 的一个排列满足以下条件，我们称它是一个特别的排列：
- 对于 0 <= i < n - 1 的下标 i ，要么 nums[i] % nums[i+1] == 0 ，要么 nums[i+1] % nums[i] == 0 。
请你返回特别排列的总数目，由于答案可能很大，请将它对 109 + 7 取余 后返回。
测试样例
输入：nums = [2,3,6]
输出：2
解释：
[3,6,2] 和 [2,6,3] 是 nums 两个特别的排列。
解答：这道题目有点难度。我能想到的是利用状态压缩配合动态规划计算所有可能。状态压缩已经使用的数字，并且记录最后一个数字。然后动态规划，计算下一个可能转移的位置。
class Solution {
private static final int mod = 1_000_000_007;
public int specialPerm(int[] nums) {
int len = nums.length;
int max = (1 << len) * (len + 1);
Long[] mem = new Long[max];
return (int) (helper(0, -1, mem, nums) % mod);
}
private long helper(int key, int last, Long[] mem, int[] nums) {
if (key == (1 << nums.length) - 1) {
return 1;
}
int tmp = (key * (nums.length + 1)) + (last + 1);
if (mem[tmp] != null) {
return mem[tmp];
}
mem[tmp] = 0L;
for (int i = 0; i < nums.length; ++i) {
if (!isUsed(key, i) && (last == -1 || nums[i] % nums[last] == 0 || nums[last] % nums[i] == 0)) {
mem[tmp] += helper(key + (1 << i), i, mem, nums);
}
}
return mem[tmp];
}
private boolean isUsed(int key, int o) {
int m = (key >> o) & 1;
return m == 1;
}
}6447. Painting the Walls
给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time ，分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠：
- 一位需要 付费 的油漆匠，刷第 i 堵墙需要花费 time[i] 单位的时间，开销为 cost[i] 单位的钱。
- 一位 免费 的油漆匠，刷 任意 一堵墙的时间为 1 单位，开销为 0 。但是必须在付费油漆匠 工作 时，免费油漆匠才会工作。
请你返回刷完 n 堵墙最少开销为多少。
测试样例
输入：cost = [1,2,3,2], time = [1,2,3,2]
输出：3
解释：下标为 0 和 1 的墙由付费油漆匠来刷，需要 3 单位时间。同时，免费油漆匠刷下标为 2 和 3 的墙，需要 2 单位时间，开销为 0 。总开销为 1 + 2 = 3 。
解答：这真的是什么奇怪的免费油漆匠。这道题目稍微需要一点脑经急转弯，因为免费的油漆匠刷墙永远是1单位，所以动态规划的范围可以确定上线是cost.length(cost.length的时候，免费油漆匠可以完成所以砌墙)。我没想到更好的优化方案，所以代码就比较暴力。动态规划用了当前付费油漆匠已经使用的时间和付费油漆匠已经完成墙面数。
如果付费油漆匠已经使用的时间+已经完成的前面数>=剩余墙面数，这个时候程序可以记录最小值（剩下的墙面都是免费油漆匠完成）。
class Solution {
public int paintWalls(int[] cost, int[] time) {
int len = cost.length;
int[][] dp = new int[len + 1][len + 1];
dp[0][0] = 0;
int res = Integer.MAX_VALUE;
for (int i = 0; i < cost.length; ++i) {
int c = cost[i], t = time[i];
int[][] nextDp = new int[len + 1][len + 1];
nextDp[0][0] = 0;
for (int j = 0; j <= len; ++j) {
for (int k = 0; k + j < len; ++k) {
if ((j == 0 && k == 0) || dp[j][k] != 0) {
if (nextDp[j][k] == 0 || nextDp[j][k] > dp[j][k]) {
nextDp[j][k] = dp[j][k];
}
int nt = Math.min(t + j, len - k - 1);
if (nextDp[nt][k + 1] == 0 || nextDp[nt][k + 1] > dp[j][k] + c) {
nextDp[nt][k + 1] = dp[j][k] + c;
if (nt + k + 1 >= len) {
res = Math.min(res, nextDp[nt][k + 1]);
}
}
}
}
}
dp = nextDp;
}
return res;
}
}这周题目，还是挺有难度的。。。接下来两周会停更，终于可以休假了。等我休假回来之后，会把缺少的题解补上。