题目链接

玩家积分榜系统

题目描述

你需要设计一个玩家积分榜系统，支持四种操作：

  1. 更新/插入 (1 NAME SCORE): 更新或插入玩家 NAME 的积分为 SCORE。成功后输出 "OK"。
  2. 查询 (2 NAME): 查询玩家 NAME 的积分。如果存在，输出其积分；否则输出 "Not found"。
  3. 删除 (3 NAME): 删除玩家 NAME 的记录。如果成功，输出 "Deleted successfully"；否则输出 "Not found"。
  4. 统计 (4): 输出当前积分榜上的玩家总数。

这是一个 核心代码模式 的题目，你需要实现题目指定的四个函数，并在函数内部直接打印结果。

输入描述:

  • 第一行是一个整数 Q，表示操作总数。
  • 接下来 Q 行，每行是一个操作请求。

输出描述:

  • 根据每个操作的要求，输出相应的结果，每个结果占一行。

示例: 输入:

5
1 wangzai 10
2 wangzai
3 wangzai
2 wangzai
4

输出:

OK
10
Deleted successfully
Not found
0

解题思路

这个问题要求我们实现一个动态的键值对存储系统，其中键是玩家的 NAME (字符串)，值是他们的 SCORE (整数)。这是 哈希表 (Hash Map / Dictionary) 的一个典型应用场景。

核心数据结构： 我们需要一个全局的哈希表来存储所有玩家的积分。

  • C++: std::map<string, int> 或 std::unordered_map<string, int>。unordered_map 通常提供更快的平均性能(O(1))，而map提供有序遍历(O(log n))。对于本题，两者均可，unordered_map 更优。
  • Java: java.util.HashMap<String, Integer>。
  • Python: dict。

这个哈希表将作为我们所有操作的共享数据存储。

各操作的实现:

  1. insertOrUpdateScore(name, score):

    • 直接使用哈希表的赋值/插入功能。如果 name 已存在，其对应的值会被更新为 score；如果不存在，则会创建一个新的键值对。
    • 例如 scoreboard[name] = score; (C++/Python) 或 scoreboard.put(name, score); (Java)。
    • 操作完成后，打印 "OK"。

  2. queryScore(name):

    • 在哈希表中查找键 name。
    • 如果找到，打印对应的积分值。
    • 如果未找到，打印 "Not found"。

  3. deletePlayer(name):

    • 在哈希表中查找并尝试删除键 name。
    • 检查删除操作是否成功（即，name 是否原本存在）。
    • 如果成功删除，打印 "Deleted successfully"。
    • 如果 name 原本就不存在，打印 "Not found"。

  4. countPlayers():

    • 直接返回哈希表的大小（size/length）。
    • 打印这个数字。

代码

#include <unordered_map>
// 将哈希表定义为全局变量，以便所有函数共享
unordered_map<string, int> scoreboard;

void insertOrUpdateScore(const string &name, int score) {
    scoreboard[name] = score;
    cout << "OK" << endl;
}

void queryScore(const string &name) {
    if (scoreboard.count(name)) {
        cout << scoreboard[name] << endl;
    } else {
        cout << "Not found" << endl;
    }
}

void deletePlayer(const string &name) {
    if (scoreboard.erase(name)) { // erase返回删除的元素数量
        cout << "Deleted successfully" << endl;
    } else {
        cout << "Not found" << endl;
    }
}

void countPlayers() {
    cout << scoreboard.size() << endl;
}

import java.util.HashMap;
import java.util.Map;
// 将哈希表定义为静态成员变量，以便所有静态方法共享
static Map<String, Integer> scoreboard = new HashMap<>();

public static void insertOrUpdateScore(String name, int score) {
    scoreboard.put(name, score);
    System.out.println("OK");
}

public static void queryScore(String name) {
    if (scoreboard.containsKey(name)) {
        System.out.println(scoreboard.get(name));
    } else {
        System.out.println("Not found");
    }
}

public static void deletePlayer(String name) {
    if (scoreboard.remove(name) != null) { // remove返回被删除的值，如果键不存在则返回null
        System.out.println("Deleted successfully");
    } else {
        System.out.println("Not found");
    }
}

public static void countPlayers() {
    System.out.println(scoreboard.size());
}

# 将字典定义为全局变量
scoreboard = {}

def insert_or_update_score(name, score):
    """插入或更新玩家的分数"""
    scoreboard[name] = score
    print("OK")

def query_score(name):
    """查询玩家的分数"""
    if name in scoreboard:
        print(scoreboard[name])
    else:
        print("Not found")

def delete_player(name):
    """删除玩家记录"""
    if name in scoreboard:
        del scoreboard[name]
        print("Deleted successfully")
    else:
        print("Not found")

def count_players():
    """统计玩家总数"""
    print(len(scoreboard))

算法及复杂度

  • 算法: 哈希表
  • 时间复杂度:
    • 对于所有四种操作（插入/更新、查询、删除、统计大小），哈希表的平均时间复杂度都是 。
    • C++ std::map 的版本会是 ，其中 N 是玩家数量。
    • 对于一个包含 Q 个操作的序列，总时间复杂度为 ，其中 L 是字符串NAME的平均长度（因为哈希/比较字符串需要时间），在哈希表操作为O(1)的情况下。
  • 空间复杂度: ，其中 N 是积分榜上玩家的最大数量，L 是NAME的平均长度。空间用于存储玩家的名字和分数。