文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

森林中，每個兔子都有顏色。
其中一些兔子（可能是全部）告訴你還有多少其他的兔子和自己有相同的顏色。
我們將這些回答放在 answers 數(shù)組里。

返回森林中兔子的最少數(shù)量。

示例: 輸入: answers = [1, 1, 2] 輸出: 5 解釋: 兩只回答了 "1" 的兔子可能有相同的顏色，設(shè)為紅色。 之后回答了 "2" 的兔子不會是紅色，否則他們的回答會相互矛盾。 設(shè)回答了 "2" 的兔子為藍色。 此外，森林中還應(yīng)有另外 2 只藍色兔子的回答沒有包含在數(shù)組中。 因此森林中兔子的最少數(shù)量是 5: 3 只回答的和 2 只沒有回答的。輸入: answers = [10, 10, 10] 輸出: 11輸入: answers = [] 輸出: 0說明: answers 的長度最大為1000。 answers[i] 是在 [0, 999] 范圍內(nèi)的整數(shù)。

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/rabbits-in-forest
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 思維題

class Solution { public:int numRabbits(vector<int>& answers) {unordered_map<int,int> m;for(auto a : answers)m[a+1]++;//有a+1個人一個顏色，多少個兔子這么說了int ans = 0;for(auto &mi : m){int tellnum = mi.first;//這么多兔子是一種顏色int people = mi.second;//有多少個兔子這么說了//貪心，讓他們組成同一種顏色，如 5個兔子說有5個兔子顏色一樣// 那么這5個兔子組成一種顏色即可，答案是5只// 6個兔子說有5個兔子顏色一樣，把5個顏色一樣的拿走// 還剩下的1只兔子肯定是別的顏色，他還有4個同伴沒有回答，答案是10只ans += ceil(double(people)/tellnum)*tellnum;}return ans;} };

4 ms 8.4 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 781. 森林中的兔子（哈希+贪心）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。