“气球” 的最大数量
难度:
标签:
题目描述
给你一个字符串 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'?
▷🦆
在计算 'l' 和 'o' 的数量时,为什么要进行除以2的操作,这样的处理对结果的准确性有何影响?
▷🦆
为什么使用位移操作 '>> 1' 来代替除以2,这两种操作在效率上有何区别?
▷🦆
该算法中使用 text.count(char) 方法多次遍历整个字符串,是否有更高效的方法只遍历一次字符串就完成所有字母的统计?
▷