leetcode
leetcode 2051 ~ 2100
收集垃圾的最少总时间

收集垃圾的最少总时间

难度:

标签:

题目描述

代码结果

运行时间: 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'类型的垃圾,算法是否仍然正确运行?
如果某种垃圾类型不存在于任何房子中,例如'G'类型垃圾,那么在代码中对应的循环将直接跳过,不会增加任何额外的行驶时间。这是因为循环中的条件`if g in garbage[i]`将始终为假,循环将在不执行任何操作的情况下结束。因此,算法仍然可以正确运行并得出正确的总时间。
🦆
代码中的`for i in range(n, 0, -1):`循环是否会错过检查`garbage[0]`的情况,因为range的结束参数是不包括的?
是的,这段代码中的`for i in range(n, 0, -1):`确实会错过检查`garbage[0]`的情况。这是因为Python中`range`函数的结束索引是不包括的。如果`garbage[0]`包含了某种类型的垃圾,而这种垃圾又只在`garbage[0]`中出现,那么该类型的垃圾将不会被正确处理。这是代码的一个潜在错误,应该通过将范围更改为`range(n+1, 0, -1)`或类似的方式来修正。

相关问题