1189. Maximum Number of Balloons

Given a string text, you want to use the characters of text to form as many instances of the word “balloon” as possible.

You can use each character in text at most once. Return the maximum number of instances that can be formed.

Example 1:

Input: text = "nlaebolko"
Output: 1

Example 2:

Input: text = "loonbalxballpoon"
Output: 2

Example 3:

Input: text = "leetcode"
Output: 0

这道题给了一个字符串 text,问用其中的字符最多能组成多少个 ballon,每个字符最多使用一次。对于一道 Easy 的题目来说,并没有太大的难度,就是考察了一个统计字符出现的次数的操作,用一个 HashMap 来建立每个字符和其出现次数之间的映射就可以了。balloon 中的字符 b,a,n 分别出现了一次,l和o出现了两次,怎么算最多能拼成多个 balloon 呢,当然要找这些字符出现次数最少的那个,就像木桶盛水一样,最短的那个板子决定了盛水总量。然后遍历 balloon 中的每个字符,取其中的最小值,注意对于l和o字符要将次数除以2,因为它们分别都出现了2次,最终返回这个最小值即可,参见代码如下:

class Solution {
public:
    int maxNumberOfBalloons(string text) {
        int res = INT_MAX;
        string balloon = "balloon";
        unordered_map<char, int> charCnt;
        for (char c : text) ++charCnt[c];
        for (char c : balloon) {
            if (c == 'l' || c == 'o') res = min(res, charCnt[c] / 2);
            else res = min(res, charCnt[c]);
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1189

参考资料:

https://leetcode.com/problems/maximum-number-of-balloons/

https://leetcode.com/problems/maximum-number-of-balloons/discuss/382396/JavaPython-3-Count-solution-w-analysis.

https://leetcode.com/problems/maximum-number-of-balloons/discuss/382401/WithComments-StraightForward-Java-Simple-count-of-chars

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation