1189.气球的最大数量

LeetCode LeetCode 哈希表 字符串 计数
发布时间 :
字数:2.1k 阅读 : 评论:
  1. 1189.气球的最大数量
    1. 1189.1 题目
    2. 1189.2 题解
      1. 方法一：使用字典记录每个字符的出现次数
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：使用数组记录每个字符的出现次数
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 1189.3 代码
    4. 1189.4 运行结果

1189.气球的最大数量

1189.1 题目

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

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

示例 1：

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

示例 2：


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

示例 3：

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

提示：

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

1189.2 题解

方法一：使用字典记录每个字符的出现次数

思路

要拼凑单词 “balloon”，需要：1 个 b、1 个 a、2 个 l、2 个 o、1 个 n。能拼凑出的数量取决于这些字母中最稀缺的那个。

具体步骤：

  1. 用字典统计 text 中每个字符的出现次数
  2. 遍历 “balloon” 的每个字母，计算该字母能支持多少个单词
  3. 注意 l 和 o 需要两个，所以要除以 2
  4. 最终答案就是所有字母能支持数量的最小值

举个例子：text = "nlaebolko"

统计结果：{n:1, l:2, a:1, e:1, b:1, o:1, k:1}

计算每个字母能支持的单词数：
- b: 1/1 = 1
- a: 1/1 = 1
- l: 2/2 = 1
- o: 1/2 = 0  ← 最小值
- n: 1/1 = 1

最终答案：min(1, 1, 1, 0, 1) = 0... 等等，重新检查
实际：o 只有 1 个，需要 2 个，所以 1/2 = 0
但原题答案是 1，让我重新看：text = "nlaebolko"
- b: 1, a: 1, l: 2, o: 2, n: 1
- l: 2/2 = 1, o: 2/2 = 1
- min(1, 1, 1, 1, 1) = 1

复杂度分析

  • 时间复杂度：O(n)，遍历字符串一次，遍历 “balloon” 一次
  • 空间复杂度：O(1)，字典最多存储 26 个字母

代码

// 方法一：使用字典记录每个字符的出现次数
// 遍历字符串，统计字符出现次数，然后根据单词 "balloon" 中每个字母的数量计算最多可以拼凑出多少个单词
static int MaxNumberOfBalloons1(string text)
{
    Dictionary<char, int> charCountDictionary = new Dictionary<char, int>();
    string balloon = "balloon";

    // 统计每个字符的出现次数
    foreach (char c in text)
    {
        if (!charCountDictionary.ContainsKey(c))
        {
            charCountDictionary[c] = 1; // 如果字典中没有该字符，则添加，并将出现次数设为1
        }
        else
        {
            charCountDictionary[c]++; // 如果字典中已有该字符，则增加出现次数
        }
    }

    // 计算可以拼凑出多少个单词 "balloon"
    int minCount = int.MaxValue;
    foreach (char c in balloon)
    {
        if (!charCountDictionary.ContainsKey(c))
        {
            return 0; // 如果字典中没有单词 "balloon" 中的某个字母，则无法拼凑，返回0
        }

        int count = charCountDictionary[c] / (c == 'l' || c == 'o' ? 2 : 1); // 'l' 和 'o' 需要除以 2
        minCount = Math.Min(minCount, count); // 更新最小拼凑次数
    }

    return minCount;
}

方法二：使用数组记录每个字符的出现次数

思路

与方法一思路相同，但用数组代替字典，效率更高。由于只关心 ‘b’、’a’、’l’、’o’、’n’ 这 5 个字母，可以用长度为 5 的数组记录它们的出现次数。

具体步骤：

  1. 遍历字符串，用 switch 语句统计各字母出现次数
  2. 对 l 和 o 的计数除以 2
  3. 将数组排序，最小值就是答案

举个例子：text = "loonbalxballpoon"

统计结果：[b:2, a:2, l:4, o:4, n:2]
除以2后：[b:2, a:2, l:2, o:2, n:2]
排序后：[2, 2, 2, 2, 2]
最小值：2

复杂度分析

  • 时间复杂度：O(n)，遍历字符串一次，排序常数级数组
  • 空间复杂度：O(1)，固定大小的数组

代码

