【leetcode刷题】T213-森林中的兔子
- 2019 年 12 月 23 日
- 筆記
木又连续日更第91天（91/100）
木又的第213篇leetcode解题报告
数学类型第29篇解题报告
leetcode第781题：森林中的兔子
https://leetcode-cn.com/problems/rabbits-in-forest/
【题目】
森林中，每个兔子都有颜色。其中一些兔子（可能是全部）告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在 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] 范围内的整数。
【思路】
我最开始的理解是，对数组直接取set，求set的和再加上set的长度。
但是有问题，一是0怎么处理；二是如果回答该数的兔子超过了该数，肯定不止一种颜色，比如有三个兔子回答1，那么至少存在两种颜色。
其实，解决了这两个问题，这道题也就解决了。
我们用res来存储结果，主要步骤是：先用字典统计每个数字的个数，然后遍历字典（键值为k，值为v），如果k==0，则res += v；如果v <= k，则res += k+1；否则，res += special。
计算special的过程有个点需要注意，因为v/(k+1)是浮点数，有可能是2.99999999，也有可能是3.00000001，不能简单的用floor或者round或者ceil。可以直接判断v % (k+1)是否为0，是则再处理。
说的有点啰嗦，show me the code。
【代码】
python版本
class Solution(object): def numRabbits(self, answers): """ :type answers: List[int] :rtype: int """ if len(answers) == 0: return 0 d = {} for a in answers: d[a] = d.get(a, 0) + 1 res = 0 for k, v in d.items(): print(k, v) if k == 0: res += v elif v <= k: res += (k + 1) else: res += v // (k + 1) * (k + 1) if v % (k + 1) != 0: res += k + 1 return res
C++版本
class Solution { public: int numRabbits(vector<int>& answers) { if(answers.size() == 0) return 0; int res = 0; // 统计个数 map<int, int> d; for(int i=0; i<answers.size(); i++) d[answers[i]]++; // 得到结果 int k = 0, v = 0; for(map<int, int>::iterator it=d.begin(); it!=d.end(); it++){ k = it->first; v = it->second; if(k == 0) res += v; else{ if(v <= k) res += (k + 1); else{ res += v / (k+1) * (k+1); if(v % (k+1) != 0) res += (k+1); } } } return res; } };
