leetcode
leetcode 1101 ~ 1150
“气球” 的最大数量

“气球” 的最大数量

难度:

标签:

题目描述

给你一个字符串 text,你需要使用 text 中的字母来拼凑尽可能多的单词 "balloon"(气球)

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

 

示例 1:

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

示例 2:

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

示例 3:

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

 

提示:

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

代码结果

运行时间: 24 ms, 内存: 0.0 MB


/*
 * 思路:
 * 1. 使用Java Streams来简化字符计数过程。
 * 2. 统计每个字符的出现频率,并计算能够组成多少个 'balloon'。
 */

import java.util.function.Function;
import java.util.stream.Collectors;

public class Solution {
    public int maxNumberOfBalloons(String text) {
        Map<Character, Long> frequency = text.chars()
            .mapToObj(c -> (char) c)
            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
        return Math.min(frequency.getOrDefault('b', 0L).intValue(),
                        Math.min(frequency.getOrDefault('a', 0L).intValue(),
                        Math.min(frequency.getOrDefault('l', 0L).intValue() / 2,
                        Math.min(frequency.getOrDefault('o', 0L).intValue() / 2,
                                 frequency.getOrDefault('n', 0L).intValue()))));
    }
}

解释

方法:

该题解使用了一种高效的方法来计算可以拼凑出的单词 'balloon' 的最大数量。首先,它通过统计字符串 'text' 中 'b', 'a', 'l', 'o', 'n' 这五个字母的出现次数来确定能够组成多少单词 'balloon'。因为在 'balloon' 中,'l' 和 'o' 各出现了两次,所以需要对其实际计数进行除以2的操作(右移一位操作等同于除以2)。最后,通过取这些统计值的最小值来确定最多可以组成多少个单词 'balloon',因为组成单词所需的字母数量受到最少出现字母的限制。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么选择通过计算每个关键字母的数量来解决问题,而不是直接尝试构造单词 'balloon'?
通过计算每个关键字母的数量来解决问题是一种更为高效的方法。如果尝试直接构造单词 'balloon',我们可能需要反复检查和修改字符串,这在有大量重复字母或字符串很长时,会显著增加算法的复杂度和运行时间。相反,统计关键字母的数量可以在一次或几次遍历中完成,然后直接通过数学计算来确定可以构造的 'balloon' 单词的最大数量,这种方法更直接且效率更高。
🦆
在计算 'l' 和 'o' 的数量时,为什么要进行除以2的操作,这样的处理对结果的准确性有何影响?
在单词 'balloon' 中,字母 'l' 和 'o' 各出现了两次,因此在计算可以组成 'balloon' 的最大数量时,必须考虑到这一点。计算 'l' 和 'o' 的数量时进行除以2的操作是为了得到这两个字母能够组成 'balloon' 的对数,即每两个 'l' 或 'o' 才能构成一个 'balloon'。这样的处理是必须的,且能确保结果的准确性,因为它直接反映了这两个字母相对于其他字母在组成单词中的数量限制。
🦆
为什么使用位移操作 '>> 1' 来代替除以2,这两种操作在效率上有何区别?
位移操作 '>> 1' 通常会比传统的除以2操作效率更高,特别是在低级语言中,因为它直接在二进制层面上操作,而不涉及复杂的算术运算。在高级语言如 Python 中,这两种操作的性能差异可能不大,因为编译器或解释器会对常见操作进行优化。然而,使用位移操作在代码中可以提供一种更快、更直接的方式来表达除以2,且在某些情况下能稍微提升性能。
🦆
该算法中使用 text.count(char) 方法多次遍历整个字符串,是否有更高效的方法只遍历一次字符串就完成所有字母的统计?
是的,有更高效的方法可以通过只遍历一次字符串来统计所有必要的字母。可以使用一个字典来存储每个字母的出现次数,然后遍历字符串一次,对每个字符进行检查和计数。这种方法只需要一次遍历,相较于多次调用 count 方法,可以大幅提高效率。遍历完成后,可以从字典中直接获取 'b', 'a', 'l', 'o', 'n' 字母的计数并进行后续计算。这种方法在处理大型数据时尤为有用,因为它显著减少了重复遍历字符串的需要。

相关问题