LeetCode 781. Rabbits in Forest

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

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

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

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

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

因此，总数为 11。

输入：answers = []
输出：0

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

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 ] 
}

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
        }
    }
})

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
}