石头剪刀布游戏 - 华为OD统一考试

OD统一考试

分值： 100分

题解： Java / Python / C++

alt

题目描述

石头剪刀布游戏有 3 种出拳形状: 石头、剪刀、布。分别用字母 A,B,C 表示游戏规则：

出拳形状之间的胜负规则如下: A>B; B>C; C>A；左边一个字母，表示相对优势形状。右边一个字母，表示相对劣势形状。
当本场次中有且仅有一种出拳形状优于其它出拳形状，则该形状的玩家是胜利者。否则认为是平局。当发生平局，没有赢家。有多个胜利者时，同为赢家。

例如 1: 三个玩家出拳分别是A,B,C，由于出现三方优势循环(即没有任何一方优于其它出拳者)，判断为平局。

例如 2: 两个玩家，出拳分别是 A，B，出拳 A的获胜。

例如 3: 三个玩家，出拳全部是 A，判为平局。

输入描述

在一场游戏中，每个玩家的信息为一行。玩家数量不超过 1000。

每个玩家信息有 2 个字段，用空格隔开：

玩家 ID:一个仅由英文字母Q和数字组成的字符串。
出拳形状: 以英文大写字母表示，A、B、C 形状。

输出描述

输出为赢家的玩家 ID 列表(一个或多个)，每个 ID 一行，按字符串升序排列。

如果没有赢家，输出为“NULL"字符串。

示例1

输入：
abc1 A
xyz B输出：
abc1说明：
A比B有优势，abc1 胜出。

示例2

输入：
abc1 A
xyz A输出：
NULL说明：
没有优胜的出拳形状，平局。

示例3

输入：
abc1 A
def A
alic A
xyz B输出：
abc1
alic
def说明：
A为优胜方，有三个赢家。

题解

解题思路

题目要求找出赢家的玩家 ID 列表，或者输出 “NULL”。首先，我们需要将玩家的信息按照出拳形状分组，即分成A、B、C三组。然后，判断每一组中是否有且仅有一种出拳形状优于其它出拳形状，如果是，则该组中的玩家是胜利者。最后，将胜利者的玩家 ID 按照字符串升序排列输出。

代码描述

使用三个列表A、B、C分别表示出拳形状为A、B、C的玩家。
遍历输入，根据出拳形状将玩家信息分组。
判断每一组中是否有且仅有一种出拳形状优于其它出拳形状，如果是，则该组中的玩家是胜利者。
将胜利者的玩家 ID 按照字符串升序排列输出；如果没有胜利者，输出"NULL"。

复杂度分析

时间复杂度：假设有n个玩家，遍历输入的时间复杂度为O(n)。

空间复杂度：使用了三个列表A、B、C来存储玩家信息，空间复杂度为O(n)。

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
/*** @author code5bug*/
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);List<String> A = new ArrayList<>();List<String> B = new ArrayList<>();List<String> C = new ArrayList<>();while (scanner.hasNext()) {String user_id = scanner.next();String shape = scanner.next();if (shape.equals("A")) {A.add(user_id);} else if (shape.equals("B")) {B.add(user_id);} else {C.add(user_id);}}if (C.isEmpty() && !A.isEmpty() && !B.isEmpty()) {printResult(A);} else if (A.isEmpty() && !B.isEmpty() && !C.isEmpty()) {printResult(B);} else if (B.isEmpty() && !A.isEmpty() && !C.isEmpty()) {printResult(C);} else {System.out.println("NULL");}}private static void printResult(List<String> users) {Collections.sort(users);for (String user : users) {System.out.println(user);}}}

IDEA 控制台结束输入使用 Ctrl + D

Python

import sysA, B, C = [], [], []
for line in sys.stdin:user_id, shape = line.split()if shape == 'A':A.append(user_id)elif shape == 'B':B.append(user_id)else:C.append(user_id)def print_result(users):users.sort()print(*users, sep="\n", end="")if A and B and not C:   # 出 A 的人赢print_result(A)
elif B and C and not A:print_result(B)
elif C and A and not B:print_result(C)
else:print("NULL")

VS Code 控制台结束输入使用 Ctrl + Z

C++

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int main() {vector<string> A, B, C;string user_id, shape;while (cin >> user_id >> shape) {if (shape == "A") {A.push_back(user_id);} else if (shape == "B") {B.push_back(user_id);} else {C.push_back(user_id);}}auto printResult = [](const vector<string>& users) {vector<string> sortedUsers = users;sort(sortedUsers.begin(), sortedUsers.end());for (const auto& user : sortedUsers) {cout << user << endl;}};if (A.empty() && !B.empty() && !C.empty()) {printResult(B);} else if (B.empty() && !A.empty() &&  !C.empty()) {printResult(C);} else if (C.empty() && !A.empty() && !B.empty()) {printResult(A);} else {cout << "NULL" << endl;}return 0;
}