Last Updated on 2023-11-20 by Clay
題目
You are given a 0-indexed array of strings garbage where garbage[i] represents the assortment of garbage at the ith house. garbage[i] consists only of the characters 'M', 'P' and 'G' representing one unit of metal, paper and glass garbage respectively. Picking up one unit of any type of garbage takes 1 minute.
You are also given a 0-indexed integer array travel where travel[i] is the number of minutes needed to go from house i to house i + 1.
There are three garbage trucks in the city, each responsible for picking up one type of garbage. Each garbage truck starts at house 0 and must visit each house in order; however, they do not need to visit every house.
Only one garbage truck may be used at any given moment. While one truck is driving or picking up garbage, the other two trucks cannot do anything.
Return the minimum number of minutes needed to pick up all the garbage.
Example 1:Input: garbage = ["G","P","GP","GG"], travel = [2,4,3] Output: 21
Explanation: The paper garbage truck: 1. Travels from house 0 to house 1 2. Collects the paper garbage at house 1 3. Travels from house 1 to house 2 4. Collects the paper garbage at house 2 Altogether, it takes 8 minutes to pick up all the paper garbage. The glass garbage truck: 1. Collects the glass garbage at house 0 2. Travels from house 0 to house 1 3. Travels from house 1 to house 2 4. Collects the glass garbage at house 2 5. Travels from house 2 to house 3 6. Collects the glass garbage at house 3 Altogether, it takes 13 minutes to pick up all the glass garbage. Since there is no metal garbage, we do not need to consider the metal garbage truck. Therefore, it takes a total of 8 + 13 = 21 minutes to collect all the garbage.
Example 2:Input: garbage = ["MMM","PGM","GP"], travel = [3,10] Output: 37
Explanation: The metal garbage truck takes 7 minutes to pick up all the metal garbage. The paper garbage truck takes 15 minutes to pick up all the paper garbage. The glass garbage truck takes 15 minutes to pick up all the glass garbage. It takes a total of 7 + 15 + 15 = 37 minutes to collect all the garbage.
Constraints:
2 <= garbage.length <= 105garbage[i]consists of only the letters'M','P', and'G'.1 <= garbage[i].length <= 10travel.length == garbage.length - 11 <= travel[i] <= 100
題目給定兩個輸入，garbage 和 travel。其中 garbage 內的元素是字串，字串中只會出現三個字元：G、P、M。
G 代表一般垃圾、P 代表紙類垃圾、M 代表金屬垃圾。每種垃圾的垃圾車都是不同的。一次只能使用一台垃圾車（代表時間不會重疊，題目複雜性較低），並且從 house_i 移動到 house_i+1 的時間為 travel[i] 分鐘、收垃圾的時間為 1 分鐘。
每台垃圾車的都從 house_0 開始，計算收完所有的垃圾，最快需要多久？
解題思路
直覺上來看，反過來看會比較容易：在還沒遇到自己種類的垃圾時，都不需要開始計算前一刻移動的時間。與此同時，我們要計算每種垃圾出現的次數，最後垃圾出現的次數等於回收垃圾所花的時間。
而移動時間則是從每項垃圾至少有 1 以後，才需要計算。比方說範例一：
["G", "P", "GP", "GG"]，移動時間為 [2, 4, 3]。
而我們反過來看，發現從 GG 開始，PM 的垃圾車都不需要移動到這裡。所以只計算 G 移動到這裡所需要的時間 total = 3 + 2（GG）。
接著是 GP，我們會發現 P 垃圾車至少需要移動到這裡了，所以總共時間 total = 5 + 2 + (4 * 2) = 15。
接著是 P，總共時間是 total = 15 + 1 + (2 * 2) = 20，可以看到 M 車到現在都還沒出發。
最後則是 G，所有的車一開始都從這裡開始，所以不用計算移動，只需要計算垃圾回收時間 total = 20 + 1 = 21。
最後所花的時間就是 21。
複雜度
| Time Complexity | O(n) |
| Space Complexity | O(1) |
C++ 範例程式碼
class Solution {
public:
int garbageCollection(vector<string>& garbage, vector<int>& travel) {
// Init
int total = 0;
unordered_map<char, int> c2n;
// Count the total times
for (int i=garbage.size()-1; i>0; --i) {
for (int j=0; j<garbage[i].size(); ++j) {
++c2n[garbage[i][j]];
}
if (c2n['G'] > 0) {
total += travel[i-1];
}
if (c2n['P'] > 0) {
total += travel[i-1];
}
if (c2n['M'] > 0) {
total += travel[i-1];
}
}
// At house 0
for (char& c: garbage.front()) {
++c2n[c];
}
return total + c2n['G'] + c2n['P'] + c2n['M'];
}
};Python 範例程式碼
class Solution:
def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:
# Init
total = 0
c2n = {}
# Count the total times
for i in range(len(garbage)-1, 0, -1):
for c in garbage[i]:
c2n[c] = c2n.get(c, 0) + 1
if c2n.get('G'):
total += travel[i-1]
if c2n.get('P'):
total += travel[i-1]
if c2n.get('M'):
total += travel[i-1]
# At house 0
return total + len(garbage[0]) + c2n.get('G', 0) + c2n.get('P', 0) + c2n.get('M', 0)