使用哈希表记录每张牌以及出现次数,利用哈希表的大小来判断是哪种类型的牌

#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)。