使用哈希表记录每张牌以及出现次数,利用哈希表的大小来判断是哪种类型的牌
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
// 得出一个玩家的牌型
int kind(unordered_map<int, int> player) {
if (player.size() == 1) {
return 4; // 豹子
} else if (player.size() == 2) {
return 2; // 对子
}
auto iter = player.begin();
if (iter->first == next(iter)->first - 1 &&
iter->first == next(next(iter))->first - 2) {
return 3; // 顺子
}
return 1; // 普通牌型
}
// 牌型为豹子或顺子时根据值计算分数
int score(unordered_map<int, int> player) {
int res = 0;
for (const auto& [k, v] : player) {
res += k;
}
return res;
}
int main() {
string str1, str2;
while (cin >> str1 >> str2) {
if (str1.size() > 6 || str1.size() < 3 || str2.size() > 6 || str2.size() < 3) {
cout << -2 << endl;
continue;
}
unordered_map<int, int> player1, player2; // 记录玩家的牌以及每张牌的次数
for (int i = 0; i < str1.size(); i++) {
if (str1[i] == '1' && str1[i + 1] == '0') { // 牌10 的表示方法
player1[10]++;
i++;
} else if (str1[i] == 'J') {
player1[11]++;
} else if (str1[i] == 'Q') {
player1[12]++;
} else if (str1[i] == 'K') {
player1[13]++;
} else if (str1[i] == 'A') {
player1[14]++;
} else {
player1[str1[i] - '0']++;
}
}
for (int i = 0; i < str2.size(); i++) {
if (str2[i] == '1' && str2[i + 1] == '0') {
player2[10]++;
i++;
} else if (str2[i] == 'J') {
player2[11]++;
} else if (str2[i] == 'Q') {
player2[12]++;
} else if (str2[i] == 'K') {
player2[13]++;
} else if (str2[i] == 'A') {
player2[14]++;
} else {
player2[str2[i] - '0']++;
}
}
int kind1 = kind(player1), kind2 = kind(player2); // 得出两个玩家的牌型
if (kind1 > kind2) { // 先比较类型
cout << 1 << endl;
} else if (kind1 < kind2) {
cout << -1 << endl;
} else if (kind1 == 4 || kind1 == 3) { // 两者都是豹子或顺子时
int score1 = score(player1), score2 = score(player2); // 计算数值得分
if (score1 > score2) {
cout << 1 << endl;
} else if (score1 < score2) {
cout << -1 << endl;
} else {
cout << 0 << endl;
}
} else if (kind1 == 2) { // 两者都是对子时
int p1Max = 0, p2Max = 0; // 记录具体是哪个对子
for (const auto &[k, v] : player1) {
if (v == 2) {
p1Max = k;
}
}
for (const auto &[k, v] : player2) {
if (v == 2) {
p2Max = k;
}
}
if (p1Max > p2Max) {
cout << 1 << endl;
} else if (p1Max < p2Max) {
cout << -1 << endl;
} else {
cout << 0 << endl;
}
} else { // 两者都是普通牌型
int p1 = 0, p2 = 0; // 记录牌的大小
for (const auto &[k, v] : player1) { // 移位操作,是哪张牌就移多少位
p1 += 1 << k;
}
for (const auto &[k, v] : player2) {
p2 += 1 << k;
}
if (p1 > p2) {
cout << 1 << endl;
} else if (p1 < p2) {
cout << -1 << endl;
} else {
cout << 0 << endl;
}
}
}
return 0;
}
时间复杂度:
1、对于输入的两个字符串,需要遍历每个字符,因此字符串的长度为n,时间复杂度为O(n)。
2、对于遍历玩家的牌,需要遍历每个牌的次数,因此牌的种类数为m,时间复杂度为O(m)。
3、对于计算牌型和分数的函数,需要遍历玩家的牌,时间复杂度为O(m)。
4、对于比较牌型和分数的逻辑,时间复杂度为O(1)。
整个程序的时间复杂度为O(n + m)。
空间复杂度:
1、使用了两个unordered_map对象来记录玩家的牌和每张牌的次数,空间复杂度为O(m)。
2、其他变量的空间复杂度为O(1)。
整个程序的空间复杂度为O(m)。

京公网安备 11010502036488号