leetcode每日一题2022-02-13
本题是一道模拟问题,思考方式是数学中的统计
题目描述
给你一个字符串 text,你需要使用 text 中的字母来拼凑尽可能多的单词 “balloon”(气球)。
字符串 text 中的每个字母最多只能被使用一次。请你返回最多可以拼凑出多少个单词 “balloon”。
样例
示例 1:
输入:text = “nlaebolko”
输出:1
示例 2:
输入:text = “loonbalxballpoon”
输出:2
示例 3:
输入:text = “leetcode”
输出:0
算法
(简单模拟)
单词balloon,其中我们发现共有5中字母,其中l和o分别出现了两次,我们设置一个数组letter用于存储字母出现的次数,并对存储o和l的对应数值/2,最后得到的数值中的最小值即为要求的balloon出现的次数
时间复杂度
设$C$为目标字符串的字符种类的数量,本题中$C = 5$,统计$text$的词频复杂度为$O(n)$,计算答案复杂度为$O(C)$。
整体复杂度为:
$O(n+C)$
C++ 代码
class Solution {
public:
int maxNumberOfBalloons(string text) {
vector<int> letter(5);
for (auto & word : text)
{
if (word == 'b') letter[0] ++ ;
if (word == 'a') letter[1] ++ ;
if (word == 'l') letter[2] ++ ; // 俩l
if (word == 'o') letter[3] ++ ; // 俩o
if (word == 'n') letter[4] ++ ;
}
letter[2] /= 2;
letter[3] /= 2;
// min_element范围[first,last),刚好使用.begin()和.end()可以使用,返回一个头指针
return *min_element(letter.begin(),letter.end());
}
};