LeetCode 1244. 力扣排行榜

地址 https://www.acwing.com/solution/LeetCode/content/5765/

题目描述
新一轮的「力扣杯」编程大赛即将启动，为了动态显示参赛者的得分数据，需要设计一个排行榜 Leaderboard。

请你帮忙来设计这个 Leaderboard 类，使得它有如下 3 个函数：

addScore(playerId, score)：
假如参赛者已经在排行榜上，就给他的当前得分增加 score 点分值并更新排行。
假如该参赛者不在排行榜上，就把他添加到榜单上，并且将分数设置为 score。
top(K)：返回前 K 名参赛者的得分总和。
reset(playerId)：将指定参赛者的成绩清零。题目保证在调用此函数前，该参赛者已有成绩，并且在榜单上。
请注意，在初始状态下，排行榜是空的

输入：

["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"]

[[],[,],[,],[,],[,],[,],[],[],[],[,],[]]

输出：

[null,null,null,null,null,null,,null,null,null,]

解释：

Leaderboard leaderboard = new Leaderboard ();

leaderboard.addScore(,);   // leaderboard = [[1,73]];

leaderboard.addScore(,);   // leaderboard = [[1,73],[2,56]];

leaderboard.addScore(,);   // leaderboard = [[1,73],[2,56],[3,39]];

leaderboard.addScore(,);   // leaderboard = [[1,73],[2,56],[3,39],[4,51]];

leaderboard.addScore(,);    // leaderboard = [[1,73],[2,56],[3,39],[4,51],[5,4]];

leaderboard.top();           // returns 73;

leaderboard.reset();         // leaderboard = [[2,56],[3,39],[4,51],[5,4]];

leaderboard.reset();         // leaderboard = [[3,39],[4,51],[5,4]];

leaderboard.addScore(,);   // leaderboard = [[2,51],[3,39],[4,51],[5,4]];

leaderboard.top();           // returns 141 = 51 + 51 + 39;

算法1
这道题目我感觉更像系统设计题
由于需要依靠ID快速查找对应分数并且分数还需要快速排序，所以我觉得应该需要两个容器去进行存储，应对不同的需求。
查找当然是哈希，排序的话由于分数不是唯一的，我采取的是vector
那么对记录进行增删改的时候就需要对两个容器进行操作

C++ 代码

 class Leaderboard {

 public:

     vector<int> scoreVec;

     map<int, int> idScore;

     Leaderboard() {

         scoreVec.clear();

         idScore.clear();

     }

     void addScore(int playerId, int score) {

         if (idScore.count(playerId) != ) {

             int oldscore = idScore[playerId];

             idScore[playerId] += score;

             vector<int>::iterator it = find(scoreVec.begin(), scoreVec.end(), oldscore);

             *it += score;

         }

         else {

             idScore[playerId] = score;

             scoreVec.push_back(score);

         }

     }

     int top(int K) {

         sort(scoreVec.begin(), scoreVec.end(),greater<int>());

         int sum = ;

         for (int i = ; i < scoreVec.size() && i < K; i++) {

             sum += scoreVec[i];

         }

         return sum;

     }

     void reset(int playerId) {

         int score = idScore[playerId];

         idScore.erase(playerId);

         vector<int>::iterator it = find(scoreVec.begin(), scoreVec.end(), score);

         scoreVec.erase(it);

     }

 };

巴特西

LeetCode 1244. 力扣排行榜

最新文章

热门文章