LeetCode 题解：781. 森林中的兔子，贪心，JavaScript，详细注释

关注

发布于: 1 小时前

LeetCode题解：781. 森林中的兔子，贪心，JavaScript，详细注释

解题思路：

如果一只兔子说还有n只兔子与它有相同颜色，那么必然存在n + 1只兔子。
answers中并不包含所有兔子，也就是说[2]、[2, 2]、[2, 2, 2]三种情况其实是一样的。
如果answers = [2, 2, 2]，只有当兔子数量为3只时，才能满足任意一只能告诉你还有2只与它有相同颜色。
如果answers = [2, 2, 2, 2]，此时回答可以拆分成两组，分别是[2, 2, 2]和[2]，共有6只兔子。
因此问题就转换为，将answers按照回答数量分类，并统计所有分类的兔子数量。
如果每类回答ans的数量有count个，那么兔子一共可以分为Math.ceil(count / (ans + 1))组，每组ans + 1只。
因此每类回答对应的兔子数量为Math.ceil(count / (ans + 1)) * (ans + 1)。

/** * @param {number[]} answers * @return {number} */var numRabbits = function (answers) {  let map = new Map(); // 使用Map缓存每种回答的数量  let result = 0; // 缓存结果
  // 遍历所有回答，统计每种回答出现的次数  for (const ans of answers) {    map.set(ans, map.has(ans) ? map.get(ans) + 1 : 1);  }
  // 根据每种回答的次数，计算兔子数量  for (const [ans, count] of map) {    // 统计每类回答对应兔子数量    result +=      // 计算每类回答可分为几组      Math.ceil(count / (ans + 1)) *      // 每组的兔子数量      (ans + 1);  }
  return result;};

复制代码

发布于: 1 小时前阅读数: 2

原文链接:【http://xie.infoq.cn/article/1496de52bd2069eb2a96451c4】。文章转载请联系作者。

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

发布

暂无评论

创作场景

LeetCode 题解：781. 森林中的兔子，贪心，JavaScript，详细注释

Lee Chen

评论