力扣算法:森林中的兔子

力扣算法:森林中的兔子

一、森林中的兔子

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']

上一篇:lnmp项目搭建 wordpress wecenter


下一篇:centos7搭建LNMP环境-编译安装&yum安装-超详细