最小展台数量

难度: Easy

力扣嘉年华将举办一系列展览活动，后勤部将负责为每场展览提供所需要的展台。已知后勤部得到了一份需求清单，记录了近期展览所需要的展台类型， `demand[i][j]` 表示第 `i` 天展览时第 `j` 个展台的类型。在满足每一天展台需求的基础上，请返回后勤部需要准备的 **最小** 展台数量。 **注意：** - 同一展台在不同天中可以重复使用。 **示例 1：** >输入：`demand = ["acd","bed","accd"]` > >输出：`6` > >解释： >第 `0` 天需要展台 `a、c、d`； >第 `1` 天需要展台 `b、e、d`； >第 `2` 天需要展台 `a、c、c、d`； >因此，后勤部准备 `abccde` 的展台，可以满足每天的展览需求; **示例 2：** >输入：`demand = ["abc","ab","ac","b"]` > >输出：`3` **提示：** - `1 <= demand.length,demand[i].length <= 100` - `demand[i][j]` 仅为小写字母

Submission

运行时间: 38 ms

内存: 16.0 MB

class Solution:
    def minNumBooths(self, demand: List[str]) -> int:
        dict_={}
        for i in demand:
            s=set(i)
            for j in s:
                if j in dict_:
                    dict_[j]=max(i.count(j),dict_[j])
                else:
                    dict_[j]=i.count(j)
        i=0
        for val in dict_.values():
            i+=val
        return i

Explain

题解的核心思路是使用一个字典来记录所有天中，每种展台类型所需的最大数量。首先遍历每天的需求，对于每天的展台类型，使用集合去重，然后对每个展台类型，计算当天所需的数量，并与字典中已记录的该展台类型的数量对比，更新为较大值。最后，将字典中所有值相加，得到总的最少展台数量。

时间复杂度: O(n * k^2)

空间复杂度: O(u)

class Solution:
    def minNumBooths(self, demand: List[str]) -> int:
        dict_ = {}
        # 遍历所有天的需求
        for i in demand:
            s = set(i)  # 去重，获取当天所需的所有不同展台类型
            # 遍历每种展台类型
            for j in s:
                # 如果字典中已有该展台，更新为最大需求量
                if j in dict_:
                    dict_[j] = max(i.count(j), dict_[j])
                else:
                    # 否则，直接记录该展台的需求量
                    dict_[j] = i.count(j)
        # 计算并返回所有展台的总最大需求量
        return sum(dict_.values())

Explore

使用集合去重展台类型是为了确保每天的需求中每种展台类型只被计算一次，这样可以避免在字典中进行不必要的多次更新。如果不使用集合去重，每次遇到一个展台类型就需要在字典中更新，这将导致多次不必要的字典操作，尤其是当一天中某个展台类型出现多次时。使用集合可以先确定哪些展台类型是需要的，然后只针对这些展台类型进行一次需求量的计算和字典更新，从而提高效率。

在确定字典中应该更新为最大需求量而不是累计需求量的依据是，问题的目标是找到满足所有天的需求所需要的最小展台数量。每种展台类型的需求量取决于单日需求的最大值，而不是需求的总和。如果使用累计需求量，会造成对展台数量的过度估计，因为不需要同时满足所有天的需求，而只需要满足任何给定一天中的最大需求。因此，只记录每种展台类型出现的最大单日需求量，就足以确保在任何一天都有足够的展台满足需求。

为了避免在每天的需求分析中重复计算字符的数量，可以在遍历每天的需求时，首先使用一个局部字典来记录该天中每种展台类型的数量。这样，对于每种类型，只需在局部字典中查找一次，然后与全局字典进行比较和可能的更新。这种方法减少了字符计数的次数，因为每种类型在每天只计算一次，而不是在每次出现时都重新计数。这不仅减少了计算量，也使代码更加清晰和高效。