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