力扣算法:森林中的兔子
2021/7/14 20:08:19
本文主要是介绍力扣算法:森林中的兔子,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
力扣算法:森林中的兔子
- 一、森林中的兔子
- 1、问题
- 2、思路
- 3、代码
- 4、时间与空间复杂度
- 备注
一、森林中的兔子
1、问题
森林中,每个兔子都有颜色。其中一些兔子(可能是全部)告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在 answers 数组里。
返回森林中兔子的最少数量。
示例1:
输入: answers = [1, 1, 2]
输出: 5
解释: 两只回答了 “1” 的兔子可能有相同的颜色,设为红色。 之后回答了 “2” 的兔子不会是红色,否则他们的回答会相互矛盾。 设回答了 “2” 的兔子为蓝色。 此外,森林中还应有另外 2只蓝色兔子的回答没有包含在数组中。 因此森林中兔子的最少数量是 5: 3 只回答的和 2 只没有回答的。
示例2:
输入: answers = [10, 10, 10]
输出: 11
示例3:
输入: answers = []
输出: 0
说明:
- answers 的长度最大为1000。
- answers[i] 是在 [0, 999] 范围内的整数。
2、思路
如果有 x 只兔子都回答 y,则至少有 ⌈x/(y+1)⌉种不同的颜色,且每种颜色有 y+1 只兔子,因此兔子数至少为⌈x/(y+1)⌉*(y+1)
例如:
如果5出现了8次, 那么至少得 2*(5+1)只兔子;
如果5出现了6次呢? 至少需要6只兔子;
如果5出现了3次呢? 还是6只兔子;
- 我们用哈希表进行统计,当 key 出现了 value 次:
- 如果 value %(key+1) == 0, 需要(value /(key+1))*(key+1)只兔子;
- 如果没有整除, 则至少需要( value /(key+1)+1)* (key+1)只兔子;
向上取整 (value+key) //(key+1)*(key+1)
3、代码
#coding:utf-8 from typing import List import collections class Solution: def numRabbits(self, answers: List[int]) -> int: return sum((k+v)//(k+1)*(k+1) for k,v in collections.Counter(answers).items()) if __name__ == "__main__": # answers = [1, 1, 2] # answers = [10, 10, 10] # answers = [] # answers = [1,0,1,0,0] answers = [0, 0, 1, 1, 1] print(Solution().numRabbits(answers))
4、时间与空间复杂度
时间复杂度:O(n)
n为answers 数组长度
空间复杂度:O(n)
n为哈希表的大小
备注
1、参考:
LeetCode-Solution
https://leetcode-cn.com/problems/rabbits-in-forest/solution/sen-lin-zhong-de-tu-zi-by-leetcode-solut-kvla/
2、Python3 字典 items() 方法:
- Python 字典 items() 方法以列表返回视图对象,是一个可遍历的key/value 对。
- dict.keys()、dict.values() 和 dict.items() 返回的都是视图对象( view objects),提供了字典实体的动态视图,这就意味着字典改变,视图也会跟着变化。
- 视图对象不是列表,不支持索引,可以使用 list() 来转换为列表。
- 我们不能对视图对象进行任何的修改,因为字典的视图对象都是只读的。
#遍历例子 dict = {'Name': 'Runoob', 'Age': 7} for i,j in dict.items(): print(i, ":\t", j) #输出: #Name : Runoob #Age : 7 #将字典的 key 和 value 组成一个新的列表: d={1:"a",2:"b",3:"c"} result=[] for k,v in d.items(): result.append(k) result.append(v) print(result) #输出: #[1, 'a', 2, 'b', 3, 'c']
这篇关于力扣算法:森林中的兔子的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求