LeetCode每日一题4.20

781.森林中的兔子

问题

问题分析

根据题目描述，我们需要解决的问题是：给定一个数组 answers，其中每个元素表示某只兔子回答的“还有多少只兔子与你颜色相同”，要求返回森林中兔子的最少数目。

思路

理解 answers 数组：
answers[i] = x 表示第 i 只兔子回答说还有 x 只兔子与它的颜色相同。
因此，每种颜色的兔子数量为 x + 1（包括它自己）。
统计每种回答的频率：
使用一个字典来统计每种回答（即 x）出现的次数。
计算每种颜色的兔子数量：
对于每种回答 x，如果其出现次数为 freq，则该颜色的兔子数量为 k * (x + 1)，其中 k 是使得 k * (x + 1) >= freq 的最小整数。
汇总所有颜色的兔子数量：
将每种颜色的兔子数量相加，得到总数。

代码

class Solution:def numRabbits(self, answers: List[int]) -> int:# 统计每种回答的频率count = Counter(answers)total_rabbits = 0for answer, freq in count.items():# 每种颜色的兔子数量为 (answer + 1)rabbits_per_color = answer + 1# 需要的颜色组数color_groups = (freq + rabbits_per_color - 1) // rabbits_per_color# 该颜色的兔子总数total_rabbits += color_groups * rabbits_per_colorreturn total_rabbits

复杂度分析

时间复杂度：O(n)（其中 n 是 answers 的长度）
空间复杂度：O(m)（其中 m 是 answers 中不同元素的数量）

学习

导入必要的模块：
Counter 用于统计 answers 中每个元素的频率。
定义 Solution 类和 numRabbits 方法：
numRabbits 方法接收一个列表 answers 作为参数。
统计每种回答的频率：
使用 Counter(answers) 得到每个回答的频率。
计算总兔子数：
遍历 count 字典，对于每种回答 answer 和其频率 freq：
计算每种颜色的兔子数量 rabbits_per_color = answer + 1。
计算需要的颜色组数 color_groups = (freq + rabbits_per_color - 1) // rabbits_per_color。
累加该颜色的兔子总数 total_rabbits += color_groups * rabbits_per_color。
返回结果：
最终返回 total_rabbits 作为结果。

color_groups = (freq + rabbits_per_color - 1) // rabbits_per_color

这行代码的目的是计算对于特定的 answer（即特定的 rabbits_per_color），需要多少组这样的兔子来覆盖所有的 freq 只兔子。
示例：

示例 1：answers = [1, 1, 2]
answer = 1 时，freq = 2（有两个 1），rabbits_per_color = 2。
color_groups = (2 + 2 - 1) // 2 = 3 // 2 = 1，即需要 1 组 2 只兔子。
answer = 2 时，freq = 1（有一个 2），rabbits_per_color = 3。
color_groups = (1 + 3 - 1) // 3 = 3 // 3 = 1，即需要 1 组 3 只兔子。
示例 2：answers = [10, 10, 10]
answer = 10 时，freq = 3（有三个 10），rabbits_per_color = 11。
color_groups = (3 + 11 - 1) // 11 = 13 // 11 = 1，即需要 1 组 11 只兔子。
4. total_rabbits += color_groups * rabbits_per_color
最后，将每种颜色组的兔子数量累加到 total_rabbits 中，得到最终的兔子总数。