LeetCode-2391. 收集垃圾的最少总时间【数组 字符串 前缀和】
LeetCode-2391. 收集垃圾的最少总时间【数组 字符串 前缀和】
- 题目描述：
- 解题思路一：处理垃圾和路程单独计算。
- 解题思路二：逆向思维，计算多走的路
- 解题思路三：只记录，当前t需要计算几次
题目描述：
给你一个下标从 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
解释：
收拾纸的垃圾车：
- 从房子 0 行驶到房子 1
- 收拾房子 1 的纸垃圾
- 从房子 1 行驶到房子 2
- 收拾房子 2 的纸垃圾
收拾纸的垃圾车总共花费 8 分钟收拾完所有的纸垃圾。
收拾玻璃的垃圾车： - 收拾房子 0 的玻璃垃圾
- 从房子 0 行驶到房子 1
- 从房子 1 行驶到房子 2
- 收拾房子 2 的玻璃垃圾
- 从房子 2 行驶到房子 3
- 收拾房子 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
解题思路一：处理垃圾和路程单独计算。
- 所有垃圾事一定要处理完的！
for g in garbage: ans += len(g) - 反向遍历
garbage数组，得到每个垃圾车需要到达的最远距离，即可计算出所需路程时间。
class Solution:def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:n = len(garbage)ans = 0for g in garbage:ans += len(g)G, M, P = 0, 0, 0for i in range(len(garbage) - 1, 0, -1):if 'G' in garbage[i]:G = ians += sum(travel[:G])breakfor i in range(len(garbage) - 1, 0, -1):if 'M' in garbage[i]:M = ians += sum(travel[:M])breakfor i in range(len(garbage) - 1, 0, -1):if 'P' in garbage[i]:P = ians += sum(travel[: P])breakreturn ans# 简化
class Solution:def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:n = len(garbage)ans = sum(map(len, garbage))for c in "GMP":for i, g in enumerate(reversed(garbage)):if c in g:ans += sum(travel[:n-i-1])breakreturn ans
时间复杂度：O(n)
空间复杂度：O(1)
解题思路二：逆向思维，计算多走的路
class Solution:def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:ans = sum(map(len, garbage)) + sum(travel) * 3for c in "MPG":for g, t in zip(reversed(garbage), reversed(travel)):if c in g:breakans -= t # 没有垃圾 c，多跑了return ans
时间复杂度：O(n)
空间复杂度：O(1)
解题思路三：只记录，当前t需要计算几次
class Solution:def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:ans = len(garbage[0])seen = set()for g, t in zip(reversed(garbage), reversed(travel)):seen.update(g)ans += len(g) + t * len(seen)return ans
时间复杂度：O(n)
空间复杂度：O(n)
♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