LeetCode-Go 题解1189. Maximum Number of Balloons —— 用字母频次统计拼出最多的气球单词【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇技术指南围绕 LeetCode 第 1189 题「Maximum Number of Balloons」展开完整继承并深入讲解 leetcode/1189.Maximum-Number-of-Balloons 目录下题解文档中的题目描述、约束条件与解题思路并结合仓库内的 Go 源码与测试用例进行逐行剖析。读完本文你将掌握「以目标单词为模板做字母频次计数、按瓶颈字母取最小值」这一经典计数题套路并能直接在 LeetCode-Go 仓库中运行验证该题的实现与测试。题目理解用 text 中的字母拼出最多的 balloon原题文档给出的问题描述如下给定一个字符串text你需要使用text中的字母来拼凑尽可能多的单词balloon气球。字符串text中的每个字母最多只能被使用一次返回最多可以拼凑出多少个单词 balloon。换句话说这题并不是要你判断某个子串是否存在而是要求把整个text当作一个字母资源池每个字符用一次、用完即废问这个资源池最多能完整地生产出几个balloon。约束条件原题文档明确列出两道约束它们决定了算法的设计空间1 text.length 10^4字符串长度上限为 1 万O(n) 的线性扫描完全够用text全部由小写英文字母组成这直接启发了用定长 26 的数组做频次统计的做法因为字符范围是固定且有限的。示例与预期输出原题文档给出三组标准示例输入 text输出说明nlaebolko1恰好能凑出 1 个 balloonloonbalxballpoon2字母资源足够凑出 2 个 balloonleetcode0缺少b、a、l、o、n中的关键字母凑不出任何完整单词解题思路频次统计 取五个字母的短板原题文档给出的核心思路只有一句话先统计 26 个字母每个字母的频次然后取出 balloon 这 5 个字母出现频次最小的值就是结果。 下面把它拆解成可执行的三步并结合仓库源码印证。第一步为什么要统计全部 26 个字母单词 balloon 只涉及 5 种字符但这 5 种字符在text中出现的次数并不均匀可能还有大量无关字符混在其中。因此最稳妥的预处理方式是一次性统计整个text中每个小写字母的出现次数之后再从频次表中取数而不是对每个目标字符单独扫描一遍字符串那样会退化为 5 次 O(n) 扫描虽然仍可接受但明显更笨拙。仓库实现 题解源码 中的做法正是如此用一个长度固定为 26 的int数组充当哈希表利用t-a把字符映射到下标fre : make([]int, 26) for _, t : range text { fre[t-a] }因为题目约束text只含小写英文字母t-a的结果必然落在[0, 25]不需要做任何越界判断。这一步是本题的 O(n) 核心开销。第二步把频次折算成可拼出的单词数单词 balloon 的字母构成是字母在 balloon 中出现次数频次数组下标b11b-aa10a-al211l-ao214o-an113n-a关键点在于l和o在单词中各出现2 次。也就是说text里每 2 个l才能支撑 1 个 balloon每 2 个o才能支撑 1 个 balloon。因此折算规则是字符b、a、n能拼出的 balloon 数 频次直接取原值字符l、o能拼出的 balloon 数 频次除以 2 向下取整Go 中整数除法天然向下取整。第三步取最小值——木桶原理balloon 是一个完整单词五个字母必须同时齐备才能拼出 1 个。所以最终答案由出现得最稀缺的那个字母决定即五个折算值中的最小值。这正是原题文档所说的取出频次最小的值就是结果。Go 源码逐行解读仓库中 1189. Maximum Number of Balloons.go 的完整实现如下func maxNumberOfBalloons(text string) int { fre : make([]int, 26) for _, t : range text { fre[t-a] } // 字符 b 的频次是数组下标 1 对应的元素值 // 字符 a 的频次是数组下标 0 对应的元素值 // 字符 l 的频次是数组下标 11 对应的元素值这里有 2 个 l所以元素值需要除以 2 // 字符 o 的频次是数组下标 14 对应的元素值这里有 2 个 o所以元素值需要除以 2 // 字符 n 的频次是数组下标 13 对应的元素值 return min(fre[1], min(fre[0], min(fre[11]/2, min(fre[14]/2, fre[13])))) } func min(a int, b int) int { if a b { return b } return a }源码中的注释已经把字母 → 下标 → 是否除以 2的映射关系标注得十分清楚这里再补充几点实现细节下标的由来l-a 108-97 11o-a 111-97 14n-a 110-97 13与注释一一对应嵌套min的结构min一次只比较两个数通过嵌套把 5 个折算值两两归并最终拿到全局最小值。这与顺序遍历取最小等价只是写法更紧凑辅助函数min是题解包内的自实现本仓库的题解代码刻意不依赖标准库或外部包保证每道题目的代码可以独立复制、独立运行从仓库结构看leetcode目录下的题解均为这种自包含风格空字符串边界题目约束text.length 1即便出现更宽松的输入空串时频次表全为 0min结果也会正确返回 0不会越界。测试用例与验证方式仓库为本题配套了表驱动风格的测试文件 1189. Maximum Number of Balloons_test.go其中para1189封装输入参数textans1189封装期望答案覆盖了以下 4 组用例qs : []question1189{ {para1189{nlaebolko}, ans1189{1}}, {para1189{loonbalxballpoon}, ans1189{2}}, {para1189{leetcode}, ans1189{0}}, {para1189{bballoonn}, ans1189{1}}, }其中前三组与题解文档中的官方示例完全一致最后一组bballoonn是仓库额外补充的用例它包含 2 个b、1 个a、2 个l、2 个o、2 个n由于a只有 1 个正确答案是 1——专门用于检验瓶颈字母逻辑避免只测了字母充足的乐观场景。在仓库根目录执行如下命令即可运行本题测试仓库通过 gotest.sh 以-covermodeatomic收集整个leetcode包的全量覆盖率go test ./leetcode/1189.Maximum-Number-of-Balloons/ -v复杂度分析时间复杂度O(n)其中n len(text)。只需一次线性扫描构建频次表随后对 5 个下标做常数次运算不随输入规模增长空间复杂度O(1)。频次表是长度恒为 26 的int数组与输入规模无关。由于题目约束1 n 10^4O(n) 的时间开销在任意语言下都能轻松通过这也是原题文档将其定位为简单题的原因。边界情况与易错点结合源码与用例实际编码时最容易踩的坑有三个忘记l、o需要除以 2这是本题唯一的陷阱。若直接取 5 个字母的原始频次最小值loonbalxballpoon会被误判为 4因为l、o各出现 4 次而正确答案是 2下标计算错误l是下标 11、o是下标 14、n是下标 13不要与字母表顺序的直觉如n在第 14 位混淆建议像源码注释那样把映射写清楚用map[byte]int替代数组虽然可行但需要额外处理键不存在的零值问题定长 26 数组在本题更简洁也完全符合小写字母的约束前提。扩展思考把解法泛化本题的套路可以抽象为一个通用模板给定字符串 S 和目标模板串 T求 S 最多能拼出几个 T。通用做法是统计 S 的字符频次表freS统计 T 的字符频次表freT对 T 中每个字符c计算freS[c] / freT[c]整数除法取所有商的最小值。本题正是该模板的特例模板固定为 balloon且freT中只有l、o为 2其余为 1因此源码直接硬编码了 5 个下标与两处/2省去了第二张频次表换来的是极致的简洁与 O(1) 空间。理解了这一点你就能在面对拼单词类变体题如模板串变化、字符可重复利用等变种时快速写出通用解法。小结核心考点字母频次统计 按单词模板折算 取最小值短板效应仓库实现定长 26 数组一次扫描嵌套min取五个折算值中的最小值源码见 leetcode/1189.Maximum-Number-of-Balloons验证方式仓库测试文件覆盖官方 3 组示例并补充 1 组瓶颈字母用例可运行go test直接验证性能O(n) 时间、O(1) 空间满足10^4的数据规模约束。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考