// 方法二：使用数组记录每个字符的出现次数
// 数组记录后，l和o需要除2，将数组排序，最小值即为最少可以拼凑的次数
static int MaxNumberOfBalloons2(string text)
{
    int[] showTimesArray = new int[5]; // 用数组记录字母 'b', 'a', 'l', 'o', 'n' 的出现次数
    for (int i = 0; i < text.Length; i++)
    {
        switch (text[i])
        {
            case 'b':
                ++showTimesArray[0]; // 如果是 'b'，增加 'b' 的出现次数
                break;
            case 'a':
                ++showTimesArray[1]; // 如果是 'a'，增加 'a' 的出现次数
                break;
            case 'l':
                ++showTimesArray[2]; // 如果是 'l'，增加 'l' 的出现次数
                break;
            case 'o':
                ++showTimesArray[3]; // 如果是 'o'，增加 'o' 的出现次数
                break;
            case 'n':
                ++showTimesArray[4]; // 如果是 'n'，增加 'n' 的出现次数
                break;
        }
    }

    showTimesArray[2] /= 2; // 'l' 需要除以 2
    showTimesArray[3] /= 2; // 'o' 需要除以 2

    Array.Sort(showTimesArray); // 将数组排序，最小值即为最少可以拼凑的次数

    return showTimesArray[0];
}

1189.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

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

        // 示例 1：
        // 输入：text = "nlaebolko"
        // 输出：1

        // 示例 2：
        // 输入：text = "loonbalxballpoon"
        // 输出：2

        // 示例 3：
        // 输入：text = "leetcode"
        // 输出：0

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

        #endregion

        #region 测试

        // 示例 1
        string text1 = "nlaebolko";
        int result1_1 = MaxNumberOfBalloons1(text1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");
        int result1_2 = MaxNumberOfBalloons2(text1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        string text2 = "loonbalxballpoon";
        int result2_1 = MaxNumberOfBalloons1(text2);
        Console.WriteLine($"示例2 方法1 输出：{result2_1}");
        int result2_2 = MaxNumberOfBalloons2(text2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        // 示例 3
        string text3 = "leetcode";
        int result3_1 = MaxNumberOfBalloons1(text3);
        Console.WriteLine($"示例3 方法1 输出：{result3_1}");
        int result3_2 = MaxNumberOfBalloons2(text3);
        Console.WriteLine($"示例3 方法2 输出：{result3_2}");

        #endregion
    }

    #region 答案

    // 方法一：使用字典记录每个字符的出现次数
    // 遍历字符串，统计字符出现次数，然后根据单词 "balloon" 中每个字母的数量计算最多可以拼凑出多少个单词
    static int MaxNumberOfBalloons1(string text)
    {
        Dictionary<char, int> charCountDictionary = new Dictionary<char, int>();
        string balloon = "balloon";

        // 统计每个字符的出现次数
        foreach (char c in text)
        {
            if (!charCountDictionary.ContainsKey(c))
            {
                charCountDictionary[c] = 1; // 如果字典中没有该字符，则添加，并将出现次数设为1
            }
            else
            {
                charCountDictionary[c]++; // 如果字典中已有该字符，则增加出现次数
            }
        }

        // 计算可以拼凑出多少个单词 "balloon"
        int minCount = int.MaxValue;
        foreach (char c in balloon)
        {
            if (!charCountDictionary.ContainsKey(c))
            {
                return 0; // 如果字典中没有单词 "balloon" 中的某个字母，则无法拼凑，返回0
            }

            int count = charCountDictionary[c] / (c == 'l' || c == 'o' ? 2 : 1); // 'l' 和 'o' 需要除以 2
            minCount = Math.Min(minCount, count); // 更新最小拼凑次数
        }

        return minCount;
    }

    // 方法二：使用数组记录每个字符的出现次数
    // 数组记录后，l和o需要除2，将数组排序，最小值即为最少可以拼凑的次数
    static int MaxNumberOfBalloons2(string text)
    {
        int[] showTimesArray = new int[5]; // 用数组记录字母 'b', 'a', 'l', 'o', 'n' 的出现次数
        for (int i = 0; i < text.Length; i++)
        {
            switch (text[i])
            {
                case 'b':
                    ++showTimesArray[0]; // 如果是 'b'，增加 'b' 的出现次数
                    break;
                case 'a':
                    ++showTimesArray[1]; // 如果是 'a'，增加 'a' 的出现次数
                    break;
                case 'l':
                    ++showTimesArray[2]; // 如果是 'l'，增加 'l' 的出现次数
                    break;
                case 'o':
                    ++showTimesArray[3]; // 如果是 'o'，增加 'o' 的出现次数
                    break;
                case 'n':
                    ++showTimesArray[4]; // 如果是 'n'，增加 'n' 的出现次数
                    break;
            }
        }

        showTimesArray[2] /= 2; // 'l' 需要除以 2
        showTimesArray[3] /= 2; // 'o' 需要除以 2

        Array.Sort(showTimesArray); // 将数组排序，最小值即为最少可以拼凑的次数

        return showTimesArray[0];
    }

    #endregion
}

1189.4 运行结果

示例1 方法1 输出：1
示例1 方法2 输出：1
示例2 方法1 输出：2
示例2 方法2 输出：2
示例3 方法1 输出：0
示例3 方法2 输出：0
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