题目： LCP 66.最小展台数量

题面

力扣嘉年华将举办一系列展览活动，后勤部将负责为每场展览提供所需要的展台。已知后勤部得到了一份需求清单，记录了近期展览所需要的展台类型， 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

Tips

1 <= demand.length,demand[i].length <= 100

demand[i][j] 仅为小写字母

Code

代码解释

这段 C++ 代码的目的是解决一个问题：给定多个字符串（表示不同天的需求），找到满足所有需求所需的最少展位数量。这个算法通过遍历每个字符串并记录每个字母的最大出现次数来解决问题。

class Solution {
public:
    int minNumBooths(vector<string>& demand) {
        const int N{26};  // 定义常量 N，表示字母表中字母的数量，即 26 个字母
        int* t1{new int[N]{0}}, *t2{new int[N]{0}};  // 动态分配两个大小为 26 的数组 t1 和 t2，并初始化为 0
  
        for(const auto& s : demand) {  // 遍历 demand 向量中的每个字符串 s
            for(const char& c : s) ++t2[c - 'a'];  // 遍历字符串 s 中的每个字符 c，增加 t2 中相应字母位置的计数
            for(int i{0}; i < N; ++i)  // 遍历字母表中的每个字母
                if(t2[i] > 0) {  // 如果 t2[i] 大于 0，说明当前字符串中该字母出现过
                    t1[i] = max(t1[i], t2[i]);  // 更新 t1[i]，保存该字母在所有字符串中的最大出现次数
                    t2[i] = 0;  // 重置 t2[i] 为 0，为下一个字符串做准备
                }
        }
        return accumulate(t1, t1 + N, 0);  // 累加 t1 数组中的所有值，返回总和，即所需的最少展位数量
    }
};

逐行解释

const int N{26};:
- 定义了一个常量 N，表示字母表中有 26 个字母。
int* t1{new int[N]{0}}, *t2{new int[N]{0}};:
- 动态分配了两个大小为 26 的整型数组 t1 和 t2，并将所有元素初始化为 0。
- t1 用来存储每个字母在所有需求字符串中出现的最大次数。
- t2 用来存储当前字符串中每个字母的出现次数。
for(const auto& s : demand) { ... }:
- 使用范围循环遍历 demand 向量中的每个字符串 s。
for(const char& c : s) ++t2[c - 'a'];:
- 遍历当前字符串 s 中的每个字符 c，并在 t2 数组中相应的位置增加计数。
- c - 'a' 计算出字符 c 在字母表中的位置，例如 'a' 对应 0，'b' 对应 1，以此类推。
for(int i{0}; i < N; ++i) ...:
- 遍历字母表中的每个字母，检查 t2 数组中是否有计数大于 0 的字母。
if(t2[i] > 0) { ... }:
- 如果当前字母在 t2 中的计数大于 0，说明该字母在当前字符串中出现过。
- 比较并更新 t1[i]，将该字母在所有字符串中的最大出现次数保存在 t1 中。
- 将 t2[i] 重置为 0，为下一个字符串准备。
return accumulate(t1, t1 + N, 0);:
- 使用 accumulate 函数计算并返回 t1 数组中所有元素的总和。
- t1 数组中每个位置的值表示某个字母的最大需求量，因此总和表示满足所有需求所需的最少展位数量。