1189.气球的最大数量

LeetCode LeetCode 哈希表字符串计数

发布时间 : 2000-01-11 01:08

字数:1.6k 阅读 :

评论:

1189.气球的最大数量

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" 中每个字母的数量计算最多可以拼凑出多少个单词
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];
}

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