資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究在 C++ 中設計排行榜
假設我們必須設計一個 Leaderboard 類，它有三個不同的函式：
- addScore(playerId, score) - 此函式將透過將分數新增到給定玩家的分數來更新排行榜。當排行榜中沒有具有給定 ID 的玩家時，將該玩家及其分數新增到排行榜。
- top(K) - 此函式將返回前 K 名玩家的分數總和。
- reset(playerId) - 此函式將把具有給定 ID 的玩家的分數重置為 0。保證在呼叫此函式之前，該玩家已新增到排行榜中。
最初，排行榜應該是空的。
如果我們執行如下操作：
- Leaderboard leaderboard = new Leaderboard ();
- leaderboard.addScore(1,73); // 排行榜為 [[1,73]];
- leaderboard.addScore(2,56); // 排行榜為 [[1,73],[2,56]];
- leaderboard.addScore(3,39); // 排行榜為 [[1,73],[2,56],[3,39]];
- leaderboard.addScore(4,51); // 排行榜為 [[1,73],[2,56],[3,39],[4,51]];
- leaderboard.addScore(5,4); // 排行榜為 [[1,73],[2,56],[3,39],[4,51],[5,4]];
- leaderboard.top(1); // 返回 73;
- leaderboard.reset(1); // 排行榜為 [[2,56],[3,39],[4,51],[5,4]];
- leaderboard.reset(2); // 排行榜為 [[3,39],[4,51],[5,4]];
- leaderboard.addScore(2,51); // 排行榜為 [[2,51],[3,39],[4,51],[5,4]];
- leaderboard.top(3); // 返回 141 = 51 + 51 + 39;
為了解決這個問題，我們將遵循以下步驟：
- 定義一個名為 pq 的整數對優先佇列，建立一個 int 型別鍵和 int 型別值的對映 m。初始化時，它將清空對映，如果佇列不為空，則刪除佇列中的所有元素。
- addScore() 方法將如下所示：
- 如果 playerId 存在，則 m[playerId] := m[playerId] + score
- 將一個對 (m[playerId], playerId) 插入到 pq 中
- 否則 m[playerId] = score
- top() 方法將如下所示
- 建立一個對向量 temp，設定 sum := 0
- 當 k 不為 0 時
- curr := pq 的頂部，從 pq 中刪除
- 如果 m[curr 對的第二個值] = curr 對的第一個值
- 將 k 減 1
- sum := sum + curr 的第一個值
- 將 curr 插入到 temp 中
- 對於 i 在 0 到 temp 大小範圍內
- 將 temp[i] 插入到 pq 中
- reset() 函式將如下所示：
- m[playerId] = 0
示例（C++）
讓我們看看以下實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Leaderboard {
public:
priority_queue< pair <int,int> > pq;
map < int, int > m;
Leaderboard() {
m.clear();
while(!pq.empty())pq.pop();
}
void addScore(int playerId, int score) {
if(m.find(playerId)!=m.end()){
m[playerId] += score;
}
else m[playerId] = score;;
pq.push({m[playerId], playerId});
}
int top(int k) {
vector < pair <int,int> > temp;
int sum = 0;
while(k){
pair <int, int> curr = pq.top();
pq.pop();
if(m[curr.second] == curr.first){
k--;
sum += curr.first;
temp.push_back(curr);
}
}
for(int i = 0; i < temp.size(); i++)pq.push(temp[i]);
return sum;
}
void reset(int playerId) {
m[playerId] = 0;
}
};
main(){
Leaderboard ob;
ob.addScore(1,73);
ob.addScore(2,56);
ob.addScore(3,39);
ob.addScore(4,51);
ob.addScore(5,4);
cout <<ob.top(1) << endl;
ob.reset(1);
ob.reset(2);
ob.addScore(2,51);
cout <<ob.top(2) << endl;
}輸入
Initialize leader board then use the functions to see different results. See the main() function
輸出
73 102
更新於： 2020 年 4 月 30 日
1K+ 次瀏覽
廣告