题目描述与示例

题目描述

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

牌型：单顺，又称顺子，最少 5 张牌，最多 12 张牌( 3...A )，不能有 2，也不能有大小王，不计花色。 例如：3-4-5-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(大王)， 每种牌除大小王外有 4 种花色(共有 13X4+2 张牌)

题目练习网址：https://www.algomooc.com/problem/P2830

输入描述

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

输出描述

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

示例一

输入

3-3-3-3-4-4-5-5-6-7-8-9-10-J-Q-K-A
4-5-6-7-8-8-8

输出

9-10-J-Q-K-A

示例二

输入

3-3-3-3-8-8-8-8
K-K-K-K

输出

NO-CHAIN

解题思路

比较常规的哈希表题目，但由于涉及到字符和数字之间的相互转换，即"J"、"Q"、"K"、"A"和数字11、12、13、14之间的相互转换，故代码比较长，需要细心完成。

数字和字母之间的映射

首先我们可以构建两个哈希表convert_dic和convert_dic2，分别完成从数字映射到字母，以及从字母映射到数字的工作。

# 构建将字符转换为数字的哈希映射
convert_dic = {f"{num}": num for num in range(3, 11)}
convert_dic["J"] = 11
convert_dic["Q"] = 12
convert_dic["K"] = 13
convert_dic["A"] = 14


# 构建将数字转换为字符的哈希映射
convert_dic2 = {num: f"{num}" for num in range(3, 11)}
convert_dic2[11] = "J"
convert_dic2[12] = "Q"
convert_dic2[13] = "K"
convert_dic2[14] = "A"

数据预处理

题目所给定的两行输入，分别代表手上已有的牌和已经出过的牌。

题目要求判断的对手手上可能拥有的最长顺子，其实就是要计算除了上述两种情况的剩余所有情况。

由于我们知道在一副牌中，每种牌只有最多只有4张，我们可以很容易判断出，剩余的牌的张数。

我们可以把上述两种情况进行合并，储存在同一个哈希表cnt_using_str中，表示所有已经使用过的牌的个数

from collections import Counter, defaultdict

# 将手上的牌、已经打出的牌储存为lst1和lst2
# 注意这里没有转换成数字，元素仍为字符串
lst1 = input().split("-")
lst2 = input().split("-")

# 使用计数器Counter，储存所有已经使用过的牌的个数
# 注意这里的key是str类型
cnt_using_str = Counter(lst1 + lst2)
# 如果存在2和大小王"B"、"C"
# 因为不影响顺子的判断，可以直接删去
del cnt_using_str["2"]
del cnt_using_str["B"]
del cnt_using_str["C"]

再将cnt_using_str里的key转化为int类型，对应的value不变，储存在一个新的哈希表cnt_using_num中。使用int类型来储存数据，是因为这样做更加方便我们进行顺子的判断

# 将cnt_using_str里的key转化为int类型，对应的value不变
# 储存在一个新的哈希表cnt_using_num中
cnt_using_num = {convert_dic[k]: v for k, v in cnt_using_str.items()}

顺子的判断

在关于顺子的判断中，我们可以先初始化3个变量来维护整个过程

# 初始化三个变量
# 当前顺子长度、最长顺子长度、最长顺子对应的答案ans
cur_length = 0
max_length = 0
ans = "NO-CHAIN"

由于顺子中包含的数字范围是3到14，我们可以做一个从3到14的for循环。

当cnt_using_num[i] == 4时，说明此时当前数字i已经完全用完，无法构成一个包含i的顺子。

当cnt_using_num[i] != 4时，说明此时当前数字i还有剩余，有可能构成一个包含i的顺子（之所以说有可能，是因为还需要考虑顺子的长度至少为5）。

因此当cnt_using_num[i] != 4时，我们可以令当前顺子长度cur_length += 1，来表示当前可能存在的顺子长度增加。

而当cnt_using_num[i] == 4时，由于此时已经不构成包含i的顺子了，而在i之前的若干已经判断过的数字i-cur_length, ..., i-3, i-2, i-1是可能能够构成顺子的。

此时我们有可能要更新答案。

如果cur_length ≥ 5，且cur_length ≥ max_length的时候，我们要更新ans和max_length。

在更新ans的时候，我们可以直接使用推导式结合前面构建的将数字转化为字母的哈希表convert_dic2来完成。而max_length要更新为当前已经得到的最长顺子长度cur_length

