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 只兔子。

试想一下：

• 如果 A 与 B 不同，那么总共有 2 + 2 = 4 只兔子。
• 如果 A 与 B 相同，那么总共有 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，总数为 3。B 的剩余坑位为 2。

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

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

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

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

• 第七只兔子说有 2 只兔子同色，虽然跟它口径一致的是兔 3 和 6，但兔 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 组坑位。

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

3. 假设答案为 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
}

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