2391.收集垃圾的最少总时间
给你一个下标从 0 开始的字符串数组 garbage ，其中 garbage[i] 表示第 i 个房子的垃圾集合。garbage[i] 只包含字符 'M' ，'P' 和 'G' ，但可能包含多个相同字符，每个字符分别表示一单位的金属、纸和玻璃。垃圾车收拾 一 单位的任何一种垃圾都需要花费 1 分钟。
同时给你一个下标从 0 开始的整数数组 travel ，其中 travel[i] 是垃圾车从房子 i 行驶到房子 i + 1 需要的分钟数。
城市里总共有三辆垃圾车，分别收拾三种垃圾。每辆垃圾车都从房子 0 出发，按顺序 到达每一栋房子。但它们 不是必须 到达所有的房子。
任何时刻只有 一辆 垃圾车处在使用状态。当一辆垃圾车在行驶或者收拾垃圾的时候，另外两辆车 不能 做任何事情。
请你返回收拾完所有垃圾需要花费的 最少 总分钟数。
示例 1：
输入：garbage = ["G","P","GP","GG"], travel = [2,4,3]
输出：21
解释：
收拾纸的垃圾车：
1. 从房子 0 行驶到房子 1
2. 收拾房子 1 的纸垃圾
3. 从房子 1 行驶到房子 2
4. 收拾房子 2 的纸垃圾
收拾纸的垃圾车总共花费 8 分钟收拾完所有的纸垃圾。
收拾玻璃的垃圾车：
1. 收拾房子 0 的玻璃垃圾
2. 从房子 0 行驶到房子 1
3. 从房子 1 行驶到房子 2
4. 收拾房子 2 的玻璃垃圾
5. 从房子 2 行驶到房子 3
6. 收拾房子 3 的玻璃垃圾
收拾玻璃的垃圾车总共花费 13 分钟收拾完所有的玻璃垃圾。
由于没有金属垃圾，收拾金属的垃圾车不需要花费任何时间。
所以总共花费 8 + 13 = 21 分钟收拾完所有垃圾。
示例 2：
输入：garbage = ["MMM","PGM","GP"], travel = [3,10]
输出：37
解释：
收拾金属的垃圾车花费 7 分钟收拾完所有的金属垃圾。
收拾纸的垃圾车花费 15 分钟收拾完所有的纸垃圾。
收拾玻璃的垃圾车花费 15 分钟收拾完所有的玻璃垃圾。
总共花费 7 + 15 + 15 = 37 分钟收拾完所有的垃圾。
提示：
2 <= garbage.length <= 105garbage[i]只包含字母'M'，'P'和'G'。1 <= garbage[i].length <= 10travel.length == garbage.length - 11 <= travel[i] <= 100
题解一
/**
* 思路一：按照业务逻辑，首先派出一辆车从0位置到n依次清理指定垃圾
* 题目中要求，如果有对应的垃圾则清理，无则不计入时间，直观来说就是，如果到达指定位置发现没有想清理的垃圾，则寻找下一个
* 位置，如果后面都没有清理的垃圾，则路上的时间也不计入总时间。
* 主要思路：1.计算每个位置清理垃圾需要的时间，如果有垃圾清理，则将路程时间+清理时间计入总和
*
* 时间复杂度: O(MN) M为garbage长度 N为travel长度
* 空间复杂度: O(1)
*/
public int garbageCollection(String[] garbage, int[] travel) {
final int m = garbageTarget(garbage, travel, 'M');
final int p = garbageTarget(garbage, travel, 'P');
final int g = garbageTarget(garbage, travel, 'G');
return m + p + g;
}
public int garbageTarget(String[] garbage, int[] travel, Character target) {
int accumulate = 0;
int sum = 0;
for (int i = 0; i < garbage.length; i++) {
// 清理垃圾需要的时间
int count = count(garbage[i], target);
// 如果大于0则表示有垃圾需要清理，并且需要将为了清理该垃圾花费在路上的时间计入总时间
if (count > 0) {
sum+=count;
sum+=accumulate;
accumulate = 0;
}
// 继续往下一步
if (i < travel.length) {
accumulate += travel[i];
}
}
return sum;
}
public int count(String str, Character target) {
final char[] chars = str.toCharArray();
int num = 0;
for (char c : chars) {
if (c == target) {
num++;
}
}
return num;
}
题解二
/**
* 思路二：花费时间=清理垃圾时间+路上花费的时间
* 清理垃圾时间=garbage中每个位置字符串长度的总和
* 路上花费的时间=最后一次出现垃圾的索引位置index距离
* 其中清理垃圾时间比较好计算，怎么计算最后一次出现垃圾的索引位置index距离呢？
* 可以在遍历garbage的时候一直累计计算当前距离值，发现垃圾则更新该垃圾的距离值
*
*/
public int garbageCollection2(String[] garbage, int[] travel) {
Map<Character, Integer> distance = new HashMap<>();
int res = 0, curDis = 0;
for (int i = 0; i < garbage.length; i++) {
// 清理垃圾时间
res += garbage[i].length();
// 累计距离值
if (i > 0) {
curDis += travel[i - 1];
}
// 更新距离值
for (char c : garbage[i].toCharArray()) {
distance.put(c, curDis);
}
}
// 清理垃圾时间+每个垃圾车距离时间
return res + distance.values().stream().reduce(0, Integer::sum);
}
题解三
/**
* 思路3：倒序遍历
* 根据题目特点，我们从garbage的最后一个位置开始遍历，
* 获取字符串garbage[i]时，可以根据长度计算清理垃圾消耗的时间，距离时间怎么计算呢
* 我们通过travel可以知道从上个垃圾站到当前垃圾站的距离时间为travel[i-1]
*
* 问题1：{"G", "P", "P", "PG"}, index=2,"P"中没有包含G，但是index=3中只计算了 2->3的距离值
* 怎么计算这种间断了的距离值？
* 我们可以使用set,来添加垃圾，每一次计算的是 travel[i-1] * seen.size()，当遍历到index2,"P"
* 时，seen(P,G)*travel[1],也会计算到G来到2到位置的距离
*/
public int garbageCollection3(String[] garbage, int[] travel) {
int ans = garbage[0].length();
HashSet<Character> seen = new HashSet<>();
for (int i = garbage.length - 1; i > 0; i--) {
char[] g = garbage[i].toCharArray();
for (char c : g) {
seen.add(c);
}
ans += g.length + travel[i - 1] * seen.size();
}
return ans;
}
