服务器建设网站,一般网站维护费用,WordPress电子书模板模板,营销网站设计上海天气给你一个下标从 0 开始的字符串数组 garbage #xff0c;其中 garbage[i] 表示第 i 个房子的垃圾集合。garbage[i] 只包含字符 ‘M’ #xff0c;‘P’ 和 ‘G’ #xff0c;但可能包含多个相同字符#xff0c;每个字符分别表示一单位的金属、纸和玻璃。垃圾车收拾 一 单位…给你一个下标从 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.length 105 garbage[i] 只包含字母 ‘M’ ‘P’ 和 ‘G’ 。 1 garbage[i].length 10 travel.length garbage.length - 1 1 travel[i] 100
直接模拟即可
class Solution {
public:int garbageCollection(vectorstring garbage, vectorint travel) {int houseNum garbage.size();int time 0;int maxM -1;int maxP -1;int maxG -1;for (int i 0; i houseNum; i) {for (char c : garbage[i]) {if (c M) {maxM i;} else if (c P) {maxP i;} else if (c G) {maxG i;}time;}}for (int i 0; i houseNum - 1; i) {if (maxM i) {time travel[i];} if (maxP i) {time travel[i];}if (maxG i) {time travel[i];}}return time;}
};如果有n个房子此算法时间复杂度为On空间复杂度为O1。
