用C ++设计排行榜

假设我们必须设计一个排行榜类，有三个不同的功能-

• addScore(playerId,score)-这将通过将分数添加到给定玩家的分数来更新排行榜。如果排行榜中没有这样的具有给定ID的玩家，请将其添加到具有给定分数的排行榜中。

• top(K)-这将返回前K名选手的得分总和。

• reset(playerId)-这会将具有给定id的玩家的得分重置为0。确保在调用此函数之前将玩家添加到排行榜。

最初，排行榜应为空。

如果我们执行如下操作-

• 排行榜排行榜=新的排行榜()；

• 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] +得分

• 在pq中插入一对（m [playerId]，playerId）

• 否则m [playerId] =得分

• 该top()方法会像

• 制作温度对的向量，设置sum：= 0

• 当k不为0时

• 将k减1

• sum：= sum + curr的第一个值

• 将curr插入temp

• curr：= pq的顶部，从pq中删除

• 如果m [货币对的第二个值] =货币对的第一个值

• 对于我在0到温度范围内

• 将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