Question

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

English Version

题目描述

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

解法

方法一：计数统计

由于题目中说明同一时刻只有一辆车处于使用状态，因此我们直接模拟每辆车的运行过程，累加时间。

更进一步思考，我们发现，答案的总耗时其实可以分成两部分：

1. 所有垃圾的数量，我们遍历 garbage 中的每一项 v，然后累加 v.length 就能得到；
2. 根据每一种垃圾在 garbage 中最后一次出现的位置 i，我们累加 travel[0..i) 即可。这里可以先算出 travel 的前缀和。

时间复杂度 $O(n)$，其中 $n$ 为垃圾的数量。

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

class Solution {
  public int garbageCollection(String[] garbage, int[] travel) {
    int[] last = new int[26];
    int n = garbage.length;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      int k = garbage[i].length();
      ans += k;
      for (int j = 0; j < k; ++j) {
        last[garbage[i].charAt(j) - 'A'] = i;
      }
    }
    int m = travel.length;
    int[] s = new int[m + 1];
    for (int i = 0; i < m; ++i) {
      s[i + 1] = s[i] + travel[i];
    }
    for (int i : last) {
      ans += s[i];
    }
    return ans;
  }
}

class Solution {
public:
  int garbageCollection(vector<string>& garbage, vector<int>& travel) {
    int n = garbage.size(), m = travel.size();
    int last[26]{};
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      ans += garbage[i].size();
      for (char& c : garbage[i]) {
        last[c - 'A'] = i;
      }
    }
    int s[m + 1];
    s[0] = 0;
    for (int i = 1; i <= m; ++i) {
      s[i] = s[i - 1] + travel[i - 1];
    }
    for (int i : last) {
      ans += s[i];
    }
    return ans;
  }
};

func garbageCollection(garbage []string, travel []int) (ans int) {
  last := [26]int{}
  for i, s := range garbage {
    ans += len(s)
    for _, c := range s {
      last[c-'A'] = i
    }
  }
  s := make([]int, len(travel)+1)
  for i, x := range travel {
    s[i+1] = s[i] + x
  }
  for _, i := range last {
    ans += s[i]
  }
  return
}

function garbageCollection(garbage: string[], travel: number[]): number {
  const n = garbage.length;
  const m = travel.length;
  let ans = 0;
  const last = new Array(26).fill(0);
  for (let i = 0; i < n; ++i) {
    ans += garbage[i].length;
    for (const c of garbage[i]) {
      last[c.charCodeAt(0) - 'A'.charCodeAt(0)] = i;
    }
  }
  const s = new Array(m + 1).fill(0);
  for (let i = 1; i <= m; ++i) {
    s[i] = s[i - 1] + travel[i - 1];
  }
  for (const i of last) {
    ans += s[i];
  }
  return ans;
}

impl Solution {
  pub fn garbage_collection(garbage: Vec<String>, travel: Vec<i32>) -> i32 {
    let n = garbage.len();
    let cs = [b'M', b'P', b'G'];
    let mut count = [0, 0, 0];
    for s in garbage.iter() {
      for c in s.as_bytes().iter() {
        count[if c == &b'M' { 0 } else if c == &b'P' { 1 } else { 2 }] += 1;
      }
    }

    let mut res = 0;
    for i in 0..3 {
      for j in 0..n {
        let s = &garbage[j];
        for c in s.as_bytes().iter() {
          if c == &cs[i] {
            res += 1;
            count[i] -= 1;
          }
        }
        if count[i] == 0 {
          break;
        }

        res += travel[j];
      }
    }
    res
  }
}

public class Solution {
  public int GarbageCollection(string[] garbage, int[] travel) {
    int len = garbage.Length;
    int res = 0;
    HashSet<char> s = new HashSet<char>();
    for (int i = len - 1; i >= 0; i--) {
      foreach (char ch in garbage[i].ToCharArray()) {
        if (!s.Contains(ch))
          s.Add(ch);
      }
      res += garbage[i].Length;
      res += i > 0 ? s.Count * travel[i - 1] : 0;
    }
    return res;
  }
}

方法二

class Solution:
  def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:
    def f(x: str) -> int:
      ans = 0
      st = 0
      for i, s in enumerate(garbage):
        if t := s.count(x):
          ans += t + st
          st = 0
        if i < len(travel):
          st += travel[i]
      return ans

    return f('M') + f('P') + f('G')

class Solution {
  private String[] garbage;
  private int[] travel;

  public int garbageCollection(String[] garbage, int[] travel) {
    this.garbage = garbage;
    this.travel = travel;
    return f('M') + f('P') + f('G');
  }

  private int f(char c) {
    int ans = 0;
    int st = 0;
    for (int i = 0; i < garbage.length; ++i) {
      int cnt = 0;
      for (int j = 0; j < garbage[i].length(); ++j) {
        if (garbage[i].charAt(j) == c) {
          ++cnt;
        }
      }
      if (cnt > 0) {
        ans += cnt + st;
        st = 0;
      }
      if (i < travel.length) {
        st += travel[i];
      }
    }
    return ans;
  }
}

class Solution {
public:
  int garbageCollection(vector<string>& garbage, vector<int>& travel) {
    auto f = [&](char x) {
      int ans = 0, st = 0;
      for (int i = 0; i < garbage.size(); ++i) {
        int cnt = 0;
        for (char& c : garbage[i]) {
          if (c == x) {
            ++cnt;
          }
        }
        if (cnt > 0) {
          ans += cnt + st;
          st = 0;
        }
        if (i < travel.size()) {
          st += travel[i];
        }
      }
      return ans;
    };
    return f('M') + f('P') + f('G');
  }
};

func garbageCollection(garbage []string, travel []int) (ans int) {
  f := func(x rune) int {
    ans, st := 0, 0
    for i, s := range garbage {
      cnt := strings.Count(s, string(x))
      if cnt > 0 {
        ans += cnt + st
        st = 0
      }
      if i < len(travel) {
        st += travel[i]
      }
    }
    return ans
  }
  return f('M') + f('P') + f('G')
}

function garbageCollection(garbage: string[], travel: number[]): number {
  const f = (x: string) => {
    let ans = 0;
    let st = 0;
    for (let i = 0; i < garbage.length; ++i) {
      let cnt = 0;
      for (const c of garbage[i]) {
        if (c === x) {
          ++cnt;
        }
      }
      if (cnt > 0) {
        ans += cnt + st;
        st = 0;
      }
      if (i < travel.length) {
        st += travel[i];
      }
    }
    return ans;
  };
  return f('M') + f('P') + f('G');
}