收集垃圾的最少总时间

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

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

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

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

php 解法, 执行用时: 305 ms, 内存消耗: 41.8 MB, 提交时间: 2024-05-11 09:31:12

class Solution {

    /**
     * @param String[] $garbage
     * @param Integer[] $travel
     * @return Integer
     */
    function garbageCollection($garbage, $travel) {
        $ans = strlen($garbage[0]);
        $seen = [];
        for ( $i = count($garbage) - 1; $i > 0; $i-- ) {
            $g = $garbage[$i];
            foreach ( str_split($g) as $c ) {
                $seen[$c] = 0;
            }
            $ans += strlen($g) + $travel[$i-1] * count($seen);
        }
        return $ans;
    }
}

rust 解法, 执行用时: 42 ms, 内存消耗: 9 MB, 提交时间: 2024-05-11 09:24:41

use std::collections::HashSet;

impl Solution {
    // 倒序，贡献法
    pub fn garbage_collection(garbage: Vec<String>, travel: Vec<i32>) -> i32 {
        let mut ans = garbage[0].len() as i32;
        let mut seen = HashSet::new();
        for (g, &t) in garbage.iter().rev().zip(travel.iter().rev()) {
            seen.extend(g.chars());
            ans += g.len() as i32 + t * seen.len() as i32;
        }
        ans
    }
    
    // 正序
    pub fn garbage_collection2(garbage: Vec<String>, travel: Vec<i32>) -> i32 {
        let mut ans = garbage[0].len() as i32;
        let mut sum_t = 0;
        let mut t_map = [0; 4];
        for i in 1..garbage.len() {
            let s = &garbage[i];
            ans += s.len() as i32;
            sum_t += travel[i - 1];
            for c in s.chars() {
                ans += sum_t - t_map[c as usize & 3];
                t_map[c as usize & 3] = sum_t;
            }
        }
        ans
    }
    
    // 多次遍历
    pub fn garbage_collection3(garbage: Vec<String>, travel: Vec<i32>) -> i32 {
        let mut ans = travel.iter().sum::<i32>() * 3 +
            garbage.iter().map(|g| g.len()).sum::<usize>() as i32;
        for c in "MPG".chars() {
            for (g, &t) in garbage.iter().rev().zip(travel.iter().rev()) {
                if g.contains(c) {
                    break;
                }
                ans -= t; // 没有垃圾 c，多跑了
            }
        }
        ans
    }
}

javascript 解法, 执行用时: 149 ms, 内存消耗: 64.6 MB, 提交时间: 2024-05-11 09:22:51

/**
 * @param {string[]} garbage
 * @param {number[]} travel
 * @return {number}
 */
var garbageCollection = function(garbage, travel) {
    let ans = garbage[0].length;
    const seen = new Set();
    for (let i = garbage.length - 1; i; i--) {
        const g = garbage[i];
        for (const c of g) {
            seen.add(c);
        }
        ans += g.length + travel[i - 1] * seen.size;
    }
    return ans;
};

var garbageCollection2 = function(garbage, travel) {
    let ans = garbage[0].length;
    let sumT = 0;
    let tMap = Array(4).fill(0);
    for (let i = 1; i < garbage.length; i++) {
        let g = garbage[i];
        ans += g.length;
        sumT += travel[i - 1];
        for (const c of g) {
            ans += sumT - tMap[c.charCodeAt(0) & 3];
            tMap[c.charCodeAt(0) & 3] = sumT;
        }
    }
    return ans;
};

var garbageCollection3 = function(garbage, travel) {
    let ans = _.sum(travel) * 3;
    for (const g of garbage) {
        ans += g.length;
    }
    for (const c of ['M', 'P', 'G']) {
        for (let i = garbage.length - 1; i && !garbage[i].includes(c); i--) {
            ans -= travel[i - 1]; // 没有垃圾 c，多跑了
        }
    }
    return ans;
};

golang 解法, 执行用时: 105 ms, 内存消耗: 13.8 MB, 提交时间: 2024-05-11 09:21:57

func garbageCollection(garbage []string, travel []int) (ans int) {
    for _, s := range garbage {
        ans += len(s)
    }
    for _, t := range travel {
        ans += t * 3
    }
    for _, c := range []byte("MPG") {
        for i := len(garbage) - 1; i > 0 && strings.IndexByte(garbage[i], c) < 0; i-- {
            ans -= travel[i-1] // 没有垃圾 c，多跑了
        }
    }
    return
}

// 正序一次
func garbageCollection2(garbage []string, travel []int) int {
    ans := len(garbage[0])
    sumT := 0
    tMap := [4]int{}
    for i, g := range garbage[1:] {
        ans += len(g)
        sumT += travel[i]
        for _, c := range g {
            ans += sumT - tMap[c&3]
            tMap[c&3] = sumT
        }
    }
    return ans
}

// 倒序（贡献法）
func garbageCollection3(garbage []string, travel []int) int {
    ans := len(garbage[0])
    seen := map[rune]struct{}{}
    for i := len(garbage) - 1; i > 0; i-- {
        g := garbage[i]
        for _, c := range g {
            seen[c] = struct{}{}
        }
        ans += len(g) + travel[i-1]*len(seen)
    }
    return ans
}

python3 解法, 执行用时: 122 ms, 内存消耗: 37 MB, 提交时间: 2024-05-11 09:20:52

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
        
    # 正序
    def garbageCollection2(self, garbage: List[str], travel: List[int]) -> int:
        ans = sum_t = 0
        t_map = defaultdict(int)
        # 避免 [0] + travel 产生额外空间
        for i, g in enumerate(garbage):
            ans += len(g)
            sum_t += travel[i - 1] if i else 0
            for c in g:
                ans += sum_t - t_map[c]
                t_map[c] = sum_t
        return ans
        
    # 多次
    def garbageCollection3(self, garbage: List[str], travel: List[int]) -> int:
        ans = sum(map(len, garbage)) + sum(travel) * 3
        for c in "MPG":
            for g, t in zip(reversed(garbage), reversed(travel)):
                if c in g:
                    break
                ans -= t  # 没有垃圾 c，多跑了
        return ans

java 解法, 执行用时: 2 ms, 内存消耗: 58.7 MB, 提交时间: 2024-05-11 09:19:43

class Solution {
    // 多次遍历
    public int garbageCollection(String[] garbage, int[] travel) {
        int ans = 0;
        for (String g : garbage) {
            ans += g.length();
        }
        for (int t : travel) {
            ans += t * 3;
        }
        for (char c : new char[]{'M', 'P', 'G'}) {
            for (int i = garbage.length - 1; i > 0 && garbage[i].indexOf(c) < 0; i--) {
                ans -= travel[i - 1]; // 没有垃圾 c，多跑了
            }
        }
        return ans;
    }
    
    // 正序一次
    public int garbageCollection2(String[] garbage, int[] travel) {
        int ans = garbage[0].length();
        int sumT = 0;
        int[] tMap = new int[4];
        for (int i = 1; i < garbage.length; i++) {
            char[] s = garbage[i].toCharArray();
            ans += s.length;
            sumT += travel[i - 1];
            for (char c : s) {
                ans += sumT - tMap[c & 3];
                tMap[c & 3] = sumT;
            }
        }
        return ans;
    }
    
    // 倒序一次
    public int garbageCollection3(String[] garbage, int[] travel) {
        int ans = garbage[0].length();
        HashSet<Character> seen = new HashSet<>();
        for (int i = garbage.length - 1; i > 0; i--) {
            char[] g = garbage[i].toCharArray();
            for (char c : g) {
                seen.add(c);
            }
            ans += g.length + travel[i - 1] * seen.size();
        }
        return ans;
    }
}

cpp 解法, 执行用时: 167 ms, 内存消耗: 103.4 MB, 提交时间: 2024-05-11 09:18:18

class Solution {
public:
    // 倒序一次遍历
    int garbageCollection(vector<string>& garbage, vector<int>& travel) {
        int ans = garbage[0].length();
        unordered_set<char> seen;
        for (int i = garbage.size() - 1; i; i--) {
            auto& g = garbage[i];
            seen.insert(g.begin(), g.end());
            ans += g.length() + travel[i - 1] * seen.size();
        }
        return ans;
    }
    
    // 正序一次遍历
    int garbageCollection2(vector<string>& garbage, vector<int>& travel) {
        int ans = garbage[0].length();
        int sum_t = 0;
        int t_map[4]{};
        for (int i = 1; i < garbage.size(); i++) {
            auto& s = garbage[i];
            ans += s.length();
            sum_t += travel[i - 1];
            for (char c : s) {
                ans += sum_t - t_map[c & 3];
                t_map[c & 3] = sum_t;
            }
        }
        return ans;
    }
    
    // 多次遍历
    int garbageCollection3(vector<string>& garbage, vector<int>& travel) {
        int ans = reduce(travel.begin(), travel.end()) * 3;
        for (auto& g : garbage) {
            ans += g.length();
        }
        for (char c : {'M', 'P', 'G'}) {
            for (int i = garbage.size() - 1; i && garbage[i].find(c) == string::npos; i--) {
                ans -= travel[i - 1]; // 没有垃圾 c，多跑了
            }
        }
        return ans;
    }
};

python3 解法, 执行用时: 164 ms, 内存消耗: 32.7 MB, 提交时间: 2022-11-09 15:49:16

class Solution:
    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:
        ans = 0
        right = {}
        for i, s in enumerate(garbage):
            ans += len(s)
            for c in s:
                right[c] = i
        return ans + sum(sum(travel[:r]) for r in right.values())

上一题

下一题

详情