地址 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"] [[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]] 输出: [null,null,null,null,null,null,73,null,null,null,141] 解释: Leaderboard leaderboard = new Leaderboard (); leaderboard.addScore(1,73); // leaderboard = [[1,73]]; leaderboard.addScore(2,56); // leaderboard = [[1,73],[2,56]]; leaderboard.addScore(3,39); // leaderboard = [[1,73],[2,56],[3,39]]; leaderboard.addScore(4,51); // leaderboard = [[1,73],[2,56],[3,39],[4,51]]; leaderboard.addScore(5,4); // leaderboard = [[1,73],[2,56],[3,39],[4,51],[5,4]]; leaderboard.top(1); // returns 73; leaderboard.reset(1); // leaderboard = [[2,56],[3,39],[4,51],[5,4]]; leaderboard.reset(2); // leaderboard = [[3,39],[4,51],[5,4]]; leaderboard.addScore(2,51); // leaderboard = [[2,51],[3,39],[4,51],[5,4]]; leaderboard.top(3); // returns 141 = 51 + 51 + 39;
算法1
这道题目 我感觉更像系统设计题
由于需要依靠ID快速查找对应分数 并且分数还需要快速排序,所以我觉得应该 需要两个容器去进行存储,应对不同的需求。
查找当然是哈希,排序的话由于分数不是唯一的,我采取的是vector
那么对记录进行增删改的时候 就需要对两个容器进行操作
C++ 代码
1 class Leaderboard { 2 public: 3 vector<int> scoreVec; 4 map<int, int> idScore; 5 Leaderboard() { 6 scoreVec.clear(); 7 idScore.clear(); 8 } 9 10 void addScore(int playerId, int score) { 11 if (idScore.count(playerId) != 0) { 12 int oldscore = idScore[playerId]; 13 idScore[playerId] += score; 14 vector<int>::iterator it = find(scoreVec.begin(), scoreVec.end(), oldscore); 15 *it += score; 16 } 17 else { 18 idScore[playerId] = score; 19 scoreVec.push_back(score); 20 } 21 } 22 23 int top(int K) { 24 sort(scoreVec.begin(), scoreVec.end(),greater<int>()); 25 int sum = 0; 26 for (int i = 0; i < scoreVec.size() && i < K; i++) { 27 sum += scoreVec[i]; 28 } 29 return sum; 30 } 31 32 void reset(int playerId) { 33 int score = idScore[playerId]; 34 idScore.erase(playerId); 35 vector<int>::iterator it = find(scoreVec.begin(), scoreVec.end(), score); 36 scoreVec.erase(it); 37 } 38 };