関小君刷题记

题目大意：

“气球” 的最大数量

给你一个字符串 text，你需要使用 text 中的字母来拼凑尽可能多的单词 “balloon”（气球）。

字符串 text 中的每个字母最多只能被使用一次。请你返回最多可以拼凑出多少个单词 “balloon”。

示例 1：

输入：text = "nlaebolko"
输出：1

示例 2：

输入：text = "loonbalxballpoon"
输出：2

示例 3：

输入：text = "leetcode"
输出：0

提示：

• 1 <= text.length <= 10^4
• text 全部由小写英文字母组成

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1189

解题思路分析：

这道题难度不大，要看给定的字符串中包含多少个balloon这个单词，我们需要知道原字符串中包含几个b，几个a，几个l，几个o，以及以及n。首先遍历一下原字符串，累加出每个字符出现的次数，然后再看看b，a，l，o，n各有多少个。注意，在balloon这个单词中l和o出现了2次，因此他们需要较之其他字符双倍的数量。出现次数最少的那个字符的个数即是答案。

看下实现代码：

public int maxNumberOfBalloons(String text) {
    int[] count = new int[26]; // 计算出每种字符出现的次数
    for(int i=0;i<text.length();i++){
        count[text.charAt(i)-'a']++;
    }
    int res = Integer.MAX_VALUE; // 返回结果
    for(int i=0;i<5;i++){
        char c = "balon".charAt(i); // 查看balon每个字符出现的次数
        int num = count[c-'a'];
        if(c == 'l' || c=='o'){ // 如果是l或者o，次数除以2
            num /= 2;
        }
        if(num==0){ // 如果出现次数为0，直接返回0
            return 0;
        }
        res = Math.min(res, num); // 找到出现次数最少的即是结果
    }
    return res;
}

本题解法执行时间为2ms。

Runtime: 2 ms, faster than 73.86% of Java online submissions for Maximum Number of Balloons.

Memory Usage: 36.1 MB, less than 100.00% of Java online submissions for Maximum Number of Balloons.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1189-maximum-number-of-balloons-解题思路分析/