收集垃圾的最少总时间

标签: 数组 字符串 前缀和

难度: Medium

给你一个下标从 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 <= 105
  • garbage[i] 只包含字母 'M' ，'P' 和 'G' 。
  • 1 <= garbage[i].length <= 10
  • travel.length == garbage.length - 1
  • 1 <= travel[i] <= 100

Submission

运行时间: 60 ms

内存: 36.8 MB

class Solution:
    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:
        n = len(travel)
        # last_idx= {'M':0, 'P':0, 'G':0}
        # for g in ['M', 'P', 'G']:
        #     for i in range(n, 0, -1):
        #         if g in garbage[i]:
        #             last_idx[g] = i
        #             break
        ans = 0
        for gar in garbage:
            ans += len(gar)
        for g in ['M', 'P', 'G']:
            for i in range(n, 0, -1):
                if g in garbage[i]:
                    # print(i)
                    ans += sum(travel[:i])
                    break
        return ans

Explain

题解的思路是首先计算清理所有房屋中垃圾的总时间，即遍历每个房子的垃圾字符串，统计所有字符的数量。然后，对于每种垃圾类型（'M', 'P', 'G'），找出包含该类型垃圾的最远房子的索引，并计算从房子0到该房子的行驶时间之和。这种方法有效地将问题拆分为两个主要步骤：1）计算清理垃圾的时间，2）计算行驶到必要的最远房子的时间。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:
        n = len(travel)
        ans = 0
        # 计算清理所有房子中的垃圾所需的总时间
        for gar in garbage:
            ans += len(gar)  # 每个字符代表一单位垃圾，需要1分钟来清理
        # 对每种垃圾类型，找出需要收集的最远的房子
        for g in ['M', 'P', 'G']:
            for i in range(n, 0, -1):
                if g in garbage[i]:
                    # 从房子0到房子i的行驶时间累加
                    ans += sum(travel[:i])
                    break
        return ans

Explore

在这个算法中，只需要考虑每种垃圾类型需要到达的最远房子索引，是因为清洁车只需一次性地前往这个最远房子收集沿途所有对应类型的垃圾。由于清洁车在返回途中不需再次停留收集，所以不必单独计算每个包含该类型垃圾的房子的距离。这种方法减少了不必要的计算，优化了行驶路径和时间。

如果某种垃圾类型不存在于任何房子中，例如'G'类型垃圾，那么在代码中对应的循环将直接跳过，不会增加任何额外的行驶时间。这是因为循环中的条件`if g in garbage[i]`将始终为假，循环将在不执行任何操作的情况下结束。因此，算法仍然可以正确运行并得出正确的总时间。

是的，这段代码中的`for i in range(n, 0, -1):`确实会错过检查`garbage[0]`的情况。这是因为Python中`range`函数的结束索引是不包括的。如果`garbage[0]`包含了某种类型的垃圾，而这种垃圾又只在`garbage[0]`中出现，那么该类型的垃圾将不会被正确处理。这是代码的一个潜在错误，应该通过将范围更改为`range(n+1, 0, -1)`或类似的方式来修正。