[LeetCode] 825. Friends Of Appropriate Ages

miya 發(fā)布于2019-08-16 13:47 / 2978人閱讀

Problem

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.

Solution

class Solution {
    public int numFriendRequests(int[] ages) {
        //0.5*ages[A]+7 < ages[B] <= ages[A]
        //7 < 0.5*ages[A] ====> ages[A] >= 15
        int res = 0;
        int[] nums = new int[121];
        int[] sums = new int[121];
        
        for (int age: ages) {
            nums[age]++;
        }
        
        for (int i = 1; i <= 120; i++) {
            sums[i] = sums[i-1]+nums[i];
        }
        
        for (int i = 15; i <= 120; i++) {
            if (nums[i] == 0) continue;
            int count = sums[i] - sums[i/2+7]; //number of range B
            res += count*nums[i] - nums[i]; //range B * number of age A
        }
        
        return res;
    }
}

GPU云服務(wù)器云服務(wù)器 Appropriate Ages Friends LeetCode

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/72320.html

相關(guān)文章

[LeetCode/LintCode] Design Twitter/Mini Twitter

摘要：首先建立按時(shí)間戳從大到小排列的，找到中的，出其中在中存在的，把每一個(gè)的推特鏈表放入，再?gòu)闹腥☆^十條推特的放入結(jié)果數(shù)組。 Design Twitter Note 建立兩個(gè)HashMap，一個(gè)存user，一個(gè)存tweets。以及整型的時(shí)間戳timestamp。user的k-v pair是userId-follower_set，tweets的k-v pair是userId-tweets_li...

honmaple 2019-08-14 15:31 評(píng)論0 收藏0
Lodash 中 assign，extend 和 merge 的區(qū)別

摘要：簡(jiǎn)介我們經(jīng)常在別人的代碼中看見，，函數(shù)，這三個(gè)函數(shù)用起來很相似，都是合并源對(duì)象的屬性到目標(biāo)對(duì)象中。會(huì)修改原來的對(duì)象在版本中，是的別名，它們的作用是一模一樣的。在版本中，是的別名，和有點(diǎn)區(qū)別。如果源對(duì)象的屬性值為，則會(huì)忽略該屬性。簡(jiǎn)介我們經(jīng)常在別人的代碼中看見 assign，extend，merge 函數(shù)，這三個(gè)函數(shù)用起來很相似，都是合并源對(duì)象的屬性到目標(biāo)對(duì)象中。既然都是合并對(duì)象，...

solocoder 2019-08-19 18:02 評(píng)論0 收藏0
JavaScript 編程精解中文第三版六、對(duì)象的秘密

摘要：在編程文化中，我們有一個(gè)名為面向?qū)ο缶幊痰臇|西，這是一組技術(shù)，使用對(duì)象和相關(guān)概念作為程序組織的中心原則。這是構(gòu)造器函數(shù)的作用。因此，上面的類聲明等同于上一節(jié)中的構(gòu)造器定義。來源：ApacheCN『JavaScript 編程精解中文第三版』翻譯項(xiàng)目原文：The Secret Life of Objects 譯者：飛龍協(xié)議：CC BY-NC-SA 4.0 自豪地采用谷歌翻譯部分參考...

ddongjian0000 2019-08-23 18:19 評(píng)論0 收藏0
golang學(xué)習(xí)筆記（一）——golang基礎(chǔ)和相關(guān)數(shù)據(jù)結(jié)構(gòu)

摘要：小白前端一枚，最近在研究，記錄自己學(xué)習(xí)過程中的一些筆記，以及自己的理解。此外，結(jié)構(gòu)體也支持嵌套。在函數(shù)聲明時(shí)，在函數(shù)名前放上一個(gè)變量，這個(gè)變量稱為方法的接收器，一般是結(jié)構(gòu)體類型的。小白前端一枚，最近在研究golang，記錄自己學(xué)習(xí)過程中的一些筆記，以及自己的理解。 go中包的依賴管理 go中的切片 byte 和 string go中的Map go中的struct結(jié)構(gòu)體 go中的方...

lyning 2019-08-26 13:27 評(píng)論0 收藏0
Python全棧之路系列之元組數(shù)據(jù)類型

摘要：元組和列表的為唯一區(qū)別就是列表可以更改，元組不可以更改，其他功能與列表一樣創(chuàng)建元組的兩種方法第一種第二種如果元祖內(nèi)只有一個(gè)元素，那么需要加上一個(gè)逗號(hào)，否則就變成字符串了。元組(tuple)和列表的為唯一區(qū)別就是列表可以更改，元組不可以更改，其他功能與列表一樣創(chuàng)建元組的兩種方法第一種 ages = (11, 22, 33, 44, 55) 第二種 ages = tuple((11,...

李濤 2019-07-25 11:22 評(píng)論0 收藏0