LeetCode 781. Rabbits in Forest

用户头像
liu_liu
关注
发布于: 2020 年 05 月 16 日
LeetCode 781. Rabbits in Forest

@(LeetCode)

问题描述



在一个森林里,每只兔子有着某种颜色。部分兔子(也可能是全部)会告诉你额外还有多少只与其颜色一样的兔子。这些答案放在数组中。



返回森林中可能存在的最少数量的兔子。



栗 1:

输入:answers = [1, 1, 2]
输出:5

解释:
第一只兔子说额外有 1 只兔子和其颜色一样,假设颜色记为 red,那么 red 总数为 2,因为是除它之外还有 1 只兔子。
第二只兔子说额外有 1 只兔子和其颜色一样,那么它也可以是 red,这样满足前两只兔子的说法。
第三只兔子说额外有 2 只兔子和其颜色一样,但它不可能为 red。
如果为 red,red 的兔子就有 3 个,那么第一/二只兔子的说法就不正确,因此它只能是另外的颜色,且该颜色的兔子有 3 只。

因此,总数为 3 + 2 = 5。



栗 2:

输入:answers = [10, 10, 10]
输出:11

解释:
第一只兔子说额外有 10 只兔子与其颜色一样,假设颜色为 red,那么 red 的兔子数有 11 只。
第二只兔子也说有 10 只兔子与其颜色一样,那么它也可以是 red,因为 red 还剩 10 个空位。这样它占一个后,还剩 9 个。
第三只兔子也说有 10 只兔子与其颜色一样,那么它也可以是 red,因为还有 9 个空位,它可以占一个。

因此,总数为 11。



栗 3:

输入:answers = []
输出:0



注意:

  1. answers 最大长度为 1000

  2. 每个答案 answer[i] 都是整数,且范围在 [0, 999]



想看英文原文的戳这里



解题思路



解这道题最主要是想清楚在什么条件下,会让兔子数量最少。



我们先来看几个栗子。



栗子分析

栗 1

举个简单的栗子,比如 answers = [1, 1]



  • 第一只兔子说与其颜色相同的有 1 只,假设颜色为 A,那么 A 色的总共有 2 只兔子。

  • 第二只兔子说与其颜色相同的有 1 只,假设颜色为 B,那么 B 色的总共有 2 只兔子。



试想一下:

  • 如果 AB 不同,那么总共有 2 + 2 = 4 只兔子。

  • 如果 AB 相同,那么总共有 2 只兔子。

因此,从上可以看出,要想让兔子数量最小,就要尽量让兔子同色,同时也要满足兔子所说的同色个数。



栗 2



另外再举个栗子,比如 answers = [1, 1, 1]



前两只兔子的分析同栗 1,假设颜色均为 A,且有 2 只。

第三只兔子说与其颜色相同的兔子有 1 只,那么它可能为 A 色吗?

答案是不可能,因为如果为 A,则三只兔子同色,与它们所说的数量不同。所以它只能是另外的颜色,且有 2 只。



因此,最少兔子数量为 2 + 2 = 4

栗 3

再看个稍微复杂些的例子,比如 answers = [5, 2, 2, 0, 2, 2, 2]。分析过程如下:



  • 第一只兔子说有 5 只与其同色,假设颜色为 A,那么 A 色共有 6 只兔子。

  • 第二只兔子说有 2 只与其同色。



虽然我们上面说过,要让兔子尽可能同色,但它可能与 A 同色吗?



很显然不能。如果同色,就不满足兔 1 说的条件,互相矛盾。所以兔 2 是另外的颜色,记为 B,总数为 3B 的剩余坑位为 2



  • 第三只兔子说有 2 只与其同色,而跟它口径一致的是兔 2,那么他们可能同色吗?可能,因为 B 的剩余坑位数还有 2。它占了一个后,B 的剩余坑位为 1

  • 第四只兔子说没有与其同色的,那么它只能是单独的颜色,总数为 1

  • 第五只兔子说有 2 只兔子同色,而跟它口径一致的是兔 3,它的颜色是 B,坑位还有 1 个,因此兔 5 可以是 B。此时,B 的剩余坑位为 0

  • 第六只兔子说有 2 只兔子同色,跟它口径一致的是兔 3,而颜色 B 的坑位已经被占完。因此,它只能是其他的颜色,记为 C,总数为 3C 的剩余坑位为 2

  • 第七只兔子说有 2 只兔子同色,虽然跟它口径一致的是兔 36,但兔 3 的颜色 B 坑位已经被占完,所以只能占 C 的坑位。



因此,最少兔子数量为 6 + 3 + 1 + 3 = 13

从上面几个栗子,我们可以总结出如下结论:

  1. 尽量让兔子同色,这样才能让数量最少。

  2. 只有答案数量相同的兔子才可能为同色,否则说法矛盾。

  3. 当同色的坑被占完后,同样答案的兔子就不能是同色了,只能新起颜色。

  4. 每次新起颜色,兔子总数需要加上 answer + 1



初始解法



我最初的解法想的有些复杂:动态地给兔子分配颜色,颜色值为从 1 开始不断递增,并记录该颜色对应的总个数(等于 answer + 1)和剩余坑位数(也就等于 answer)。



在处理某只兔子的 answer 时,从 颜色 1 开始逐个遍历已分配的颜色,如果颜色对应的总个数与 answer + 1 相等,即它们的答案相同,则说明可以是同色。

  • 当剩余坑位足够,则坑位数减 1

  • 当剩余坑位不足,则分配新的颜色。



最终计算所有出颜色所对应的兔子总数之和。



数据结构如下所示,兔子总数为累加 totalCount 的值。



