「每日LeetCode」2021年4月6日

本文最后更新于：2023年3月19日 晚上

Lt1189. “气球” 的最大数量

1189. “气球” 的最大数量

给你一个字符串 text，你需要使用 text 中的字母来拼凑尽可能多的单词 “balloon”（气球）。
字符串 text 中的每个字母最多只能被使用一次。请你返回最多可以拼凑出多少个单词 “balloon”**。
**示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

思路

先用一个 map 记录出现的元素及其个数，用一个 set 记录 map 需要出现的 key 值 balon 五个，当 map 有这五个 key 值时，遍历 balloon 删除 map 中对应的个数再生成字符串进行计数，直到不能再生成时返回计数。

改进

其实就是求 balon 每个元素个数的最小值，其中 l、o 需要除以二。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {string} text
 * @return {number}
 */
var maxNumberOfBalloons = function (text) {
  const map = new Map();
  for (const char of text) {
    if (!map.has(char)) map.set(char, 1);
    else map.set(char, map.get(char) + 1);
  }
  const charSet = new Set("balloon".split(""));
  let res = 0;
  while ([...charSet.values()].every((e) => map.has(e))) {
    let temp = "";
    for (const char of "balloon") {
      if (!map.has(char)) break;
      if (map.get(char) === 1) map.delete(char);
      else map.set(char, map.get(char) - 1);
      temp += char;
    }
    if (temp === "balloon") res++;
  }
  return res;
};

改进

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {string} text
 * @return {number}
 */
var maxNumberOfBalloons = function (text) {
  const map = new Map();
  for (const char of text) {
    if (!map.has(char)) map.set(char, 1);
    else map.set(char, map.get(char) + 1);
  }
  for (const char of "balon") {
    if (!map.has(char)) map.set(char, 0);
  }

  return Math.min(
    map.get("b"),
    map.get("a"),
    parseInt(map.get("l") / 2),
    parseInt(map.get("o") / 2),
    map.get("n")
  );
};