数据结构
网络
关系数据库管理系统 (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 次浏览
广告