C#森林中的兔子(力扣题目)

C#森林中的兔子(力扣题目)

题目介绍

森林中有未知数量的兔子。提问其中若干只兔子 “还有多少只兔子与你（指被提问的兔子）颜色相同?” ，将答案收集到一个整数数组 answers 中，其中 answers[i] 是第 i 只兔子的回答。

给你数组 answers ，返回森林中兔子的最少数量。

示例 1：

输入：answers = [1,1,2]
输出：5
解释：
两只回答了 “1” 的兔子可能有相同的颜色，设为红色。
之后回答了 “2” 的兔子不会是红色，否则他们的回答会相互矛盾。
设回答了 “2” 的兔子为蓝色。
此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。
因此森林中兔子的最少数量是 5 只：3 只回答的和 2 只没有回答的。
示例 2：

输入：answers = [10,10,10]
输出：11

提示：

1 <= answers.length <= 1000
0 <= answers[i] < 1000

解题思路

假设一只兔子的回答是x，那么说明和它颜色相同的兔子还有x只。那么总共有x+1只同色的兔子（包括自己）。例如，回答1的话，同色共有2只；回答0的话，只有自己。

但问题在于，不同的兔子可能有相同的颜色，或者不同的颜色。我们需要将这些回答分组，使得每个分组满足条件，同时总兔子数量最少。

那如何将这些回答进行分组呢？比如，如果有多个兔子回答同一个数值，如何确定它们是否属于同一颜色组？

比如，假设两个兔子都回答1。那么可能属于同一颜色组。因为该颜色组共有2只，所以这两个的回答都正确。这时候只需要计算2只。如果有第三个回答1的兔子，那么必须分成两个组。比如前两个是一组，第三个属于另一组，这时候另一组至少需要2只（因为第三只回答1，意味着还有一只没被询问到）。所以这时候总共有2 + 2 =4只。

所以，对于相同数值的回答，我们需要将它们分组，每组的大小是该数值加1。然后将这些组的总和相加，得到总的数量。

那具体来说，假设某个数值为x的出现次数是n次。那么每个这样的组最多可以包含x+1只兔子。如果有n个这样的回答，那么需要的组数是ceil(n/(x+1))。每个组贡献x+1只兔子。所以总共有ceil(n/(x+1)) * (x+1)只。

例如，对于示例1中的回答1出现两次。x=1，所以每个组最多允许2只。出现两次的话，刚好可以组成一个组，贡献2只。另一个回答是2，x=2，每个组需要3只。这里出现一次，所以只能组成一个组，贡献3只。所以总共有2+3=5只。

解决方式

使用字典统计回答次数

这种方式利用字典来统计每个回答出现的次数，然后根据每个回答计算所需的最少兔子数量。

using System;
using System.Collections.Generic;public class Solution {public int NumRabbits(int[] answers) {Dictionary<int, int> countDict = new Dictionary<int, int>();foreach (int ans in answers) {if (countDict.ContainsKey(ans)) {countDict[ans]++;} else {countDict[ans] = 1;}}int total = 0;foreach (var pair in countDict) {int x = pair.Key;int count = pair.Value;int groupSize = x + 1;int groups = (count + groupSize - 1) / groupSize;total += groups * groupSize;}return total;}
}

使用数组统计回答次数

由于题目中取值范围是0到999，我们可以使用固定大小的数组来统计每个回答的出现次数，这种方法在数据范围已知的情况下更为高效。

public class Solution {public int NumRabbits(int[] answers) {int[] counts = new int[1000];foreach (int ans in answers) {counts[ans]++;}int total = 0;for (int x = 0; x < 1000; x++) {int count = counts[x];if (count == 0) continue;int groupSize = x + 1;int groups = (count + groupSize - 1) / groupSize;total += groups * groupSize;}return total;}
}

结合以上字典和数组

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;namespace 森林的兔子
{internal class Program{static void Main(string[] args){Solution counter = new Solution();bool exit = false;while (!exit){Console.WriteLine("请输入兔子的回答（逗号分隔，例如 1,1,2），输入 'exit' 退出：");string input = Console.ReadLine();if (input.ToLower() == "exit"){exit = true;continue;}try{// 解析输入为整数数组int[] answers = ParseInput(input);// 计算结果int resultDict = counter.CalculateWithDictionary(answers);int resultArray = counter.NumRabbits(answers);// 输出Console.WriteLine($"\n输入数据: [{string.Join(",", answers)}]");Console.WriteLine($"字典方法结果: {resultDict}");Console.WriteLine($"数组方法结果: {resultArray}");Console.WriteLine($"结果是否一致: {resultDict == resultArray}\n");}catch (Exception ex){Console.WriteLine($"错误: {ex.Message}\n");}}}// 将输入字符串解析为整数数组static int[] ParseInput(string input){if (string.IsNullOrWhiteSpace(input))throw new ArgumentException("输入不能为空！");string[] parts = input.Split(',');int[] answers = new int[parts.Length];for (int i = 0; i < parts.Length; i++){if (!int.TryParse(parts[i].Trim(), out int num) || num < 0)throw new ArgumentException($"无效输入: '{parts[i]}'，请输入非负整数。");answers[i] = num;}return answers;}}public class Solution{public int NumRabbits(int[] answers){int[] counts = new int[1000];foreach (int ans in answers){counts[ans]++;}int total = 0;for (int x = 0; x < 1000; x++){int count = counts[x];if (count == 0) continue;int groupSize = x + 1;int groups = (count + groupSize - 1) / groupSize;total += groups * groupSize;}return total;}public int CalculateWithDictionary(int[] answers){Dictionary<int, int> countDict = new Dictionary<int, int>();foreach (int ans in answers){if (countDict.ContainsKey(ans)){countDict[ans]++;}else{countDict[ans] = 1;}}int total = 0;foreach (var pair in countDict){int x = pair.Key;int count = pair.Value;int groupSize = x + 1;int groups = (count + groupSize - 1) / groupSize; // 向上取整计算组数total += groups * groupSize;}return total;}}
}

解题思路总结

1. 统计回答次数：统计每个回答数值出现的次数。
2. 计算每组数量：对于每个回答数值x，确定每组最多可容纳的兔子数量为x+1。然后根据该组容量将回答次数分成若干组，确保每组中的兔子数量不超过x+1。
3. 累加总数：每组数量乘以组容量，累加得到所有颜色组的总数，即为森林中兔子的最少数量。