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

云惠网小编 2021年12月29日23:18:50
评论
1835字阅读6分7秒
摘要

文章目录题目题目解析解题思维1:代码附图解题思维2:附上方法二的代码题目 题目解析 解题思维1: 将 数组ages 进行排序(升序),其实就是将这批人 按照年龄 从高到低 进行排序。此时再使用 两个 “左右指针” 进行锁定 x 的交友范围。确定好了之后,right – left 就是 符合 x 交友条件的人数,也就是题目中的 x 会向 y 发送请求。 代码class Solution { public int numFriendRequests(int[] ag

广告也精彩

通过创建一个数组 cur,容量为 121,数组下标 等价于 年龄,下标对应的元素大小,就是处在该年龄的人数。
LeetCode – 825 – 适龄的朋友 – Java -在作者看来还算细
然后在创建一个同样大小的数组 prev,每个元素等于 自身前一个元素 加上 在cur中 与 该元素下标对应的元素。
LeetCode – 825 – 适龄的朋友 – Java -在作者看来还算细
有的朋友可能看不懂这块代码,简单来说 就是累加赋值:将处于 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;// 最终返回它。
}
}

解题思维2:

在这里插入图片描述

在这里插入图片描述

题目解析

在这里插入图片描述

解题思维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;// 返回 所有人 发送好友请求的信息条数。
}
}

附图

附上方法二的代码

代码


文章目录

  • 题目
  • 题目解析
  • 解题思维1:
    • 代码
    • 附图
  • 解题思维2:
    • 附上方法二的代码

本文转自 https://blog.csdn.net/DarkAndGrey/article/details/122176535

腾讯云618
未分类
云惠网小编
SpringCloud -- Config、Bus解析

SpringCloud — Config、Bus解析

1、Config1.1、概述简介1. 分布式面临的问题微服务意味着要将单体应用中的业务拆分成一个个子服务,每个服务的粒度相对较小,因此系统中会出现大量的服务。由于每个服务都需要必要...
Java数据结构-了解复杂度

Java数据结构-了解复杂度

2.实例分析与计算  四.写在最后  // 计算斐波那契递归fibonacci的时间复杂度 int fibonacci(int N) { return N < 2 ? N : fibonacci...
[深度解剖C语言] --关键字 static

[深度解剖C语言] –关键字 static

static ---最名不副实的关键字目录1.static修饰全局变量2.static修饰函数3.static修饰局部变量static的作用:1.static修饰全局变量我们创建两...
Java数据结构-认识顺序表

Java数据结构-认识顺序表

目录二.顺序表1.概念及结构2.顺序表的实现打印顺序表获取顺序表的有效长度在pos位置新增元素判断是否包含某个元素查找某个元素对应的位置获取/查找pos位置的元素给pos位置的元素...
腾讯云618

发表评论