ans = "-".join(convert_dic2[j] for j in range(i-cur_length, i))
max_length = cur_length

综上我们可以得到以下代码

# 考虑3-14的所有数字
# 其中J、Q、K、A分别对应11、12、13、14
for i in range(3, 15):
    # 数字i被用完的情况，即在cnt_using_num中的值为4
    if cnt_using_num[i] == 4:
        # 若此时cur_length大于之前储存的max_length
        # 且cur_length大于等于5（顺子长度最低的要求）
        if cur_length >= max_length and cur_length >= 5:
            # 此时顺子为：i-cur_length, ..., i-3, i-2, i-1
            # 更新答案，注意这里要使用convert_dic2哈希表
            # 把数字重新转回字母后，再合并
            ans = "-".join(convert_dic2[j] for j in range(i-cur_length, i))
            max_length = cur_length
        # 顺子当前长度需要重置为0
        cur_length = 0
    # 数字i没被用完的情况，可以继续延长顺子
    # cur_length+1
    else:
        cur_length += 1

但是上述代码还存在一个小问题，就是当某一个以A为结尾（也就是i = 14）的顺子存在的时候，我们是无法正确地更新答案的。这是一个非常常见的边界值问题。

解决方案非常简单，我们只需要在遍历i的时候多遍历一个数字，不是遍历到14结束而是遍历到15结束。

当i = 15时，我们令其也进入更新答案的if分支，这样就可以将A作为结尾的顺子进行更新了。修改代码为

# 考虑3-15的所有数字
# 其中J、Q、K、A分别对应11、12、13、14
for i in range(3, 16):
    # 数字i被用完的情况，即在cnt_using_num中的值为4
    # 之所以把15也加入考虑
    # 是因为i取14时，由于后续没有仍然可以延长cur_length的牌
    # 会进入else中的分支，而无法实现ans的更新
    # 换句话说，当顺子最后一张牌是14的时候，需要做一次更新
    if cnt_using_num[i] == 4 or i == 15:
        # 若此时cur_length大于之前储存的max_length
        # 且cur_length大于等于5（顺子长度最低的要求）
        if cur_length >= max_length and cur_length >= 5:
            # 此时顺子为：i-cur_length, ..., i-3, i-2, i-1
            # 更新答案，注意这里要使用convert_dic2哈希表
            # 把数字重新转回字母后，再合并
            ans = "-".join(convert_dic2[j] for j in range(i-cur_length, i))
            max_length = cur_length
        # 顺子当前长度需要重置为0
        cur_length = 0
    # 数字i没被用完的情况，可以继续延长顺子
    # cur_length+1
    else:
        cur_length += 1

这种做法非常类似于做滑窗问题的时候，我们在数组或字符串末尾多填充一个占位元素或空字符，以处理包含最后一个元素的窗口的情况。大家可以多多总结比较。

代码

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频


from collections import Counter, defaultdict


# 将手上的牌、已经打出的牌储存为lst1和lst2
# 注意这里没有转换成数字，元素仍为字符串
lst1 = input().split("-")
lst2 = input().split("-")


# 使用计数器Counter，储存所有已经使用过的牌的个数
# 注意这里的key是str类型
cnt_using_str = Counter(lst1 + lst2)
# 如果存在2和大小王"B"、"C"
# 因为不影响顺子的判断，可以直接删去
del cnt_using_str["2"]
del cnt_using_str["B"]
del cnt_using_str["C"]


# 构建将字符转换为数字的哈希映射
convert_dic = {f"{num}": num for num in range(3, 11)}
convert_dic["J"] = 11
convert_dic["Q"] = 12
convert_dic["K"] = 13
convert_dic["A"] = 14


# 构建将数字转换为字符的哈希映射
convert_dic2 = {num: f"{num}" for num in range(3, 11)}
convert_dic2[11] = "J"
convert_dic2[12] = "Q"
convert_dic2[13] = "K"
convert_dic2[14] = "A"


# 将cnt_using_str里的key转化为int类型，对应的value不变
# 储存在一个新的哈希表cnt_using_num中
cnt_using_num = defaultdict(int)
for k, v in cnt_using_str.items():
    cnt_using_num[convert_dic[k]] = v


