使用哈希表记录每张牌以及出现次数,利用哈希表的大小来判断是哪种类型的牌
#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)。