LeetCode“森林中的兔子”题解：从分组计数到Java代码实现

最近看到一个挺有意思的讨论。有网友提到，他们团队的Leader已经快40岁了，却依然活跃在一线编写核心代码，甚至业余时间还在钻研Go语言源码。

有人问他，难道不担心年龄带来的“优化”风险吗？这位Leader笑着回答，大意是：如果你到了35岁，还只能和25岁的年轻人比拼熬夜加班和敲代码的手速，那确实可能被取代。但如果你能解决那些别人解决不了的关键问题，那么你就是团队不可或缺的宝贝。

这番话点出了一个核心逻辑：随着年龄增长，职场竞争力的焦点应从“体力”转向“不可替代性”。能够处理关键故障、拍板技术方案、串联业务与技术链路，这些才是更稳固的护身符。

这对年轻开发者也是一个提醒：与其过早焦虑所谓的“35岁危机”，不如把精力聚焦在如何系统性提升自己解决复杂问题的能力上。职场本质上评估的是价值，而非年龄。把自己打磨成那个“离开你事情就难办”的角色，比什么都实在。

面试题：森林中的兔子

聊完职场，我们来看一道有趣的LeetCode算法题——“森林中的兔子”。初次看到这个题目，很多人可能会疑惑：这童话般的名字背后，究竟藏着怎样的计数逻辑？

首先，我们得理解清楚场景设定。假设森林里有许多兔子，你随机采访了其中一些。每只兔子只会告诉你一个非负整数 x，这个 x 的含义是：除了它自己之外，还有 x 只兔子和它颜色相同。

注意关键词是“还有”，而不是“总共”。

题目会给你一个数组 answers，记录了这些兔子的回答，例如 [1, 1, 2]。你的任务是：根据这些回答，推断出森林里至少有多少只兔子，才能让所有回答都不矛盾。

我们来拆解一下思路。最简单的情况是回答 0：如果一只兔子说 0，意味着没有其他同色兔子，那么这种颜色就只可能有它1只。所以，每个回答 0 都固定贡献1只兔子到总数里。

难点在于那些回答大于0的情况。比如，有好几只兔子都说 1。每只说 1 的兔子都在暗示：“我这种颜色的兔子总共有2只（我自己 + 1个同伴）”。然而，你无法分辨这些说 1 的兔子是否属于同一种颜色。题目要求的是“最少情况”，所以我们需要按照回答进行分组，来计算数量的下限。

举个例子，对于数组 [1, 1, 1, 1]：
所有兔子都说“还有1只和我同色”。在一个颜色组里，最多能容纳几只说 1 的兔子？答案是 1 + 1 = 2 只。如果超过2只，就必须开启新的颜色组。

这4只说 1 的兔子可以这样分配：

• 前2只属于颜色A（共2只）
• 后2只属于颜色B（共2只）

因此，最少也需要4只兔子。我们可以总结出规律：

对于某个回答值 x，如果这个值出现了 cnt 次，而每组颜色最多能容纳 x + 1 只兔子，那么最少需要的颜色组数就是：groups = ceil(cnt / (x + 1))。

在整数运算中，向上取整 ceil(a / b) 有一个常用技巧：(a + b - 1) / b。

计算出需要多少组后，每一组都代表 x + 1 只同色兔子，因此这部分对总数的贡献就是：groups * (x + 1)。

最后，将所有不同 x 值的贡献相加，就得到了最终答案。

让我们用这个思路来验算经典示例 [1, 1, 2]：

• 对于回答 1：出现次数 cnt = 2，x = 1，组大小 groupSize = 2。
  • 组数 groups = ceil(2 / 2) = 1
  • 这意味着这2只兔子可以属于同一种颜色，该颜色贡献 1 * 2 = 2 只兔子。
• 对于回答 2：出现次数 cnt = 1，x = 2，组大小 groupSize = 3。
  • 组数 groups = ceil(1 / 3) = 1
  • 这意味着虽然只看到1只兔子这么说，但为了满足它的回答（还有2只同色），这种颜色至少要有3只兔子。

所以总数为 2 + 3 = 5，这与LeetCode的示例答案一致。

Java代码实现

思路清晰后，Java代码实现就水到渠成了。主要分为几步：

1. 使用 HashMap 统计每种回答 x 出现的次数。
2. 遍历这个Map，对每一个键值对 (x, cnt) 进行计算。
3. 套用公式 groupSize = x + 1 和 groups = (cnt + groupSize - 1) / groupSize，累加贡献值 groups * groupSize。
4. 返回累加结果。

以下是完整的可运行代码：

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int numRabbits(int[] answers) {
        if (answers == null || answers.length == 0) {
            return 0;
        }

        Map<Integer, Integer> countMap = new HashMap<>();
        for (int ans : answers) {
            countMap.put(ans, countMap.getOrDefault(ans, 0) + 1);
        }

        int res = 0;
        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            int x = entry.getKey();      // 兔子回答的数字
            int cnt = entry.getValue();  // 有多少只兔子给了这个回答

            int groupSize = x + 1;       // 一种颜色最多有几只
            // 需要多少组这种颜色，向上取整
            int groups = (cnt + groupSize - 1) / groupSize;

            res += groups * groupSize;
        }

        return res;
    }

    // 简单测试
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.numRabbits(new int[]{1, 1, 2})); // 输出 5
        System.out.println(s.numRabbits(new int[]{0, 0, 1, 1, 1})); // 可以自己验算一下
    }
}

复杂度分析：

• 时间复杂度 O(n)：需要遍历一遍 answers 数组进行统计，再遍历一遍HashMap的键值对进行计算。
• 空间复杂度 O(n)：HashMap存储了不同回答值的计数。

这道题的核心“坑点”在于，必须把“没被采访到的兔子”也考虑进去。例如，即使只看到一只说 2 的兔子，也必须为它预留出总共3只兔子的位置。只要抓住了“按回答值分组，每组容量为 x+1”这个数学模型，问题就迎刃而解了。

建议大家多构造几个测试用例，手动计算后再用代码验证，这样对解题思路的理解会更加深刻。在云栈社区的算法板块，你也能找到更多类似的题目解析与讨论，帮助你在技术成长和面试求职的道路上走得更稳。