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

简介: 森林中有未知数量的兔子。提问其中若干只兔子 "还有多少只兔子与你(指被提问的兔子)颜色相同?" ,将答案收集到一个整数数组 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
}


相关文章
|
2月前
|
算法 数据挖掘
R语言——AVOCADO“(异常植被变化检测)算法(1990-2015数据分析)监测森林干扰和再生(含GEE影像下载代码)
R语言——AVOCADO“(异常植被变化检测)算法(1990-2015数据分析)监测森林干扰和再生(含GEE影像下载代码)
62 1
|
2月前
|
算法 JavaScript
js经典算法题,鸡兔同笼问题,鸡兔共35只,共94只脚,问鸡和兔子一共有多少只?(详细解答)
js经典算法题,鸡兔同笼问题,鸡兔共35只,共94只脚,问鸡和兔子一共有多少只?(详细解答)
109 0
|
9月前
|
算法
趣味算法-神奇的兔子数列
趣味算法-神奇的兔子数列
|
机器学习/深度学习 算法 决策智能
方程就是二叉树森林?遗传算法从数据中直接发现未知控制方程和物理机理
方程就是二叉树森林?遗传算法从数据中直接发现未知控制方程和物理机理
|
算法 C语言
05【C语言 & 趣味算法】经典:兔子产子问题(即:Fibonacci数列)
05【C语言 & 趣味算法】经典:兔子产子问题(即:Fibonacci数列)
05【C语言 & 趣味算法】经典:兔子产子问题(即:Fibonacci数列)
|
存储 算法
【数据结构与算法分析】0基础带你学数据结构与算法分析10--树和森林
其实作为树的最后一点内容并没有多少,主要探讨树、森林、二叉树的关系,以及在严蔚敏老师的数据结构中提到的其他有关树的一些实现方式。
95 1
【数据结构与算法分析】0基础带你学数据结构与算法分析10--树和森林
|
存储 算法
【数据结构和算法】树与森林&树与二叉树的转换
【数据结构和算法】树与森林&树与二叉树的转换
119 0
【数据结构和算法】树与森林&树与二叉树的转换
|
存储 算法 Java
算法系统学习-兔子生兔子(迭代算法-正推法)
该系列是基于有一定语言基础(C,C++,Java等等)和基本的数据结构基础进行的算法学习专栏,如果觉得有点吃力 😥 ,建议先了解前提知识再学习喔!本个专栏会将用更容易理解的表达去学习算法,如果在一些表述上存在问题还请各位多多指点
293 0
|
算法
Java_斐波那契数列_兔子生兔子算法
斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368…… 特别指出:第0项是0,第1项是第一个1。 这个数列从第三项开始,每一项都等于前两项之和。
121 0
Java_斐波那契数列_兔子生兔子算法
[leetcode/lintcode 题解] 阿里算法面试真题:森林中的兔子
[leetcode/lintcode 题解] 阿里算法面试真题:森林中的兔子
[leetcode/lintcode 题解] 阿里算法面试真题:森林中的兔子