在 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+ 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告