LeetCode – 825 – 适龄的朋友 – Java -在作者看来还算细

题目

在这里插入图片描述


题目解析

在这里插入图片描述


解题思维1:

将 数组ages 进行排序(升序),其实就是将这批人 按照年龄 从高到低 进行排序。
此时再使用 两个 “左右指针” 进行锁定 x 的交友范围。
确定好了之后,right - left 就是 符合 x 交友条件的人数,也就是题目中的 x 会向 y 发送请求。


代码

class Solution {
    public int numFriendRequests(int[] ages) {
        Arrays.sort(ages);
        int n  = ages.length;
        int left = 0,right = 0,result=0;
        for(int age : ages){
            if( age < 15){
            // 不考虑 15岁以下的,这是题目隐藏条件,你不信邪,就加上等于,或者删除这个代码块
                continue;// 后面程序不执行,继续foreach 循环 读取数据。
            }
            while(ages[left] <= 0.5*age +7){// 太小的,不合适,left++,范围缩小
                left++;
            }
            while(right+1 < n && ages[right+1] <= age){// 年龄合适
                right++;
            }
            result += right -left;// 累计每个人 发出好友请求 
        }
        return result;// 返回 所有人 发送好友请求的信息条数。
    }
}

在这里插入图片描述

附图

在这里插入图片描述


解题思维2:

通过创建一个数组 cur,容量为 121,数组下标 等价于 年龄,下标对应的元素大小,就是处在该年龄的人数。
在这里插入图片描述
然后在创建一个同样大小的数组 prev,每个元素等于 自身前一个元素 加上 在cur中 与 该元素下标对应的元素。
在这里插入图片描述
有的朋友可能看不懂这块代码,简单来说 就是累加赋值:将处于 i 年龄段及其 比 i 年龄段小的人的总和。赋予 数组prev的 i 下标元素,将其值更新为 i 年龄段的人 及其 比 i 小的年龄段的所有人 总和。



接下来就是遍历 cur 数组,如果 有处在 i 年龄的人,也就说 cur[ i ] > 0的。此时,就需要像第一种方法一样,计算出 0.5 * i + 7 的值,也就是 处于 i 年龄的人,所不能接受的最小年龄的界限bound。
而且,请注意! 我们的prev的每个元素,都是对应cur 某一年龄及其以下的人数总和。
此时用 cur[i] 所对应的 prev[[i],就是 该年龄及其以下的人数总和,减去 计算出 0.5 * i + 7 的值,也就是 处于 i 年龄的人,所不能接受的最小年龄的界限bound。
用 prev[ i ] - prev[bound] 的结果:就是 处于 【0.5 * i + 7 < age[y] <= i 】的人数总和,也就是减去的结果都是 比 0.5 * i + 7 的结果 大,也就是说 所有人,都是 i 年龄人 的 交朋友对象。
当然 除了 自己。(不要问什么!题目要求的)
然后,就是把每个 i 年龄的人申请信息条数的一个累加。
最后返回这个累加的结果。
在这里插入图片描述


附上方法二的代码

class Solution {
    public int numFriendRequests(int[] ages) {
       // 统计每个年龄的人数,将其数组元素化
        int[] cur = new int[121];
        for(int age : ages){
            cur[age]++;
        }
        //统计每个年龄及其以下的人数总和,将其数组元素化
        int[] prev = new int[121];
        for(int i = 1; i < 121;i++){
            prev[i] = prev[i-1] + cur[i];
        }
        
        int result = 0;// 记录最终结果
        // 15岁以下不考虑,题目说的,从下标15 开始遍历数组 cur
        for(int i = 15; i < 121; i++){
            if(cur[i]>0){// 如果有处在 i 年龄的人
                int bound = (int)(0.5*i +7);// 计算他们所能接受最小年龄界限

                result += cur[i] * (prev[i] - prev[bound]-1);
                // 按照题目要求, i 年龄的人,所能接受的最小年龄,至少大于 界限 bound。
                // 用 目前 i 年龄及其以下的人数总和 减去 界限 bound的人数总和
                // 剩下就都是 比 bound 年龄大的人,且 最大年龄不超过 i 的人
                // 再根据题目要求,减去自己,剩下的人就是都 好友申请对象了。
                // 当然 处于 i 年龄的人,可能不止一个,所以要乘以一个 cur[i]。
                // 即: 每个 处于 i 年龄的人,都可以向除了自己以外的人,发出好友申请。
                // 最后。将其每个 i 年龄,所申请的信息条数累加。
            }
        }
        return result;// 最终返回它。
    }
}

在这里插入图片描述

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>