LeetCode 781. Rabbits in Forest（森林中的兔子）贪心计数题解：基于 LeetCode-Go 的 Go 实现与证明

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" can't 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 didn't answer into the array. The smallest possible number of rabbits in the forest is therefore 5: 3 that answered plus 2 that didn't. Input: answers = [10, 10, 10] Output: 11 Input: answers = [] Output: 0

注意（Note）：

1. answers的长度至多为1000；
2. 每个answers[i]都是[0, 999]范围内的整数。

题目大意

森林中，每个兔子都有颜色。其中一些兔子（可能是全部）告诉你还有多少其他的兔子和自己有相同的颜色，我们将这些回答放在answers数组里。要求返回森林中兔子的最少数量。

说明：

• answers的长度最大为 1000；
• answers[i]是在[0, 999]范围内的整数。

解题思路：贪心分组 + 哈希计数

核心矛盾：回答相同，未必同色

数组里每个数字代表"这只兔子宣称自己同类的其他数量"。关键难点在于：回答数字相同的兔子不一定属于同一种颜色，而同一种颜色内所有兔子的回答必然一致（因为它们互相是同类，看到的"其他同类数量"都是该颜色总数减一）。

反过来推理可以得到两条硬性约束：

1. 若某只兔子回答x，则它所在的颜色组大小恰好为x + 1（它自己加上x只同类）；
2. 回答同为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 = 5：3 只回答了的 + 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 }

逐行拆解

1. total累计最少兔子总数；m是一个哈希表，m[v]记录当前这一组（回答为v的颜色组）还能再接收多少个回答同为v的兔子名额。
2. 遍历answers中的每个回答v：
   • 若m[v] == 0，说明当前没有未满的组（要么从未出现过，要么上一组已凑满），此时必须新开一组：
     • m[v] += v：新组大小为v + 1，除去当前这只，还能容纳v只同类，因此把剩余名额置为v（此处m[v]恰好为 0，等价于赋值）；
     • total += v + 1：把整组大小计入总数（缺口由没回答的兔子补齐）。
   • 若m[v] > 0，说明当前组还有名额，直接m[v]--消耗一个名额，总数不变。
3. 遍历结束，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]模拟：

结果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.mod，Go 1.19+），可在仓库根目录直接运行：

# 只运行本题的测试 go test -v ./leetcode/0781.Rabbits-in-Forest/ # 运行全部 LeetCode 题解测试 go test ./leetcode/...

仓库还提供了 gotest.sh 脚本，使用-covermode=atomic -coverprofile=coverage.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