admin管理员组文章数量:1568433
题目原址
https://leetcode/problems/friends-of-appropriate-ages/description/
题目描述
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
therwise, 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?
Example 1:
Input: [16,16]
Output: 2
Explanation: 2 people friend request each other.
Example 2:
Input: [16,17,18]
Output: 2
Explanation: Friend requests are made 17 -> 16, 18 -> 17.
Example 3:
Input: [20,30,100,110,120]
Output:
Explanation: Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.
解题思路
- 首先给定的数组中的元素不是有序的,所以要先排序,调用Arrays的
sort()
方法 - 定义Map的目的:因为数组中元素有可能是重复的,因此需要按照元素的值作为map的键,将能够成为朋友的次数作为值存在map中
- ret变量是返回值,表示数组中一共可以组成多少个朋友;sum是指当前的元素与剩余的元素可以组成多少朋友;
- 首先进行一层循环,获取当前元素,如果集合中包含这个元素,就说明这个元素在之前出现过,则直接获取这个元素能够结交的朋友数累加到ret中即可,然后跳出本层循环;
- 如果集合中不包含这个元素,说明这个元素之前没有出现过,不是重复的元素,需要与数组中的其他元素进行比较,如果比较成功,则将当前的sum自加,直到遍历到数组最后一个元素
- 内层循环出来后,将当前元素的sum值加到ret中,将当前元素和当前元素的sum值放在map中
AC代码
class Solution {
public int numFriendRequests(int[] ages) {
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
Arrays.sort(ages);
int ret = 0;
int sum = 0;
for(int i = 0; i < ages.length; i++) {
if(map.containsKey(ages[i])){
ret += map.get(ages[i]);
continue;
}
sum = 0;
for(int j = 0; j < ages.length; j++) {
if(i != j && requestOrNot(ages[i],ages[j]))
sum++;
}
ret += sum;
map.put(ages[i], sum);
}
return ret;
}
public boolean requestOrNot(int A, int B) {
if(B > 100 && A < 100)
return false;
else if(B > A)
return false;
else if(B <= 0.5 * A + 7)
return false;
else
return true;
}
}
版权声明:本文标题:Leetcode——825. Friends Of Appropriate Ages 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1726299691a1064982.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论