[Swift]LeetCode825.适龄的朋友|FriendsOfAppropriateAges

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10569342.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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

Otherwise, 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.

Notes:

1 <= ages.length <= 20000.
1 <= ages[i] <= 120.

人们会互相发送好友请求，现在给定一个包含有他们年龄的数组，ages[i] 表示第 i 个人的年龄。

当满足以下条件时，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 <= ages.length <= 20000.
1 <= ages[i] <= 120.

Runtime: 240 ms

Memory Usage: 19.4 MB

 1 class Solution {
 2     func numFriendRequests(_ ages: [Int]) -> Int {
 3         var res:Int = 0
 4         var numInAge:[Int] = [Int](repeating:0,count:121)
 5         var sumInAge:[Int] = [Int](repeating:0,count:121)
 6         for age in ages
 7         {
 8             numInAge[age] += 1
 9         }
10         for i in 1...120
11         {
12             sumInAge[i] = numInAge[i] + sumInAge[i - 1]
13         }
14         for i in 15...120
15         {
16             if numInAge[i] == 0 {continue}
17             var cnt:Int = sumInAge[i] - sumInAge[Int(Double(i) * 0.5 + 7)]
18             res += cnt * numInAge[i] - numInAge[i]
19         }
20         return res
21     }
22 }

268ms

 1 class Solution {
 2     func numFriendRequests(_ ages: [Int]) -> Int {
 3         var count = [Int](repeating: 0, count: 121)
 4         for age in ages { count[age] += 1 }
 5 
 6         var ans = 0
 7         for ageA in 0...120 {
 8             let countA = count[ageA]
 9             for ageB in 0...120 {
10                 let countB = count[ageB]
11                 if (ageA + 14) >= 2*ageB { continue }
12                 if ageA < ageB { continue }
13                 if ageA < 100 && 100 < ageB { continue }
14                 ans += countA * countB
15                 if ageA == ageB  { ans -= countA}
16             }
17         }
18         return ans
19     }
20 }

292ms

 1 class Solution {
 2     func numFriendRequests(_ ages: [Int]) -> Int {
 3         var map = [Int: Int]()
 4         for age in ages {
 5             map[age] = (map[age] ?? 0) + 1
 6         }
 7         var result = 0
 8         for i in 0...120 {
 9             if let iCount = map[i] {
10                 for j in 0...120 {
11                     if let jCount = map[j] {
12                         if j <= i / 2 + 7 || j > i || (j > 100 && i < 100) {
13                             continue
14                         }
15                         if i == j {
16                             result += (iCount - 1) * iCount
17                         } else {
18                             result += iCount * jCount
19                         }
20                     }
21                 }
22             }
23         }
24         return result
25     }
26 }

404ms

 1 class Solution {
 2     func numFriendRequests(_ ages: [Int]) -> Int {
 3         var ageCounts = [Int](repeating: 0, count: 121)
 4         for age in ages {
 5             ageCounts[age] += 1
 6         }
 7         var res = 0
 8         for i in 0..<ageCounts.count {
 9             var ageA = i
10             for j in 0..<ageCounts.count {
11                 var ageB = j
12                 if ageB <= Int(floor(0.5 * Double(ageA) + 7)) { continue }
13                 if ageB > ageA { continue }
14                 res += ageCounts[i] * ageCounts[j]
15                 if ageA == ageB {
16                     res -= ageCounts[i]
17                 }
18             }
19         }
20         return res
21     }
22 }