数据结构
网络
关系型数据库管理系统 (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+ 次浏览
广告