LeetCode 781. Rabbits in Forest森林中的兔子贪心计数题解基于 LeetCode-Go 的 Go 实现与证明【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文以 LeetCode 第 781 题「森林中的兔子」Rabbits in Forest为题解主体结合 LeetCode-Go 仓库中该题目的真实源码与测试用例讲解如何利用按回答数字分组 哈希计数的贪心策略在 O(n) 时间内计算出森林中兔子的最小可能总数。读完本文你将掌握这一类分组凑整计数问题的通用解法并能直接运行仓库内自带的测试用例验证结果。题目描述原题面在一片森林中每只兔子都有某种颜色。其中一部分兔子可能是全部会告诉你与它颜色相同的其他兔子还有多少只。这些回答被存放在一个数组answers中。请返回森林中可能存在的兔子的最少数量。Examples: Input: answers [1, 1, 2] Output: 5 Explanation: The two rabbits that answered 1 could both be the same color, say red. The rabbit than answered 2 cant be red or the answers would be inconsistent. Say the rabbit that answered 2 was blue. Then there should be 2 other blue rabbits in the forest that didnt answer into the array. The smallest possible number of rabbits in the forest is therefore 5: 3 that answered plus 2 that didnt. Input: answers [10, 10, 10] Output: 11 Input: answers [] Output: 0注意Noteanswers的长度至多为1000每个answers[i]都是[0, 999]范围内的整数。题目大意森林中每个兔子都有颜色。其中一些兔子可能是全部告诉你还有多少其他的兔子和自己有相同的颜色我们将这些回答放在answers数组里。要求返回森林中兔子的最少数量。说明answers的长度最大为 1000answers[i]是在[0, 999]范围内的整数。解题思路贪心分组 哈希计数核心矛盾回答相同未必同色数组里每个数字代表这只兔子宣称自己同类的其他数量。关键难点在于回答数字相同的兔子不一定属于同一种颜色而同一种颜色内所有兔子的回答必然一致因为它们互相是同类看到的其他同类数量都是该颜色总数减一。反过来推理可以得到两条硬性约束若某只兔子回答x则它所在的颜色组大小恰好为x 1它自己加上x只同类回答同为x的兔子最多只能凑满一组x 1只超出部分必须另起一组同色。因此要使总数最小就应当尽量让回答相同的兔子挤进同一组每x 1只回答为x的兔子构成一个完整颜色组贡献x 1只兔子若不足x 1只则整组仍按x 1只计缺口部分视为没有回答的同类兔子。这正是原文档在 README.md 解题思路中强调的划分方式例如[2,2,2,2,2,2]中每 3 只回答2的兔子凑一组因此是3 个种类颜色总共 6 只兔子。用 map 去重相同种类的兔子不断递减剩余名额当某组名额耗尽后仍有同类回答出现就把它当作另外一个种类的兔子来看待。反例直觉为什么[1, 1, 2]的答案是 5两只回答1的兔子可以同色红色组大小 2组内名额正好用尽回答2的兔子不能是红色否则红色组会变成 3 只与只有两只回答 1矛盾所以它属于蓝色组大小 3蓝色组里另外 2 只兔子没有出现在answers中于是最少总数为2 3 53 只回答了的 2 只没回答的。源码实现LeetCode-Go 中的 numRabbits仓库中本题的完整实现位于 781. Rabbits in Forest.go代码如下package leetcode func numRabbits(ans []int) int { total, m : 0, make(map[int]int) for _, v : range ans { if m[v] 0 { m[v] v total v 1 } else { m[v]-- } } return total }逐行拆解total累计最少兔子总数m是一个哈希表m[v]记录当前这一组回答为v的颜色组还能再接收多少个回答同为v的兔子名额。遍历answers中的每个回答v若m[v] 0说明当前没有未满的组要么从未出现过要么上一组已凑满此时必须新开一组m[v] v新组大小为v 1除去当前这只还能容纳v只同类因此把剩余名额置为v此处m[v]恰好为 0等价于赋值total v 1把整组大小计入总数缺口由没回答的兔子补齐。若m[v] 0说明当前组还有名额直接m[v]--消耗一个名额总数不变。遍历结束total即为最小兔子数。关键代码点m[v] v与m[v] v在m[v] 0的分支中等价源码采用写法名额耗尽m[v]归零后再遇到相同回答就会触发新开一组分支天然实现了原文所述的当有种类的兔子为 0 以后还有该种类的兔子报数需要当做另外一个种类的兔子来看待。复杂度分析时间复杂度O(n)其中n len(answers)只需一次线性遍历哈希表读写均为均摊 O(1)空间复杂度O(n)严格说是 O(min(n, 1000))map最多记录不同回答值而取值范围被限制在[0, 999]所以实际最多 1000 个键。该实现满足题目answers长度 ≤ 1000 的约束即便在更宽松的数据规模下也能线性完成。边界情况与示例验证空数组answers []时循环体不执行total 0即森林中可能一只兔子都没有输出0。回答为 0 的兔子v 0表示没有其他兔子与我同色即每只回答0的兔子都是独立的颜色组。由于m[0] 0后m[0]仍为 0后续每个0都会触发新开组total恰好等于0的个数逻辑自洽。六个 2 的情况对[2, 2, 2, 2, 2, 2]模拟处理顺序vm[2] 操作total120→2开组3222→13321→03420→2开组6522→16621→06结果6与文档中3 个种类总共 6 只兔子的分析完全吻合。官方三个示例仓库测试文件 781. Rabbits in Forest_test.go 中给出了与题面一致的三个用例qs : []question781{ {para781{[]int{1, 1, 2}}, ans781{5}}, {para781{[]int{10, 10, 10}}, ans781{11}}, {para781{[]int{}}, ans781{0}}, }分别对应输出5、11、0与题目给出的 Expected 输出完全一致。如何运行测试该仓库为 Go module 项目见 go.modGo 1.19可在仓库根目录直接运行# 只运行本题的测试 go test -v ./leetcode/0781.Rabbits-in-Forest/ # 运行全部 LeetCode 题解测试 go test ./leetcode/...仓库还提供了 gotest.sh 脚本使用-covermodeatomic -coverprofilecoverage.txt ./leetcode/...一次性对全部包收集覆盖率并输出coverage.txt仓库根目录下已存在该文件可用于整体验证各题实现的正确性与覆盖率表现bash gotest.sh小结「森林中的兔子」是一道典型的分组凑整贪心计数题核心不是模拟兔子的颜色而是利用回答x的兔子必然属于大小x 1的组这一约束通过哈希表记录每组剩余名额把相同回答尽量凑满一组超出即另起一组从而得到全局最小总数。LeetCode-Go 中的numRabbits用 14 行代码完成了这一策略配合 781. Rabbits in Forest_test.go 中的用例即可快速验证。掌握这一思路后类似的最小分组数按计数凑整类问题如合并同值元素、按频率分组等都可以复用哈希计数 名额递减 满组重开的框架。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考