{
1 => { totalCount: 6, remainCount: 5 },
2 => { totalCount: 3, remainCount: 0 },
3 => { totalCount: 3, remainCount: 1 }
}



但这种解法的效率不高,因为每次都需要去遍历已分配的颜色。提交后运行速度只超过了 12%js 代码。



关键代码如下:

answers.forEach((answer) => {
if (answer === 0) {
sum += 1
} else {
// 在 map 中查找是否有某个颜色对应的数量相同的兔子,若有,则表示其为同一个颜色,若无,则表示为其他颜色的兔子
let found = false
// 从颜色 1 开始遍历
let i = 1
while (i <= index) {
// 有对应颜色
if (colorMap.has(i)) {
let value = colorMap.get(i)
let {totalCount, remainCount} = value
// 还有剩余坑位数,可以同色
if (totalCount === answer + 1 && remainCount > 0) {
found = true

// 更新剩余坑位
value.remainCount = remainCount - 1
colorMap.set(i, value)
break
}
}

i += 1
}

if (!found) {
// 没有找到,则为一种新颜色的兔子
const value = {totalCount: answer + 1, remainCount: answer}
colorMap.set(index, value)

// 颜色递增
index += 1
}
}
})



完整代码可点此查看



优化解法



其实,仔细想一想,我们并不需要给兔子分配颜色,只需要把同样答案的兔子聚集在一起,然后再逐个处理每个答案对应的数组。如下所示:



{
5 => [ 5 ],
2 => [ 2, 2, 2, 2, 2 ],
0 => [ 0 ]
}



比如 [2, 2, 2, 2, 2],兔子总数为 sum = 0



第一只兔子说有 2 只与其同色,那么同色总共有 3 个,sum += 3,此时还剩余 2 个坑位。

从第二只兔子开始遍历,如果坑位够,则坑位 - 1;如果不够,则新起颜色,sum += 3

...

以此类推。



因此,总是在新起颜色的时候,更新兔子总数为 sum += answer + 1,也就是上面的结论 4



这种方式比解法 1 要高效,68%



关键代码如下:

answerMap.forEach((value, key) => {
if (key === 0) {
// 每个兔子都是不同颜色
sum += value.length
} else {

// 取第一个兔子说的数目+1,即为应有的总数
const totalCount = key + 1
sum += totalCount

// 除去第一只兔子,还剩的总数
let remainCount = key

// 从第二只兔子开始
let i = 1
while (i < value.length) {
// 剩余兔子数 > 0,则该兔子说的数量可以覆盖
if (remainCount > 0) {
remainCount -= 1
} else {
// 不能覆盖,则需要新增颜色
sum += totalCount
remainCount = key
}

i += 1
}
}
})



完整代码可点此查看



最优解



其实第二种已经比较靠近最优解了,但是没有必要去一个个遍历数组计算兔子数量,这样是手工在计算数量。其实将相同答案的兔子聚合后,可以根据答案对应的兔子数量 count 来计算出所需的兔子数。



为什么这样说呢?通过解法 2 也能略知一二,因为它就是在模拟整个计算过程。下面我们还是来分析一下。



首先明确一点,答案的数值代表同色兔子数目为 answer + 1,显然,它可以覆盖到 answer + 1 只兔子。



当坑位不足的时候,即从 answer + 2 只兔子开始,需要新起颜色,此时又可以向后覆盖到 answer + 1 只兔子。因此,我们只需要计算出需要几组坑位 n,才能覆盖所有的兔子。而每组的坑位数为 answer + 1,那么数量为 n * (answer + 1)



这么说可能还是不大清楚,来看看下面几个栗子。



  1. 假设答案为 2 的兔子有 5 只,此时某种颜色的坑位数为 3,可以覆盖前 3 只兔子。第 4 只兔子需新起颜色,可覆盖后 2只兔子,因此需要 2 组坑位。



  1. 假设答案为 2 的兔子有 3 只,此时某种颜色的坑位数为 3,现在刚好有 3 只兔子,可以满足,所以只需 1 组坑位。



  1. 假设答案为 2 的兔子有 6 只,此时某种颜色的坑位数为 3,可以覆盖前 3 只兔子。第 4 只兔子需新起颜色,覆盖后三只兔子,则需要 2 组坑位。



从上,可以推导出:

  • 如果 count / (answer + 1) == 0,坑位组数 = count / (answer + 1)

  • 如果 count / (answer + 1) != 0,坑位组数 = count / (answer + 1) + 1



这种方式是最简洁的,但是需要理解其思想。效率也最高,96%

var numRabbits3 = function (answers) {
if (!answers || answers.length === 0) {
return 0
}

let sum = 0

// 计算相同答案兔子个数
let answerMap = new Map()
answers.forEach(answer => {
let count
if (answerMap.has(answer)) {
count = answerMap.get(answer) + 1
} else {
count = 1
}

answerMap.set(answer, count)
})

answerMap.forEach((value, key) => {
// 应有的兔子的总数
const num = key + 1

// Math.ceil(value / num) 表示应该有几组 num,如果 key = 10,value = 24,说明需要 3 组兔子才能满足,因为第一只兔子说的总数为 11,可以覆盖到前 11 只兔子。第 12 只兔子说的总数为 11,也可以覆盖 11 只,即到 22 只,依次类推。
sum += num * Math.ceil(value / num)
})

return sum
}



以上三种解法完整代码可点此查看



本文同步发表在简书:https://www.jianshu.com/p/d3efd992a07a



发布于: 2020 年 05 月 16 日 阅读数: 65
用户头像

liu_liu

关注

不要相信自己的记忆力 2017.11.13 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode 781. Rabbits in Forest