题目描述：

LeetCode 781. Rabbits in Forest

In a forest, each rabbit has some color. Some subset of rabbits (possibly all of them) tell you how many other rabbits have the same color as them. Those answers are placed in an array.

Return the minimum number of rabbits that could be in the forest.

Examples:
Input: answers = [1, 1, 2]
Output: 5
Explanation:
The two rabbits that answered "1" could both be the same color, say red.
The rabbit than answered "2" can't be red or the answers would be inconsistent.
Say the rabbit that answered "2" was blue.
Then there should be 2 other blue rabbits in the forest that didn't answer into the array.
The smallest possible number of rabbits in the forest is therefore 5: 3 that answered plus 2 that didn't.

Input: answers = [10, 10, 10]
Output: 11

Input: answers = []
Output: 0

Note:

1. answers will have length at most 1000.
2. Each answers[i] will be an integer in the range [0, 999].

题目大意：

树林中有一些兔子，其中一些兔子告诉你有多少只兔子与它的颜色相同，求树林中最少有多少兔子。

解题思路：

贪心算法（Greedy Algorithm）

字典cntDict[k]表示树林中具有相同颜色的k只兔子的群落，还可以容纳多少只兔子。

遍历answers，记当前兔子的答案为n（其对应群落容量为n + 1）

  若cntDict[n + 1] > 0，则令群落数目 - 1

  否则，令最终结果 += n + 1，并令cntDict[n + 1] = n

Python代码：

class Solution(object):
    def numRabbits(self, answers):
        """
        :type answers: List[int]
        :rtype: int
        """
        ans = 0
        cntDict = collections.defaultdict(int)
        for n in answers:
            if cntDict[n + 1]:
                cntDict[n + 1] -= 1
            else:
                ans += n + 1
                cntDict[n + 1] = n
        return ans

 

本文链接：http://bookshadow.com/weblog/2018/02/16/leetcode-rabbits-in-forest/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码