# 初始化三个变量
# 当前顺子长度、最长顺子长度、最长顺子对应的答案ans
cur_length = 0
max_length = 0
ans = "NO-CHAIN"

# 考虑3-15的所有数字
# 其中J、Q、K、A分别对应11、12、13、14
for i in range(3, 16):
    # 数字i被用完的情况，即在cnt_using_num中的值为4
    # 之所以把15也加入考虑
    # 是因为i取14时，由于后续没有仍然可以延长cur_length的牌
    # 会进入else中的分支，而无法实现ans的更新
    # 换句话说，当顺子最后一张牌是14的时候，需要做一次更新
    if cnt_using_num[i] == 4 or i == 15:
        # 若此时cur_length大于之前储存的max_length
        # 且cur_length大于等于5（顺子长度最低的要求）
        if cur_length >= max_length and cur_length >= 5:
            # 此时顺子为：i-cur_length, ..., i-3, i-2, i-1
            # 更新答案，注意这里要使用convert_dic2哈希表
            # 把数字重新转回字母后，再合并
            ans = "-".join(convert_dic2[j] for j in range(i-cur_length, i))
            max_length = cur_length
        # 顺子当前长度需要重置为0
        cur_length = 0
    # 数字i没被用完的情况，可以继续延长顺子
    # cur_length+1
    else:
        cur_length += 1

print(ans)

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] lst1 = scanner.nextLine().split("-");
        String[] lst2 = scanner.nextLine().split("-");
        
        Map<String, Integer> cntUsingStr = new HashMap<>();
        for (String card : lst1) {
            cntUsingStr.put(card, cntUsingStr.getOrDefault(card, 0) + 1);
        }
        for (String card : lst2) {
            cntUsingStr.put(card, cntUsingStr.getOrDefault(card, 0) + 1);
        }
        cntUsingStr.remove("2");
        cntUsingStr.remove("B");
        cntUsingStr.remove("C");
        
        Map<String, Integer> convertDic = new HashMap<>();
        for (int num = 3; num <= 10; num++) {
            convertDic.put(String.valueOf(num), num);
        }
        convertDic.put("J", 11);
        convertDic.put("Q", 12);
        convertDic.put("K", 13);
        convertDic.put("A", 14);
        
        Map<Integer, String> convertDic2 = new HashMap<>();
        for (int num = 3; num <= 10; num++) {
            convertDic2.put(num, String.valueOf(num));
        }
        convertDic2.put(11, "J");
        convertDic2.put(12, "Q");
        convertDic2.put(13, "K");
        convertDic2.put(14, "A");
        
        Map<Integer, Integer> cntUsingNum = new HashMap<>();
        for (Map.Entry<String, Integer> entry : cntUsingStr.entrySet()) {
            int num = convertDic.get(entry.getKey());
            cntUsingNum.put(num, entry.getValue());
        }
        
        int curLength = 0;
        int maxLength = 0;
        String ans = "NO-CHAIN";
        
        for (int i = 3; i <= 15; i++) {
            if (cntUsingNum.getOrDefault(i, 0) == 4 || i == 15) {
                if (curLength >= maxLength && curLength >= 5) {
                    List<String> sequence = new ArrayList<>();
                    for (int j = i - curLength; j < i; j++) {
                        sequence.add(convertDic2.get(j));
                    }
                    ans = String.join("-", sequence);
                    maxLength = curLength;
                }
                curLength = 0;
            } else {
                curLength++;
            }
        }
        
        System.out.println(ans);
    }
}

