781. Rabbits in Forest

发表于 | 分类于 | |

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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:

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

题目大意

每个兔子都有一些颜色， answers 代表兔子告诉你有多少只兔子和自己颜色相同。求总共有多少只兔子。

解题思路

利用字典储存相同颜色兔子的群落，还可以容纳多少只兔子。
若可以容纳兔子大于 0，则群落数 - 1
否则令 ans，重新计算群落数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    func numRabbits(_ answers: [Int]) -> Int {
        var dict = [Int: Int]()
        var ans = 0
        for answer in answers {
            if let v = dict[answer + 1], v > 0 {
                dict[answer + 1] = v - 1
            }else {
                ans += answer + 1
                dict[answer + 1] = answer
            }
        }
        return ans
    }
}
0%