資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++森林中的兔子
假設在森林裡，每隻兔子都有某種顏色。現在，一些兔子子集（可能是所有兔子）會告訴我們有多少其他兔子與它們顏色相同。這些答案放在一個數組中。我們必須找到森林中兔子的最小數量。因此，如果輸入類似於 [1,1,2]，則輸出將為 5，因為回答“1”的兩隻兔子可能是同一種顏色，例如白色。現在，回答“2”的兔子不能是白色，否則答案將不一致。假設回答“2”的兔子是黑色。那麼森林中還應該有 2 只其他黑色兔子沒有回答到陣列中。因此，森林中最小的兔子數量是 5：3 個回答的兔子加上 2 個沒有回答的兔子。
為了解決這個問題，我們將遵循以下步驟：
- 建立一個對映 m，以及 n := 陣列 ans 的大小
- 設定 ret 為 0
- 對於 i 從 0 到 n – 1
- x := ans[i]
- 如果 x = 0，則將 ret 加 1，並跳過本次迭代的其餘部分。
- 如果 m 包含 x，則將 ret 加上 (x + 1)，設定 m[x] := 0
- 否則
- 將 m[x] 加 1
- 如果 m[x] = x，則從 m 中刪除 x
- 返回 ret
讓我們看看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numRabbits(vector<int>& ans) {
map <int, int> m;
int n = ans.size();
int ret = 0;
for(int i = 0; i < n; i++){
int x = ans[i];
if(x == 0){
ret++;
continue;
}
if(!m.count(x)){
ret += (x + 1);
m[x] = 0;
}else{
m[x]++;
if(m[x] == x){
m.erase(x);
}
}
}
return ret;
}
};
main(){
vector<int> v = {1,1,2};
Solution ob;
cout << (ob.numRabbits(v));
}輸入
[1,1,2]
輸出
5
更新於：2020年5月4日
401 次瀏覽
廣告