锐客网

  1. 首页 > 睿知 > it技术 > >

Leetcode|Leetcode 825. 适龄的朋友 C++

Leetcode 825. 适龄的朋友 题目 人们会互相发送好友请求，现在给定一个包含有他们年龄的数组，ages[i] 表示第 i 个人的年龄。
【Leetcode|Leetcode 825. 适龄的朋友 C++】当满足以下任一条件时，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. 1 <= ages.length <= 20000.
  2. 1 <= ages[i] <= 120.
题解 滑动窗口
我们找到一个窗口，[i,j]使得i ~ j-1都可以给j发送好友请求。因为，不能满足age[B] > age[A]，我们可以知道age[i~ j-1]<=age[i]的，因此，我们先对age进行排序。
我们再考虑以下，A最小是多少岁，因为不能age[A]0.5 * age[A] + 7,也就是age[A]>14。因此，我们的i要保证，age[i]>14。
同时，由第一个条件，我们需要满足age[B] <= 0.5 * age[A] + 7，age是递增的，因此我们找到B的一个边界作为i，那么i+1 ~ j都可以给i发送好友请求。同时，和j年龄相同的人也可以给j发送好友请求，因此我们再找j右边和其年龄相同的人数。
详细过程见代码
代码
int numFriendRequests(vector& ages) { sort(ages.begin(),ages.end()); int ans = 0,n = ages.size(); int i=0,j; while(i14 j=i; //这是右边界 i=0; while(j < n){ while(i

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/friends-of-appropriate-ages
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    推荐阅读


    上一篇：leetcode|leetcode栈和队列

    下一篇：LeetCode|每日一题 leetcode 825. 适龄的朋友 java题解