leetcode每日一题 2021/4/4 781. 森林中的兔子

题目

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

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

示例:

输入: answers = [1, 1, 2]

输出: 5

解释:

两只回答了 “1” 的兔子可能有相同的颜色，设为红色。

之后回答了 “2” 的兔子不会是红色，否则他们的回答会相互矛盾。

设回答了 “2” 的兔子为蓝色。

此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。

因此森林中兔子的最少数量是 5: 3 只回答的和 2 只没有回答的。

输入: answers = [10, 10, 10]

输出: 11

输入: answers = []

输出: 0

说明:

answers 的长度最大为1000。

answers[i] 是在 [0, 999] 范围内的整数。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/rabbits-in-forest

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

这是一道经典的数学推理问题，与猜帽子差不多，大致意思就是每只兔子可以看到其他兔子并告诉我们有多少和他相同颜色的兔子，我们要从每只兔子的回答中推算出兔子的最小数量。

我们可以这样想：我们可以先假设看到相同数量的兔子为同一种颜色，以[1, 1, 2]为例，第一只和第二只兔子都是看到了1只和自己相同的兔子，所以我们把他们看成同一种颜色，这样的话我们可以将所有兔子分成两种，一种看到1和一种看到2，看到1的加上本身所以总共有2只，看到2的加上自己本身所以总共有3只，2+3就得出所有兔子应该为5.

再来一组验证[10,10,10]

按照上面的思路再来一次，看到10的有三只，看为一组，数量应该为10加上自己本身所以是11，所以答案是11，这个答案是对的，所以我们就可以直接将看到相同数量的兔子放在一组，然后通过组数来得出答案了吗？

我们再来试试[2,2,2,2]

这里最少应该有多少只兔子？按照上面的思路来的话，应该把看到2的看成同一组，因此数量应该为2+1 = 3，但是数量真的是三只吗？很明显不是，正确的答案应该是6才对，应该有两只，每组三只。这又是怎么得来的呢？其实思路还是和上面一样，只是我们要再将每一组的数量考虑进去，看到数量为2的兔子所在一组的最多数量应该是多少？没错，加上本身应该只要3只，所以我们不能直接将看到相同数量的就并为一组，在有一组的数量达到最大时，就应该另起一组。

因此我们可以得出兔子的组数计算公式：看到相同数量的兔子总数/(看到的数量+1)

兔子的数量即为：每组兔子的数量之和 + 组数

代码

javascript

var numRabbits = function(answers) {
    let m = {},
        res = 0;
    for(let i = 0; i < answers.length; i++){
        m[answers[i]] == undefined ? m[answers[i]] = 1 : m[answers[i]] ++; 
    }
    for(let key in m){
        let f = Math.ceil(m[key] / (parseInt(key) + 1));
        res += f + parseInt(key) * f;
    }
    return res;
};

python

class Solution:
    def numRabbits(self, answers: List[int]) -> int:
        d = dict()
        for i in answers:
            if i in d:
                d[i] = d[i] + 1
            else:
                d[i] = 1
        res = 0
        for key in d:
            f = math.ceil(d[key] / (key + 1))
            res += (key + 1) * f
        return res