用 C++ 设计排行榜
c++server side programmingprogramming
假设我们要设计一个排行榜类，有三个不同的函数 −
- 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
