日拱算法,森林中的兔子问题

简介: 森林中有未知数量的兔子。提问其中若干只兔子 "还有多少只兔子与你(指被提问的兔子)颜色相同?" ,将答案收集到一个整数数组 answers 中,其中 answers[i] 是第 i 只兔子的回答。

image.png

题目:


森林中有未知数量的兔子。提问其中若干只兔子 "还有多少只兔子与你(指被提问的兔子)颜色相同?" ,将答案收集到一个整数数组 answers 中,其中 answers[i] 是第 i 只兔子的回答。

给你数组 answers ,返回森林中兔子的最少数量。


示例 1:
输入:answers = [1,1,2]
输出:5
解释:
两只回答了 "1" 的兔子可能有相同的颜色,设为红色。 
之后回答了 "2" 的兔子不会是红色,否则他们的回答会相互矛盾。
设回答了 "2" 的兔子为蓝色。 
此外,森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。 
因此森林中兔子的最少数量是 5 只:3 只回答的和 2 只没有回答的。
示例 2:
输入:answers = [10,10,10]
输出:11


题目来源:森林中的兔子


题解:



这题目有点脑筋急转弯的意思,聪明的兔兔就是不会正常说话 QAQ

首先同颜色的兔子所报的数字一定是相同的,且因为包括自己,数量为answers[i] + 1,比如 [2,2],实际上是有 3 只兔子。


其次,我们可以假设总共有n只兔子都回答x,就把x + 1分为一组,看n里面有多少个x + 1, 剩下的(n % (x + 1)) 分为部分回答的兔子,它们的总数也是x + 1;


怎么理解?延续上面最简单的例子,总共有 4 只兔子,每个都回答为 2 ,就把 2+1 = 3 看成一组,剩下的就是只有部分兔子在回答的,也就是 4 - 3 = 1,那唯一的兔子只是一只“部分兔子”,它也说 2 ,说明除它之外,还有 2 只兔子,算上它,也是 2+1 = 3 只兔子。


所以在算法中分两种情况:1. 刚好分组能分完的;2. 不能分完的再取余,再合并再加,即得解。


JavaScript 实现:

var numRabbits = function(answers) {
  let map = new Map(), ans = 0
  //统计每个回答出现的次数
  for (let ans of answers) {
    map.set(ans, map.has(ans) ? map.get(ans) + 1 : 1)
  }
  //1. 如果整除说明刚好可以构成多个(a,a+1)这样的回答
  //2. 如果不整除则必多一种颜色,所以向上取整
  for (let e of map.entries()) {
    ans += (Math.ceil(e[1] / (e[0] + 1))) * (e[0] + 1)
  }
  return ans
}


相关文章
|
7月前
|
机器学习/深度学习 算法 Python
请解释Python中的随机森林算法以及如何使用Sklearn库实现它。
【2月更文挑战第28天】【2月更文挑战第101篇】请解释Python中的随机森林算法以及如何使用Sklearn库实现它。
71 3
|
7月前
|
机器学习/深度学习 算法
大模型开发:解释随机森林算法以及它是如何做出决策的。
随机森林是集成学习方法,利用多棵决策树提升性能。通过随机抽样和特征选择创建弱分类器,减少模型相关性。每个决策树基于子数据集和特征子集构建,预测时集成所有决策树结果,分类问题采用投票,回归问题取平均值。这种方法降低过拟合风险,提高准确性和稳定性,对噪声和异常值容忍度高,广泛应用。
101 0
|
7月前
|
机器学习/深度学习 算法
随机森林算法是如何通过构建多个决策树并将它们的预测结果进行投票来做出最终的预测的?
【2月更文挑战第28天】【2月更文挑战第102篇】随机森林算法是如何通过构建多个决策树并将它们的预测结果进行投票来做出最终的预测的?
127 1
|
4月前
|
数据采集 机器学习/深度学习 数据可视化
【优秀python web系统毕设】基于python的全国招聘数据分析可视化系统,包括随机森林算法
本文介绍了一个基于Python的全国招聘数据分析可视化系统,该系统利用数据挖掘技术、随机森林算法和数据可视化技术,从招聘网站抓取数据,进行处理、分析和预测,帮助用户洞察招聘市场,为求职者和企业提供决策支持。
208 2
|
26天前
|
机器学习/深度学习 算法 Python
随机森林算法是一种强大的集成学习方法,通过构建多个决策树并综合其结果进行预测。
随机森林算法是一种强大的集成学习方法,通过构建多个决策树并综合其结果进行预测。本文详细介绍了随机森林的工作原理、性能优势、影响因素及调优方法,并提供了Python实现示例。适用于分类、回归及特征选择等多种应用场景。
53 7
|
4月前
|
存储 算法
读《趣学算法》:重开算法之门,神奇的兔子数列(斐波那契数列)
本文通过《趣学算法》中的斐波那契数列问题,探讨了算法的递归实现、时间复杂度分析,并展示了如何通过迭代和优化存储空间来改进算法,最终将时间复杂度从指数级降低到线性级,并将空间复杂度从线性级降低到常数级。
97 0
读《趣学算法》:重开算法之门,神奇的兔子数列(斐波那契数列)
|
7月前
|
算法 数据挖掘
R语言——AVOCADO“(异常植被变化检测)算法(1990-2015数据分析)监测森林干扰和再生(含GEE影像下载代码)
R语言——AVOCADO“(异常植被变化检测)算法(1990-2015数据分析)监测森林干扰和再生(含GEE影像下载代码)
112 1
|
4月前
|
机器学习/深度学习 数据采集 算法
随机森林算法应用
8月更文挑战第20天
|
4月前
|
机器学习/深度学习 数据采集 算法
基于SVm和随机森林算法模型的中国黄金价格预测分析与研究
本文通过运用支持向量机(SVM)、决策树和随机森林算法,结合历史黄金价格数据和特征工程,建立了中国黄金价格的预测模型,并通过模型训练、评估及可视化分析,为黄金市场投资者和分析师提供了基于机器学习算法的预测方法和决策支持。
165 0
|
6月前
|
机器学习/深度学习 数据采集 存储
算法金 | 决策树、随机森林、bagging、boosting、Adaboost、GBDT、XGBoost 算法大全
**摘要:** 这篇文章介绍了决策树作为一种机器学习算法,用于分类和回归问题,通过一系列特征测试将复杂决策过程简化。文章详细阐述了决策树的定义、构建方法、剪枝优化技术,以及优缺点。接着,文章讨论了集成学习,包括Bagging、Boosting和随机森林等方法,解释了它们的工作原理、优缺点以及如何通过结合多个模型提高性能和泛化能力。文中特别提到了随机森林和GBDT(XGBoost)作为集成方法的实例,强调了它们在处理复杂数据和防止过拟合方面的优势。最后,文章提供了选择集成学习算法的指南,考虑了数据特性、模型性能、计算资源和过拟合风险等因素。
84 0
算法金 | 决策树、随机森林、bagging、boosting、Adaboost、GBDT、XGBoost 算法大全