【python】Leetcode每日一题-森林中的兔子

概述【python】Leetcode每日一题-森林中的兔子【题目描述】森林中，每个兔子都有颜色。其中一些兔子（可能是全部）告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在answers数组里。返回森林中兔子的最少数量。示例1：示例:输入:answers=[1,1,2]输出:5解释: 【python】Leetcode每日一题-森林中的兔子【题目描述】

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

返回森林中兔子的最少数量。

示例1：

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

说明：

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

---

【分析】

思路

解决办法就是 对于[n，n，n，···，n]，记 num=len([···]),则存在关系

\[least(num)=\begin{cases} n+1, & num\leq n+1\\ ceil(num/(n+1))*(n+1), & num = n+1 \end{cases}\]

即对于报相同数目的兔子序列，其具有相同颜色的兔子的最大数量为n+1。

由此，思路就是将原数组进行排序，然后扫一遍，对报相同数目兔子求least，最后求总和。

AC代码

class Solution:    def numRabbits(self, answers) -> int:        if answers == []:            return 0        least = 0        answers.sort()        i = 0        while i < len(answers):            p = answers[i]            if p == 0:                least += 1                i += 1                continue            num = 1            for j in range(i+1, len(answers)):                if answers[j] == p:                    num += 1                else:                    i = j                    break            else:                i = len(answers)            least += (math.ceil(num / (p+1))) * (p+1)        return least

看过题解之后，自己的思路的核心思想是贪心，同时不需要排序再遍历，可以利用哈希表统计各元素出现次数。 总结

以上是内存溢出为你收集整理的【python】Leetcode每日一题-森林中的兔子全部内容，希望文章能够帮你解决【python】Leetcode每日一题-森林中的兔子所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。