题目
Some people will make friend requests. The list of their ages is given and ages[i] is the age of the ith person.
Person A will NOT friend request person B (B != A) if any of the following conditions are true:
age[B] <= 0.5 * age[A] + 7
age[B] > age[A]
age[B] > 100 && age[A] < 100
Otherwise, A will friend request B.
Note that if A requests B, B does not necessarily request A. Also, people will not friend request themselves.
How many total friend requests are made?
这个题目特别有趣。最傻的办法就是来一个n^2循环每个pair相互用给出的三条规则比一下，符合规则requests的数量就+1。但是用屁股想也知道会TLE。
另外一个办法是，用一个size为121的array criterias
criterias[i] 表示有多少个人会对age为i的人make friend requests
你先把整个array扫一遍，就能填好criterias
接下来，再把array扫一遍，requests += criterias[ages[i]]
有一些corner case要注意: for age <= 14, none of the three criterias will satisfy
答案
class Solution {
public int numFriendRequests(int[] ages) {
int[] criterias = new int[121];
int ans = 0, cnt = 0;
for(int age : ages) {
if(age <= 14) continue;
double start = 0.5 * age + 7;
if(start % 1 == 0) start += 1.0;
else start = Math.ceil(start);
for(int i = (int)start; i <= age; i++)
criterias[i]++;
cnt++;
}
for(int age : ages)
ans += criterias[age];
return ans - cnt;
}
}
