数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中适龄朋友
假设一些人会发出好友请求。我们知道他们的年龄，这些年龄存储在 ages[i] 中。这表示第 i 个人的年龄。现在，如果满足以下任何条件，A 不会向 B (B != A) 发送好友请求：
- age[B] <= 0.5 * age[A] + 7
- age[B] > age[A]
- age[B] > 100 && age[A] < 100
否则，A 将会向 B 发送好友请求。您可以认为，如果 A 请求 B，B 不一定会请求 A。而且，人们不会向自己发送好友请求。所以我们必须找到总共发送了多少个好友请求？
假设年龄数组是 [16,17,18]，则结果为 2，因为请求将是 17 -> 16, 18 -> 17。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个大小为 1000 的数组 bucket，然后将年龄数组元素的频率存储在 bucket 中。
- 然后找到并存储 bucket 元素的累积和到 bucket 中。
- ret := 0
- 对于 i 从 0 到 ages 数组大小 - 1
- x := ages[i], y := (ages[i] / 2) + 7
- 如果 x >= y，则
- ret := bucket[x] – bucket[y]
- 如果 bucket[x] – bucket[y] 不为零，则将 ret 减 1
- 返回 ret。
让我们看看下面的实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numFriendRequests(vector<int>& ages) {
vector <int> bucket(1000);
for(int i = 0; i < ages.size(); i++){
bucket[ages[i]]++;
}
for(int i = 1; i < 1000; i++)bucket[i] += bucket[i - 1];
int ret = 0;
for(int i = 0; i < ages.size(); i++){
int x = ages[i];
int y = ((ages[i]) / 2) + 7;
if(x >= y){
ret += (bucket[x] - bucket[y]);
if((bucket[x] - bucket[y]))
ret--;
}
}
return ret;
}
};
main(){
vector<int> v1 = {16, 17, 18};
Solution ob;
cout << (ob.numFriendRequests(v1));
}输入
[16,17,18]
输出
2
更新于：2020年5月5日
219 次浏览
广告