最长的顺子 --- 华为od刷题

[斗地主]起源于湖北十堰房县，据说是一位叫吴修全的年轻人根据当地流行的扑克玩法“跑得快”改编的，如今已风靡整个中国，并流行于互联网上。

牌型：单顺，又称顺子，最少5张牌，最多12张牌(3…A)不能有2，也不能有大小王，不计花色。

例如： 3-4-5-6-7-8，7-8-9-10-J-Q，3-4-5-6-7-8-9-10-J-Q-K-A

可用的牌 3<4<5<6<7<8<9<10<J<Q<K<A<2<B(小王)<C(大王)，每种牌除大小王外有四种花色

(共有13×4+2张牌)

输入：

1. 手上有的牌
2. 已经出过的牌(包括对手出的和自己出的牌)

输出：

• 对手可能构成的最长的顺子(如果有相同长度的顺子，输出牌面最大的那一个)，
• 如果无法构成顺子，则输出 NO-CHAIN。

输入描述

输入的第一行为当前手中的牌

输入的第二行为已经出过的牌

输出描述

最长的顺子

用例

参考题库

华为OD机试备考攻略 以及题库目录分值说明 考点说明

题目描述

C++

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 将牌面映射为数字，方便处理
string mapToNumber(string pai) {
    if (pai == "J") return "11";
    if (pai == "11") return "J";
    if (pai == "Q") return "12";
    if (pai == "12") return "Q";
    if (pai == "K") return "13";
    if (pai == "13") return "K";
    if (pai == "A") return "14";
    if (pai == "14") return "A";
    return pai;
}

string getLongestChain(vector<string> myCards, vector<string> usedCards) {
    // 统计3~A的每张牌的数量，对应数组的索引3~14
    int cardCount[] = {0, 0, 0, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 0};

    // 从cardCount中去除myCards，剩下的就是对手的牌及数量
    for (string card : myCards) {
        int idx = stoi(mapToNumber(card));
        cardCount[idx]--;
    }

    // 从cardCount中去除usedCards，剩下的就是对手的牌及数量
    for (string card : usedCards) {
        int idx = stoi(mapToNumber(card));
        cardCount[idx]--;
    }

    // res用于保存顺子
    vector<string> res;
    // path用于保存连续的牌
    vector<string> path;

    for (int i = 3; i < sizeof(cardCount) / sizeof(int); i++) {
        // 从牌面3开始遍历，如果牌数量大于0，则加入path
        if (cardCount[i] > 0) {
            path.push_back(to_string(i));
        } else {
            // 如果遇到牌数量为0的，则连续的牌被中断，若此时连续的牌数量大于等于5，则可以形成顺子，我们将顺子加入res中
            if (path.size() >= 5) {
                string str;
                for (string idx : path) {
                    string pai = mapToNumber(idx);
                    str += pai + "-";
                }
                str.pop_back(); // 去掉最后一个"-"
                res.push_back(str);
            }
            // 清空path，为下一次连续的牌腾位置
            path.clear();
        }
    }

    // 如果没有顺子，则返回"NO-CHAIN"
    if (res.size() == 0) return "NO-CHAIN";

    // 如果有顺子，则先按照顺子长度升序，若长度相等，则按照字典序升序
    sort(res.begin(), res.end(), [](string a, string b) {
        return a.length() != b.length() ? a.length() < b.length() : a < b;
    });

    return res[0];
}

int main() {
    vector<string> myCards, usedCards;
    string line;
    getline(cin, line);
    size_t pos = 0;
    string token;
    while ((pos = line.find("-")) != string::npos) {
        token = line.substr(0, pos);
        myCards.push_back(token);
        line.erase(0, pos + 1);
    }
    myCards.push_back(line);

    getline(cin, line);
    pos = 0;
    while ((pos = line.find("-")) != string::npos) {
        token = line.substr(0, pos);
        usedCards.push_back(token);
        line.erase(0, pos + 1);
    }
    usedCards.push_back(line);

    cout << getLongestChain(myCards, usedCards) << endl;

    return 0;
}