每日一题:LeetCode:1189.气球的最大数量

浏览次数 : 次 2022-02-13

博文字数统计 : 486字 | 阅读所需时长 : 2分

× 文章目录

1. 2022-02-13：LeetCode：1189.气球的最大数量
1. 1.1. 1. 题目描述
2. 1.2. 2. 方法一：哈希计数

每日一题：LeetCode：1189.气球的最大数量
- 时间：2022-02-13
- 力扣难度：Easy
- 个人难度：Easy
- 数据结构：字符串、哈希表
- 算法：排序

2022-02-13：LeetCode：1189.气球的最大数量

1. 题目描述

题目：原题链接
- 给你一个字符串 text，你需要使用 text 中的字母来拼凑尽可能多的单词 “balloon”（气球）。
- 字符串 text 中的每个字母最多只能被使用一次。请你返回最多可以拼凑出多少个单词 “balloon”
- 1 <= text.length <= 10^4
输入输出规范
- 输入：字符串text
- 输出：气球个数
输入输出示例
- 输入：text = “loonbalxballpoon”
- 输出：2

2. 方法一：哈希计数

思路
- 本题需要求出字符串中的气球数量，实际上就是可以拼成的气球单词的个数
- 因此可以通过哈希表来对气球单词的每个字母进行计数，这里可以使用数组来作为哈希表
- 因为一个气球单词中需要两个字母o和l，所以即可以计数后，再除以2，也可以计数的时候使用一个布尔型的标记来表示是否凑成两个，凑成时再计数
- 最后，返回该哈希数组的最小元素，就是可以组成的气球的最大个数

题解

public int maxNumberOfBalloons(String text) {
    if(text == null || text.length() == 0) return 0;
    boolean oFlag = false, lFlag = false;
    int[] count = new int[5];
    for(int i = 0; i < text.length(); i++) {
        if(text.charAt(i) == 'b') count[0]++;
        else if(text.charAt(i) == 'a') count[1]++;
        else if(text.charAt(i) == 'n') count[4]++;
        else if(text.charAt(i) == 'l') {
            if(lFlag) count[2]++;
            lFlag = !lFlag;
        } else if(text.charAt(i) == 'o') {
            if(oFlag) count[3]++;
            oFlag = !oFlag;
        }
    }
    Arrays.sort(count);
    return count[0];
}

复杂度分析：n 是字符串的大小
- 时间复杂度：$O(n)$
- 空间复杂度：$O(C)$，C是常数，表示气球单词中包含的字母种类个数，本题C=5

本文作者： Chthollists
发布时间： 2022-02-13 22:53:20
最后更新： 2022-02-20 13:34:08
本文标题： 每日一题:LeetCode:1189.气球的最大数量
本文链接： https://chthollists.github.io/post/9ff2b50f.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！