一次遍历，LeetCode 2391. 收集垃圾的最少总时间

本文主要是介绍一次遍历，LeetCode 2391. 收集垃圾的最少总时间，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

1、题目描述

给你一个下标从 0 开始的字符串数组 garbage ，其中 garbage[i] 表示第 i 个房子的垃圾集合。garbage[i] 只包含字符 'M' ，'P' 和 'G' ，但可能包含多个相同字符，每个字符分别表示一单位的金属、纸和玻璃。垃圾车收拾 一 单位的任何一种垃圾都需要花费 1 分钟。

同时给你一个下标从 0 开始的整数数组 travel ，其中 travel[i] 是垃圾车从房子 i 行驶到房子 i + 1 需要的分钟数。

城市里总共有三辆垃圾车，分别收拾三种垃圾。每辆垃圾车都从房子 0 出发，按顺序 到达每一栋房子。但它们 不是必须 到达所有的房子。

任何时刻只有 一辆 垃圾车处在使用状态。当一辆垃圾车在行驶或者收拾垃圾的时候，另外两辆车 不能 做任何事情。

请你返回收拾完所有垃圾需要花费的 最少 总分钟数。

2、接口描述

python3

​

class Solution:def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:

cpp

​

class Solution {
public:int garbageCollection(vector<string>& garbage, vector<int>& travel) {}
};

3、原题链接

2391. 收集垃圾的最少总时间

---

二、解题报告

1、思路分析

花费来自于：捡取所有垃圾 和 每个车所需的移动距离

就是一个模拟题，遍历garbage，如果某个垃圾种类出现，对应的垃圾车的移动距离更新下

2、复杂度

时间复杂度： O(n)空间复杂度：O(1)

3、代码详解

python3

​

class Solution:def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:c1, c2, c3 = 0, 0, 0s = 0pre = 0travel = [0] + travelfor i, x in enumerate(garbage):s += len(x)pre += travel[i]if 'M' in x:c1 = preif 'P' in x:c2 = preif 'G' in x:c3 = prereturn c1 + c2 + c3 + s

cpp

​

class Solution {
public:int garbageCollection(vector<string>& garbage, vector<int>& travel) {int c1 = 0, c2 = 0, c3 = 0, s = 0;for (int i = 0, pre = 0, n = garbage.size(); i < n; i ++) {s += garbage[i].size();pre += i ? travel[i - 1] : 0;if(~garbage[i].find('M'))c1 = pre;if(~garbage[i].find('P'))c2 = pre;if(~garbage[i].find('G'))c3 = pre;}return s + c1 + c2 + c3;}
};

这篇关于一次遍历，LeetCode 2391. 收集垃圾的最少总时间的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---