Java实现 LeetCode 781 森林中的兔子（分析题）

781. 森林中的兔子 森林中，每个兔子都有颜色。其中一些兔子（可能是全部）告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在 answers 数组里。 返回森林中兔子的最少数量。 示例: 输入: answers = [1, 1, 2] 输出: 5 解释: 两只回答了 “1” 的兔子可能有相同的颜色，设为红色。 之后回答了 “2” 的兔子不会是红色，否则他们的回答会相互矛盾。 设回答了 “2” 的兔子为蓝色。 此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。 因此森林中兔子的最少数量是 5: 3 只回答的和 2 只没有回答的。 输入: answers = [10, 1 在LeetCode的第781题“森林中的兔子”中，问题的核心是根据兔子们给出的答案来推断森林中兔子的最少数量。每个答案代表一只兔子报告的与其颜色相同的其他兔子的数量。我们要找出一个最小的兔子总数，使得所有的报告都得到合理的解释。 我们来看一个例子。输入为answers = [1, 1, 2]，这意味着有两只兔子报告了它们各自的颜色相同，还有一只兔子报告说有两只有相同颜色。根据题目，如果两只报告1的兔子颜色相同，那么总共就有3只这种颜色的兔子（包括报告的两只）。但是，报告2的兔子不能是红色，否则它的答案将与已知的红色兔子数量矛盾。所以，报告2的兔子应该是另一种颜色，且至少还有1只同色兔子未报告。因此，总兔子数至少为5：3只红色（已报告的2只加上未报告的1只）和2只蓝色（报告2的兔子加上未报告的1只）。 对于输入answers = [10, 10, 10]，每只兔子都报告有10只相同颜色的兔子。假设它们颜色不同，那么至少有3种颜色的兔子，每种颜色至少有10只。然而，这会导致每种颜色的兔子总数超过1000，这是不可能的，因为答案的范围是[0, 999]。因此，这3只兔子应该具有相同的颜色，加上未报告的兔子，总数至少为11。 再来考虑空输入answers = []的情况，显然，没有兔子报告，所以森林中至少有0只兔子。 为了实现这个解法，我们可以使用哈希映射（HashMap）来存储每种颜色兔子的数量。遍历answers数组，对于每个答案answer： 1. 如果哈希表中已经有answer这个键，并且对应的值大于0，这意味着我们已经遇到了相同颜色的兔子。这时，我们只需将该键的值减1，表示这只新遇到的兔子与之前的一起计入总数。 2. 如果哈希表中没有answer这个键，或者对应的值为0，我们需要将answer+1作为新的兔子数量，并将其放入哈希表中。这是因为兔子报告的answer表示还有answer只相同颜色的兔子，包括它自己。 返回哈希表中所有值之和，即为最少的兔子总数。这种方法确保了每种颜色的兔子数量都是完整的，不会出现部分数量的情况，从而满足题目要求。 Java代码如下： ```java class Solution { public int numRabbits(int[] answers) { Map<Integer, Integer> map = new HashMap<>(); int num = 0; for (int answer : answers) { if (map.containsKey(answer) && map.get(answer) > 0) { map.put(answer, map.get(answer) - 1); } else { num += answer + 1; map.put(answer, answer); } } return num; } } ``` 这段代码简洁地实现了问题的解决方案，通过哈希映射有效地处理了不同颜色兔子的数量，确保了返回的兔子总数是最小的。