发布时间:2024-07-04 19:01
825. 适龄的朋友 https://leetcode-cn.com/problems/friends-of-appropriate-ages/
人们会互相发送好友请求,现在给定一个包含有他们年龄的数组,ages[i]
表示第 i 个人的年龄。
当满足以下条件时,A 不能给 B(A、B不为同一人)发送好友请求:
age[B] <= 0.5 * age[A] + 7
age[B] > age[A]
age[B] > 100 && age[A] < 100
否则,A 可以给 B 发送好友请求。
注意如果 A 向 B 发出了请求,不等于 B 接受了 A 的请求。而且,人们不会给自己发送好友请求。
求总共会发出多少份好友请求?
示例 1:输入: [16,16] 输出: 2 解释: 二人可以互发好友申请。
示例 2:输入: [16,17,18] 输出: 2 解释: 好友请求可产生于 17 -> 16, 18 -> 17.
示例 3:输入: [20,30,100,110,120]输出: 3 解释: 好友请求可产生于 110 -> 100, 120 -> 110, 120 -> 100.
说明:
1 <= ages.length <= 20000
.1 <= ages[i] <= 120
.思路:按照年龄归类,分类处理。
存在问题,1, 3个关系之间是或 不是 并。
2.并不是16岁就不能给16岁发哦,是同一个人不能发,两个同是16岁的可以发。
3.注意if(dp[i][j]&&i==j) sum+=(agenum[i]-1)*agenum[j];
class Solution {
public:
const int N=122;
bool dp[122][122];
int agenum[122];
int numFriendRequests(vector& ages) {
for(int i=1; i<=120; i++) {
for(int j=1; j<=120; j++) {
/*
age[B] <= 0.5 * age[A] + 7
age[B] > age[A]
age[B] > 100 && age[A] < 100*/
if((double)j<=0.5*(double)i+7
|| j>i
|| j>100 && i<100)
dp[i][j]=false;
else dp[i][j]=true;
}
}
// 统计数量
int n=ages.size();
memset(agenum,0,sizeof(agenum));
for(int i=0; i