作者： 負(fù)雪明燭
id： fuxuemingzhu
個人博客： http://fuxuemingzhu.cn/

---

題目地址：https://leetcode.com/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

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.

題目大意

這個題讓我們找出有多少個好友申請。好友申請不能成立的條件：

• age[B] <= 0.5 * age[A] + 7
• age[B] > age[A]
• age[B] > 100 && age[A] < 100

總結(jié)一下：A只能向年齡小于等于自己的人(B)申請，并且也不能太小，總之要滿足0.5 * age[A] + 7 < B <= A.

第三個條件是第二個條件的子集，只要滿足條件二一定滿足條件三。

解題方法

把上面的約束條件理解清楚之后就很簡單了。首先我們需要統(tǒng)計個數(shù)，然后肯定需要進(jìn)行排序，然后遍歷標(biāo)記為A，查找滿足他的申請條件的B有多少。

對于A,B他們之間有多少對申請？如果A!=B，那么A要向每個B進(jìn)行申請；如果A==B，那么A要向和他年齡一樣大的其他人申請。

時間復(fù)雜度是O(120 * N)，空間復(fù)雜度是O(120).

class Solution(object):def numFriendRequests(self, ages):""":type ages: List[int]:rtype: int"""count = collections.Counter(ages)ages = sorted(count.keys())N = len(ages)res = 0for A in ages:for B in range(int(0.5 * A) + 7 + 1, A + 1):res += count[A] * (count[B] - int(A == B))return res

日期

2018 年 10 月 19 日 —— 自古逢秋悲寂寥，我言秋日勝春朝

總結(jié)

以上是生活随笔為你收集整理的【LeetCode】825. Friends Of Appropriate Ages 解题报告（Python）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。