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

【python】Leetcode每日一题-森林中的兔子,第1张

概述【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每日一题-森林中的兔子所遇到的程序开发问题。

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

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/1188001.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-03
下一篇 2022-06-03

发表评论

登录后才能评论

评论列表(0条)

保存