Thursday, October 8, 2020

LeetCode [1244] Design A Leaderboard

 1244. Design A Leaderboard

Medium

Design a Leaderboard class, which has 3 functions:

  1. addScore(playerId, score): Update the leaderboard by adding score to the given player's score. If there is no player with such id in the leaderboard, add him to the leaderboard with the given score.
  2. top(K): Return the score sum of the top K players.
  3. reset(playerId): Reset the score of the player with the given id to 0 (in other words erase it from the leaderboard). It is guaranteed that the player was added to the leaderboard before calling this function.

Initially, the leaderboard is empty.

 

Example 1:

Input: 
["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]]
Output: 
[null,null,null,null,null,null,73,null,null,null,141]

Explanation: 
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;

 

Constraints:

  • 1 <= playerId, K <= 10000
  • It's guaranteed that K is less than or equal to the current number of players.
  • 1 <= score <= 100
  • There will be at most 1000 function calls.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Leaderboard {
    Map<Integer, Integer> map;
    TreeMap<Integer, Integer> sorted;
    public Leaderboard() {
        map = new HashMap<>();
        sorted = new TreeMap<>(Collections.reverseOrder());
    }
    
    public void addScore(int playerId, int score) {
        if (!map.containsKey(playerId)) {
            map.put(playerId, score);
            sorted.put(score, sorted.getOrDefault(score, 0) + 1);
        } else {
            int preScore = map.get(playerId);
            sorted.put(preScore, sorted.get(preScore) - 1);
            if (sorted.get(preScore) == 0) {
                sorted.remove(preScore);
            }
            int newScore = preScore + score;
            map.put(playerId, newScore);
            sorted.put(newScore, sorted.getOrDefault(newScore, 0) + 1);
        }
    }
    
    public int top(int K) {
        int count = 0;
        int sum = 0;
        for (int key : sorted.keySet()) {
            int times = sorted.get(key);
            for (int i = 0; i < times; i++) {
                sum += key;
                count++;
                if (count == K) {
                    break;
                }
            }
            if (count == K) {
                break;
            }
        }
        return sum;
    }
    
    public void reset(int playerId) {
        int preScore = map.get(playerId);
        sorted.put(preScore, sorted.get(preScore) - 1);
        if (sorted.get(preScore) == 0) {
            sorted.remove(preScore);
        }
        map.remove(playerId);
    }
}

/**
 * Your Leaderboard object will be instantiated and called as such:
 * Leaderboard obj = new Leaderboard();
 * obj.addScore(playerId,score);
 * int param_2 = obj.top(K);
 * obj.reset(playerId);
 */


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Leaderboard {
    class Player{
        int id;
        int score;
        Player(){};
        Player(int _id, int _score){
            id = _id;
            score = _score;
        }
    }

    Map<Integer, Player> map = new HashMap<>();
    public Leaderboard() {
        
    }
    
    public void addScore(int playerId, int score) {
        if(!map.containsKey(playerId)){
            Player newPlayer = new Player(playerId, score);
            map.put(playerId, newPlayer);
        }else{
            map.get(playerId).score += score;
        }
    }
    
    public int top(int K) {
        PriorityQueue<Player> minHeap = new PriorityQueue<>(new Comparator<Player>() {
            @Override
            public int compare(Player p1, Player p2){
                return p1.score - p2.score;
            }
        });
        
        int sum = 0;
        for(Map.Entry<Integer, Player> en : map.entrySet()){
            sum += en.getValue().score;
            minHeap.add(en.getValue());
            if(minHeap.size()>K){
                sum -= minHeap.poll().score;
            }
        }

        return sum;
    }
    
    public void reset(int playerId) {
        map.get(playerId).score = 0;
    }
}
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)