資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中適齡朋友
假設一些人會發出好友請求。我們知道他們的年齡，這些年齡儲存在 ages[i] 中。這表示第 i 個人的年齡。現在，如果滿足以下任何條件，A 不會向 B (B != A) 傳送好友請求：
- age[B] <= 0.5 * age[A] + 7
- age[B] > age[A]
- age[B] > 100 && age[A] < 100
否則，A 將會向 B 傳送好友請求。您可以認為，如果 A 請求 B，B 不一定會請求 A。而且，人們不會向自己傳送好友請求。所以我們必須找到總共傳送了多少個好友請求？
假設年齡陣列是 [16,17,18]，則結果為 2，因為請求將是 17 -> 16, 18 -> 17。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個大小為 1000 的陣列 bucket，然後將年齡陣列元素的頻率儲存在 bucket 中。
- 然後找到並存儲 bucket 元素的累積和到 bucket 中。
- ret := 0
- 對於 i 從 0 到 ages 陣列大小 - 1
- x := ages[i], y := (ages[i] / 2) + 7
- 如果 x >= y，則
- ret := bucket[x] – bucket[y]
- 如果 bucket[x] – bucket[y] 不為零，則將 ret 減 1
- 返回 ret。
讓我們看看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numFriendRequests(vector<int>& ages) {
vector <int> bucket(1000);
for(int i = 0; i < ages.size(); i++){
bucket[ages[i]]++;
}
for(int i = 1; i < 1000; i++)bucket[i] += bucket[i - 1];
int ret = 0;
for(int i = 0; i < ages.size(); i++){
int x = ages[i];
int y = ((ages[i]) / 2) + 7;
if(x >= y){
ret += (bucket[x] - bucket[y]);
if((bucket[x] - bucket[y]))
ret--;
}
}
return ret;
}
};
main(){
vector<int> v1 = {16, 17, 18};
Solution ob;
cout << (ob.numFriendRequests(v1));
}輸入
[16,17,18]
輸出
2
更新於：2020年5月5日
219 次瀏覽
廣告