每日一题——825. 适龄的朋友

825. 适龄的朋友

在社交媒体网站上有 n 个用户。给你一个整数数组 ages ,其中 ages[i] 是第 i 个用户的年龄。

如果下述任意一个条件为真,那么用户 x 将不会向用户 y(x != y)发送好友请求:

age[y] <= 0.5 * age[x] + 7
age[y] > age[x]
age[y] > 100 && age[x] < 100
否则,x 将会向 y 发送一条好友请求。

注意,如果 x 向 y 发送一条好友请求,y 不必也向 x 发送一条好友请求。另外,用户不会向自己发送好友请求。

返回在该社交媒体网站上产生的好友请求总数。


早上被这种阅读理解题整的我有点爆炸

主要关键是我不能理解第一个用例

输入:

ages = [16,16]

输出:

2

解释:

2 人互发好友请求。

那你为什么还在题目中特别强调了这是互发是不必要的呢

所以这就是所谓的不必要吗?

把我整麻了

姑且还是放一下我的错误做法吧

public class Solution {
    public int NumFriendRequests(int[] ages) {
        Array.Sort(ages);
        int left = 0;
        int right = ages.Length-1;
        int ans = 0;
        while(left <= right)
        {
            if(left == right)
            {
                left++;
                right = ages.Length-1;
                continue;
            }

            if(ages[left] > 100 && ages[right] < 100)
            {
                right--;
            }
            else if(ages[left] <= (ages[right]*0.5 + 7))
            {
                right--;
            }
            else
            {
                ans++;
                if(ages[left] == ages[right])
                {
                    ans++;
                }
                right--;
            }

        }

        return ans;
    }
}

我的思路也是二分 但是我是用计数的方式的

所以遇到像这种极端用例又超时了

贴贴官方题解的思路吧

思路差距在于

提炼条件可得0.5×ages[x]+7<ages[y]ages[x]

只需要 考虑年龄大于15的情况

x 发送的好友请求数,即为 [left,right] 区间的长度减去 1

将每一个 x 对应的[left,right] 区间长度减去 1 进行累加

就可以得到最终的答案

public class Solution {
    public int NumFriendRequests(int[] ages) {
        int n = ages.Length;
        Array.Sort(ages);
        int left = 0, right = 0, ans = 0;
        foreach (int age in ages) {
            if (age < 15) {
                continue;
            }
            while (ages[left] <= 0.5 * age + 7) {
                ++left;
            }
            while (right + 1 < n && ages[right + 1] <= age) {
                ++right;
            }
            ans += right - left;
        }
        return ans;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/friends-of-appropriate-ages/solution/gua-ling-de-peng-you-by-leetcode-solutio-v7yk/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

 


发表评论

您的电子邮箱地址不会被公开。