当前位置:网站首页>781. 森林中的兔子
781. 森林中的兔子
2022-08-10 01:34:00 【小卢要刷力扣题】
781. 森林中的兔子
森林中有未知数量的兔子。提问其中若干只兔子 “还有多少只兔子与你(指被提问的兔子)颜色相同?” ,将答案收集到一个整数数组 answers 中,其中 answers[i] 是第 i 只兔子的回答。
给你数组 answers ,返回森林中兔子的最少数量。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/rabbits-in-forest
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
给兔子分组
先排序,让相同的兔子在一起
这样就可以让相同的兔子分组,组内自我消化
排序好了,我们要怎么计算出相同的兔子的数量呢,
我们发现第一种颜色有 4 只兔子的回答为 1
那么在第一种颜色中可以分为 2 只兔子为一组
因为 1 代表这除了自己还有另外一只兔子颜色相同
因此 2 只兔子为一组,因此第一种颜色的兔子有 4 只
到了第 2 种颜色
2 代表着除了自己还有 2 只兔子颜色相同
因此需要分成 3 只兔子为一组
但第二种颜色的兔子在数组中只有 2 只,无法凑齐 3 只
证明还有兔子没被调查,需要在额外补一只兔子,
因此第二种颜色的兔子数量为 3
同理可得,第三种颜色的兔子有 8 只
第四种颜色的兔子有 5 只,因为数组中只有 3 只,需要另外补 2 只,
第五种颜色的兔子有 6 只
计算公式
变量 x 代表有多少只兔子颜色相同
c 代表当前颜色的兔子在数组中有多少只
如果当前数是 x,有 c 只,有几组?
我们以 7 个 3 为例子
3 代表除了自己有 3 只兔子颜色相同
因此 4 只兔子为一组
我们需要分出 2 组
因此为 7/4 向上取整
那么怎么向上取整
原本是 a/b
向上取整变为
(a+(b-1))/b
因此最后公式为((c+x)/(x+1))*(x+1),
🦘代码
class Solution {
public int numRabbits(int[] answers) {
int n=answers.length;
if(answers==null||n==0){
return 0;
}
Arrays.sort(answers);
int x=answers[0];
int c=1;
int ans=0;
for(int i=1;i<n;i++){
if(x!=answers[i]){
ans+=((c+x)/(x+1))*(x+1);
x=answers[i];
c=1;
}else{
c++;
}
}
return ans+((c+x)/(x+1))*(x+1);
}
}
边栏推荐
- 实操|风控模型中常用的这三种预测方法与多分类场景的实现
- OpenCV图像处理学习一,加载显示修改保存图像相关函数
- 使用IDEA的PUSH常见问题
- 2022金九银十工作潮,怎么样才能成功跳槽面试拿到高薪呢?
- 【论文笔记】基于深度学习的机器人抓取虚拟仿真实验教学系统
- RESOURCE_EXHAUSTED: etcdserver: mvcc: database space exceeded
- 2022年8月1日-8月7日(本周10小时,合计1422小时,剩余8578小时)
- 已备案域名用国外服务器会不会掉备案?
- The shell specifies the parameter name to pass the parameter
- 解决sed替换文本,里面含有“/“、“#”等特殊字符的问题
猜你喜欢
OpenCV图像处理学习一,加载显示修改保存图像相关函数
[LeetCode] Find the sum of the numbers from the root node to the leaf node
unity 报错 Unsafe code may only appear if compiling with /unsafe. Enable “Allow ‘unsafe‘ code“ in Pla
【干货】集成学习原理总结
以太网PHY芯片LAN8720A芯片研究
unity编辑器扩展界面使用 List
牛客刷题——剑指offer(第四期)
openpose脚部标注问题梳理
Unity image使用长图后 图片很糊
中文NER的SOTA:RICON
随机推荐
Button countdown reminder
DP 优化方法合集
程序员的专属浪漫——用3D Engine 5分钟实现烟花绽放效果
sql实战积累
Nacos源码分析专题(五)-Nacos小结
基于FTP协议实现文件上传与下载
hint: Updates were rejected because the tip of your current branch is behind hint: its remote counte
墨西哥大众VW Mexico常见的几种label
【UNR #6 C】稳健型选手(分治)(主席树)(二分)
中英文互译在线翻译-在线翻译软件
Unity image使用长图后 图片很糊
[LeetCode] Find the sum of the numbers from the root node to the leaf node
QT中,QTableWidget 使用示例详细说明
跳房子游戏
【SSRF漏洞】实战演示 超详细讲解
浏览器中的history详解
【wpf】拖拽的简单实现
JCMsuite—单模光纤传播模式
idea 删除文件空行
对修饰器的实验支持功能在将来的版本中可能更改。在 “tsconfig“ 或 “jsconfig“ 中设置 “experimentalDecorators“ 选项以删除此警告