前言
心中充满了痛苦与心酸，悲伤与寂寞。
但是，那样的感情，我现在也渴望毫无保留地去珍惜。
因为一旦这些感情都全部消失的时候，我想我就会彻底的不复存在了。
整体评价
VP下来，感觉挺难的，每一题都不容易，每一题都有很大收获。t2是个多重背包的题，t3思维题，t4单调栈，挺考验思维的.
这场周赛非常有质量，推荐大家VP.
1. 统计匹配检索规则的物品数量
感觉理解题意，比写代码 难点, T_T.
Java
Java
go
class Solution {
// stream流式解
public int countMatches(List<List<String>> items, String ruleKey, String ruleValue) {
List<String> arr = List.of("type", "color", "name");
int idx = arr.indexOf(ruleKey);
// 或者用map
// Map<String, Integer> hash = Map.of("type", 0, "color", 1, "name", 2);
// int idx = hash.get(ruleKey);
return (int)items.stream().filter(x -> x.get(idx).equals(ruleValue)).count();
}
}2. 最接近目标价格的甜点成本
求一个目标函数最优解，如果涉及多因子，只能固定一个变量（枚举过程），然后再求另一个变量的最优解。
当然这边思路很简单，枚举的是基料，求配料的最优组合解。
这题数据范围小,基料(), 配料(), 目标值()
而且次数限制次数()
感觉leetcode中，多重背包的题有些少见，所以这边写一下。
基本上是0-1背包扩展版，可以简单理解为0-1背包的基础上，把k个同物品，逻辑上视为为k个不同的物品，就这样简单。
Java
Java
class Solution {
// 多重背包
TreeSet<Integer> solve(int[] costs, int k, int target) {
TreeSet<Integer> sets = new TreeSet<>();
boolean[] used = new boolean[2 * target + 1];
used[0] = true;
int n = costs.length;
int m = target * 2;
// 外层 是 weight
for (int i = 0; i < n; i++) {
// 内层 是 volume，逆序
for (int j = m; j >= 0; j--) {
if (!used[j]) continue;
// 这边是 次数
for (int t = 1; t <= k; t++) {
if (j + costs[i] * t <= m) {
used[j + costs[i] * t] = true;
}
}
}
}
for (int i = 0; i < used.length; i++) {
if (used[i]) {
sets.add(i);
}
}
return sets;
}
// *) 多重背包
public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
// 背包的计算
TreeSet<Integer> sets = solve(toppingCosts, 2, target);
int ans = baseCosts[0];
for (int i = 0; i < baseCosts.length; i++) {
if (baseCosts[i] >= target) {
int t = baseCosts[i];
if (Math.abs(t - target) < Math.abs(ans - target)) {
ans = t;
} else if (Math.abs(t - target) == Math.abs(ans - target) && t < ans) {
ans = t;
}
} else {
// 从左右两个最近点，寻求最优解
Integer k1 = sets.floor(target - baseCosts[i]);
Integer k2 = sets.ceiling(target - baseCosts[i]);
int t = 0;
if (k1 != null && k2 != null) {
if (Math.abs(k1 + baseCosts[i] - target) <= Math.abs(k2 + baseCosts[i] - target)) {
t = k1;
} else {
t = k2;
}
} else if (k1 != null) {
t = k1;
} else if (k2 != null) {
t = k2;
}
t += baseCosts[i];
if (Math.abs(t - target) < Math.abs(ans - target)) {
ans = t;
} else if (Math.abs(t - target) == Math.abs(ans - target) && t < ans) {
ans = t;
}
}
}
return ans;
}
}多重背包比DFS全枚举要快很多。
3. 通过最少操作次数使数组的和相等
一道思维题吧，感觉思维题总是和贪心一块出现.
感觉这代码，写的有点丑，其实可以把和的情况，归一化处理就会简洁很多。
Java
class Solution {
public int minOperations(int[] nums1, int[] nums2) {
int s1 = 0, s2 = 0;
int[] tab1 = new int[7];
for (int v: nums1) {
tab1[v]++;
s1 += v;
}
int[] tab2 = new int[7];
for (int v: nums2) {
tab2[v]++;
s2 += v;
}
int ans = 0;
while (s1 != s2) {
if (s1 > s2) {
boolean f = false;
for (int i = 6; !f && i >= 2; i--) {
if (tab1[i] > 0) {
tab1[i]--;
tab1[1]++;
s1 = s1 - i + 1;
f = true;
} else if (tab2[6 - i + 1] > 0) {
tab2[6 - i + 1]--;
tab2[6]++;
s2 = s2 + i - 1;
f = true;
}
}
if (f) {
ans++;
if (s2 >= s1) return ans;
} else {
return -1;
}
} else {
boolean f = false;
for (int i = 6; !f && i >= 2; i--) {
if (tab2[i] > 0) {
tab2[i]--;
tab2[1]++;
s2 = s2 - i + 1;
f = true;
} else if (tab1[6 - i + 1] > 0) {
tab1[6 - i + 1]--;
tab1[6]++;
s1 = s1 + i - 1;
f = true;
}
}
if (f) {
ans++;
if (s2 <= s1) return ans;
} else {
return -1;
}
}
}
return ans;
}
}4. 车队 II
注重思维的单调栈题，真心不容易写.
首先这题得逆序，要理解为啥可以引入单调栈。
Java
class Solution {
// 后面的会遭遇前面的
public double[] getCollisionTimes(int[][] cars) {
// 逆序 + 单调栈？
int n = cars.length;
double[] res = new double[n];
int[] stacks = new int[n];
int ptr = -1;
for (int i = n - 1; i >= 0; i--) {
int v = cars[i][1];
while (ptr >= 0 && v <= cars[stacks[ptr]][1]) {
ptr--;
}
while (ptr >= 0) {
int p = stacks[ptr];
double dtime = (cars[p][0] - cars[i][0]) * 1.0 / (v - cars[p][1]);
if (res[p] != -1 && dtime > res[p]) {
ptr--;
} else {
break;
}
}
if (ptr == -1) {
res[i] = -1;
} else {
int p = stacks[ptr];
res[i] = (cars[p][0] - cars[i][0]) * 1.0 / (v - cars[p][1]);
}
stacks[++ptr] = i;
}
return res;
}
}评论 (0)
