收集垃圾的最少总时间
难度:
标签:
题目描述
代码结果
运行时间: 60 ms, 内存: 36.8 MB
/*
* 思路:
* 1. 使用流遍历每个房子的垃圾,计算收拾每种垃圾所需要的时间。
* 2. 使用流计算每种垃圾车到达的最后一个房子位置,计算行驶时间。
*/
import java.util.stream.IntStream;
public class Solution {
public int minTotalTime(String[] garbage, int[] travel) {
int[] lastHouse = new int[3];
int[] collectTime = new int[3];
IntStream.range(0, garbage.length).forEach(i -> {
garbage[i].chars().forEach(c -> {
if (c == 'M') {
collectTime[0]++;
lastHouse[0] = i;
} else if (c == 'P') {
collectTime[1]++;
lastHouse[1] = i;
} else if (c == 'G') {
collectTime[2]++;
lastHouse[2] = i;
}
});
});
IntStream.range(1, garbage.length).forEach(i -> {
if (i <= lastHouse[0]) {
collectTime[0] += travel[i - 1];
}
if (i <= lastHouse[1]) {
collectTime[1] += travel[i - 1];
}
if (i <= lastHouse[2]) {
collectTime[2] += travel[i - 1];
}
});
return IntStream.of(collectTime).sum();
}
}
解释
方法:
题解的思路是首先计算清理所有房屋中垃圾的总时间,即遍历每个房子的垃圾字符串,统计所有字符的数量。然后,对于每种垃圾类型('M', 'P', 'G'),找出包含该类型垃圾的最远房子的索引,并计算从房子0到该房子的行驶时间之和。这种方法有效地将问题拆分为两个主要步骤:1)计算清理垃圾的时间,2)计算行驶到必要的最远房子的时间。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在算法中,为什么只需要考虑每种垃圾类型需要到达的最远房子索引,而不是所有包含该类型垃圾的房子?
▷🦆
算法如何处理如果某种垃圾类型不存在于任何房子中的情况?例如,如果没有任何房子包含'G'类型的垃圾,算法是否仍然正确运行?
▷🦆
代码中的`for i in range(n, 0, -1):`循环是否会错过检查`garbage[0]`的情况,因为range的结束参数是不包括的?
▷