C++

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main() {
    string input1, input2;
    getline(cin, input1);
    getline(cin, input2);
    vector<string> lst1;
    vector<string> lst2;
    string card;
    for (char c : input1) {
        if (c == '-') {
            lst1.push_back(card);
            card = "";
        } else {
            card += c;
        }
    }
    lst1.push_back(card);
    card = "";
    for (char c : input2) {
        if (c == '-') {
            lst2.push_back(card);
            card = "";
        } else {
            card += c;
        }
    }
    lst2.push_back(card);
    
    map<string, int> cntUsingStr;
    for (string card : lst1) {
        cntUsingStr[card]++;
    }
    for (string card : lst2) {
        cntUsingStr[card]++;
    }
    cntUsingStr.erase("2");
    cntUsingStr.erase("B");
    cntUsingStr.erase("C");
    
    map<string, int> convertDic;
    for (int num = 3; num <= 10; num++) {
        convertDic[to_string(num)] = num;
    }
    convertDic["J"] = 11;
    convertDic["Q"] = 12;
    convertDic["K"] = 13;
    convertDic["A"] = 14;
    
    map<int, string> convertDic2;
    for (int num = 3; num <= 10; num++) {
        convertDic2[num] = to_string(num);
    }
    convertDic2[11] = "J";
    convertDic2[12] = "Q";
    convertDic2[13] = "K";
    convertDic2[14] = "A";
    
    map<int, int> cntUsingNum;
    for (auto entry : cntUsingStr) {
        int num = convertDic[entry.first];
        cntUsingNum[num] = entry.second;
    }
    
    int curLength = 0;
    int maxLength = 0;
    string ans = "NO-CHAIN";
    
    for (int i = 3; i <= 15; i++) {
        if (cntUsingNum[i] == 4 || i == 15) {
            if (curLength >= maxLength && curLength >= 5) {
                vector<string> sequence;
                for (int j = i - curLength; j < i; j++) {
                    sequence.push_back(convertDic2[j]);
                }
                ans = "";
                for (int j = 0; j < sequence.size(); j++) {
                    ans += sequence[j];
                    if (j < sequence.size() - 1) {
                        ans += "-";
                    }
                }
                maxLength = curLength;
            }
            curLength = 0;
        } else {
            curLength++;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_INPUT 200
#define MAX_CARDS 30

// 字符牌映射到对应数字值：3~10 为其本身，J=11, Q=12, K=13, A=14
int cardToNum(const char *card) {
    if (strcmp(card, "J") == 0) return 11;
    if (strcmp(card, "Q") == 0) return 12;
    if (strcmp(card, "K") == 0) return 13;
    if (strcmp(card, "A") == 0) return 14;
    return atoi(card); // 3~10
}

// 数字值映射回牌面字符串
const char* numToCard(int num) {
    switch (num) {
        case 11: return "J";
        case 12: return "Q";
        case 13: return "K";
        case 14: return "A";
        default: {
            static char buf[3];
            sprintf(buf, "%d", num);
            return buf;
        }
    }
}

// 分割字符串为数组
int split(const char *input, char cards[MAX_CARDS][5]) {
    int count = 0;
    int start = 0, idx = 0;
    char temp[5];
    while (1) {
        if (input[idx] == '-' || input[idx] == '\0') {
            strncpy(temp, input + start, idx - start);
            temp[idx - start] = '\0';
            strcpy(cards[count++], temp);
            if (input[idx] == '\0') break;
            start = idx + 1;
        }
        idx++;
    }
    return count;
}

int main() {
    char input1[MAX_INPUT], input2[MAX_INPUT];
    fgets(input1, sizeof(input1), stdin);
    fgets(input2, sizeof(input2), stdin);
    input1[strcspn(input1, "\n")] = '\0';
    input2[strcspn(input2, "\n")] = '\0';

    char cards1[MAX_CARDS][5];
    char cards2[MAX_CARDS][5];
    int count1 = split(input1, cards1);
    int count2 = split(input2, cards2);

    // 初始化每张牌的计数数组（索引对应牌面值，最多到14）
    int cardCount[15] = {0}; // 0-2 不用，3~14 有效

    // 累加两组牌出现的次数
    for (int i = 0; i < count1; i++) {
        int num = cardToNum(cards1[i]);
        if (num >= 3 && num <= 14) cardCount[num]++;
    }
    for (int i = 0; i < count2; i++) {
        int num = cardToNum(cards2[i]);
        if (num >= 3 && num <= 14) cardCount[num]++;
    }

    // 排除 2, B, C：因为这些无法构成顺子，cardToNum() 中未处理 B, C 即自然跳过
    cardCount[2] = 0;

    // 寻找最长顺子序列
    int curLength = 0, maxLength = 0;
    int endPos = -1; // 顺子结束位置（用于构造输出）

    for (int i = 3; i <= 15; i++) {
        if (i == 15 || cardCount[i] == 4) {
            if (curLength >= 5 && curLength >= maxLength) {
                maxLength = curLength;
                endPos = i;
            }
            curLength = 0;
        } else {
            curLength++;
        }
    }

    if (maxLength == 0) {
        printf("NO-CHAIN\n");
    } else {
        for (int i = endPos - maxLength; i < endPos; i++) {
            printf("%s", numToCard(i));
            if (i < endPos - 1) printf("-");
        }
        printf("\n");
    }

    return 0;
}

Node JavaScript

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let inputLines = [];
rl.on('line', (line) => {
    inputLines.push(line.trim());
    if (inputLines.length === 2) {
        solve(inputLines[0], inputLines[1]);
        rl.close();
    }
});

function solve(input1, input2) {
    const lst1 = input1.split("-");
    const lst2 = input2.split("-");
    
    // 统计两个输入中的所有牌数量
    const cntUsingStr = {};
    for (let card of [...lst1, ...lst2]) {
        cntUsingStr[card] = (cntUsingStr[card] || 0) + 1;
    }

    // 移除不能参与顺子的牌
    delete cntUsingStr["2"];
    delete cntUsingStr["B"];
    delete cntUsingStr["C"];

    // 字符到数字映射
    const convertDic = {};
    for (let i = 3; i <= 10; i++) convertDic[i.toString()] = i;
    convertDic["J"] = 11;
    convertDic["Q"] = 12;
    convertDic["K"] = 13;
    convertDic["A"] = 14;

    // 数字到字符映射
    const convertDic2 = {};
    for (let i = 3; i <= 10; i++) convertDic2[i] = i.toString();
    convertDic2[11] = "J";
    convertDic2[12] = "Q";
    convertDic2[13] = "K";
    convertDic2[14] = "A";

    // 数字频率统计
    const cntUsingNum = {};
    for (let card in cntUsingStr) {
        const num = convertDic[card];
        cntUsingNum[num] = cntUsingStr[card];
    }

    let curLength = 0, maxLength = 0, ans = "NO-CHAIN";

    for (let i = 3; i <= 15; i++) {
        if (cntUsingNum[i] === 4 || i === 15) {
            if (curLength >= 5 && curLength >= maxLength) {
                const sequence = [];
                for (let j = i - curLength; j < i; j++) {
                    sequence.push(convertDic2[j]);
                }
                ans = sequence.join("-");
                maxLength = curLength;
            }
            curLength = 0;
        } else {
            curLength++;
        }
    }

    console.log(ans);
}

Go

package main

import (
        "bufio"
        "fmt"
        "os"
        "strings"
)

func main() {
        reader := bufio.NewScanner(os.Stdin)
        reader.Scan()
        input1 := reader.Text()
        reader.Scan()
        input2 := reader.Text()

        lst1 := strings.Split(input1, "-")
        lst2 := strings.Split(input2, "-")

        cntUsingStr := make(map[string]int)
        for _, card := range append(lst1, lst2...) {
                cntUsingStr[card]++
        }

        delete(cntUsingStr, "2")
        delete(cntUsingStr, "B")
        delete(cntUsingStr, "C")

        convertDic := map[string]int{}
        for i := 3; i <= 10; i++ {
                convertDic[fmt.Sprintf("%d", i)] = i
        }
        convertDic["J"] = 11
        convertDic["Q"] = 12
        convertDic["K"] = 13
        convertDic["A"] = 14

        convertDic2 := map[int]string{}
        for i := 3; i <= 10; i++ {
                convertDic2[i] = fmt.Sprintf("%d", i)
        }
        convertDic2[11] = "J"
        convertDic2[12] = "Q"
        convertDic2[13] = "K"
        convertDic2[14] = "A"

        cntUsingNum := make(map[int]int)
        for card, count := range cntUsingStr {
                num := convertDic[card]
                cntUsingNum[num] = count
        }

        curLength := 0
        maxLength := 0
        ans := "NO-CHAIN"

        for i := 3; i <= 15; i++ {
                if cntUsingNum[i] == 4 || i == 15 {
                        if curLength >= 5 && curLength >= maxLength {
                                sequence := []string{}
                                for j := i - curLength; j < i; j++ {
                                        sequence = append(sequence, convertDic2[j])
                                }
                                ans = strings.Join(sequence, "-")
                                maxLength = curLength
                        }
                        curLength = 0
                } else {
                        curLength++
                }
        }

        fmt.Println(ans)
}

时空复杂度

时间复杂度：O(N)。主要是构建哈希表所需要的时间。

空间复杂度：O(1)。哈希表的长度不会大于15，可视为常数级别空间。