【LeetCode】781. 森林中的兔子
很久没有做 LeetCode 了，感觉自己笔试也不咋地就是因为最近看的都是知识点，算法题做的太少了，而且没有使用 Java 写都是用C++ 写手撕代码就有些尴尬。
【LeetCode】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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
知识点
- 哈希表
- 数组
C++ 自写答案
题目给的范围是固定的 我就用数组存起来了 用哈希表的思想进行计数 比如 1出现 了2次 就刚好 说明 2个是一对 如果 3出现4次 刚好4%（3+1）==0；
3 出现 7次 7%(3+1）== 3 不够两对 就 进位 补齐两对
class Solution {
public:
int nums[1001];
int numRabbits(vector<int>& answers) {
for(int i=0;i<answers.size();i++){
nums[answers[i]+1]++;
}
int ans= 0;
for(int i=1;i<=1000;i++){
if(nums[i]>0){
int flag=1;
if(nums[i]%i==0){
flag=0;
}
ans+=(nums[i]/i+flag)*i;
}
}
return ans;
}
};
官方解答 Java版
描述的 学术些
class Solution {
public int numRabbits(int[] answers) {
Map<Integer, Integer> count = new HashMap<Integer, Integer>();
for (int y : answers) {
count.put(y, count.getOrDefault(y, 0) + 1);
}
int ans = 0;
for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
int y = entry.getKey(), x = entry.getValue();
ans += (x + y) / (y + 1) * (y + 1);
}
return ans;
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/rabbits-in-forest/solution/sen-lin-zhong-de-tu-zi-by-leetcode-solut-kvla/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。笔记
官方的答案
ans += (x + y) / (y + 1) * (y + 1);就可以 替换我的
int flag=1;
if(nums[i]%i==0){
flag=0;
}
ans+=(nums[i]/i+flag)*i;进位的小技巧 (x+y-1)/y 其实以前就会 但是很久不做题 都忘得很干净了 所以还是要坚持 刷题 多总结 多做题总不会错的。
腾讯云开发者
