最新华为OD机试真题-石头剪刀布游戏(100分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新 华为OD机试-D卷 的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

=> LYA与朋友们的石头剪刀布游戏(100分) <=

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🪐 LYA与朋友们的石头剪刀布游戏

问题描述

LYA 和朋友们在玩石头剪刀布游戏。游戏中有三种出拳形状：石头、剪刀、布，分别用字母 、、 表示。

游戏规则如下：

1. 出拳形状之间的胜负关系： 胜 ， 胜 ， 胜 。
2. 当一轮游戏中有且仅有一种出拳形状优于其他所有出拳形状时，使用该形状的玩家获胜。否则判定为平局。
3. 平局时没有赢家。有多个玩家获胜时，他们同为赢家。

例如：

• 三个玩家出拳分别为 、、，由于出现循环优势，判断为平局。
• 三个玩家出拳分别为 、，出拳 的玩家获胜。
• 三个玩家出拳均为 ，判断为平局。

输入格式

每个玩家的信息占一行，包含两个字段，用空格隔开：

1. 玩家 ：仅由英文字母和数字组成的字符串。
2. 出拳形状：英文大写字母 、、 之一。

玩家数量不超过 。

输出格式

输出获胜玩家的 列表，每个 占一行，按字符串字典序排列。如果没有赢家，输出 NULL。

样例输入

abc1 A
xyz B

样例输出

abc1

样例输入

abc1 A
xyz A

样例输出

NULL

样例输入

abc1 A
def A
alic A 
xyz B

样例输出

abc1
alic
def

数据范围

• 玩家数量不超过 。
• 玩家 长度不超过 ，仅由英文字母和数字组成。

题解

本题可以用哈希表来解决。具体思路如下：

1. 用哈希表统计每种出拳形状对应的玩家列表。
2. 根据哈希表的大小判断游戏结果：
   • 如果只有一种出拳形状，或者三种出拳形状都有玩家选择，则判定为平局，输出 NULL。
   • 如果有两种出拳形状：
     • 如果没有 ，则 获胜；
     • 如果没有 ，则 获胜；
     • 如果没有 ，则 获胜。
   • 将获胜玩家列表按字符串字典序排序并输出。

时间复杂度 ，其中 为玩家数量。排序获胜玩家列表需要 的时间复杂度。

空间复杂度 。哈希表和获胜玩家列表的空间复杂度均为 。

参考代码

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    unordered_map<char, vector<string>> ht;
    string id;
    char gesture;

    while (cin >> id >> gesture) {
        if (gesture < 'A' || gesture > 'C') {
            cout << "NULL" << endl;
            return 0;
        }
        ht[gesture].push_back(id);
    }

    switch (ht.size()) {
        case 1:
        case 3:
            cout << "NULL" << endl;
            break;
        case 2:
            vector<string> ans;
            if (!ht.count('A')) {
                ans = ht['B'];