【华为OD机试真题】斗地主跑得快 · 最长顺子判定（Java/Go）

一、题目

1. 题目描述

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

牌型定义（顺子）：

• 又称顺子，最少 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+213×4+2 张牌）。

2. 输入描述

• 第一行：当前手中的牌（字符串形式，用 – 分隔，如 3-3-4-5…）。
• 第二行：已经出过的牌（包括对手出的和自己出的牌，格式同上）。

3. 输出描述

• 输出最长的顺子。
• 判定规则：
• 优先选择长度最长的顺子。
• 如果有多个相同长度的顺子，输出牌面最大的那一个（即起始牌最大的那个）。
• 如果无法构成顺子（长度不足 5 或无连续牌），则输出 NO-CHAIN。

4. 示例数据

示例 1

输入：

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

输出：

9-10-J-Q-K

解析：
手牌减去已出牌后，剩余牌中包含 9, 10, J, Q, K，构成长度为 5 的顺子。虽然也有 3-4-5-6-7 等，但 9 开头的顺子牌面更大。

示例 2

输入：

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

输出

NO-CHAIN

解析：
剩余牌为 3,3,3,3,8,8,8,8，无法凑齐 5 张连续的牌，故无法构成顺子。

二、解题思路

🧩 步骤一：理解牌的大小顺序

题目给出牌的优先级：

3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A < 2 < B(小王) < C(大王)

但注意：顺子不能包含2、小王、大王，且不计花色。所以实际可用于顺子的牌只有：

3,4,5,6,7,8,9,10,J,Q,K,A → 共12种点数

💡 注意：A 在顺子里可以作为最大牌（如 3-A），但不能作为最小牌（如 A-2-3 不合法）。

🧩 步骤二：数据预处理

🧩 步骤三：枚举所有可能的顺子

由于顺子长度范围是 [5, 12]，我们可以：

• 枚举起始牌（从3开始到A结束）
• 对于每个起始牌，尝试向后延伸最多12张牌（只要不超过A）
• 检查该区间内每张牌是否都有至少1张可用
• 记录满足条件的最长顺子；若长度相同，取起始牌更大的（即牌面更大）

⚠️ 注意：顺子必须是连续的，中间不能断！

🧩 步骤四：输出结果

• 如果找到顺子 → 输出最长且牌面最大的那个（用原始牌面表示，如 “9-10-J-Q-K”）
• 否则 → 输出 “NO-CHAIN”

三、Code实现🖥️

1、Java ✅️

import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String hand = scanner.nextLine();
String played = scanner.nextLine();

// 牌值映射
Map<String, Integer> rankToIndex = new HashMap<>();
String[] ranks = {"3","4","5","6","7","8","9","10","J","Q","K","A"};
for (int i = 0; i < ranks.length; i++) {
rankToIndex.put(ranks[i], i);
}

// 统计手牌数量
Map<String, Integer> handCount = countCards(hand);
Map<String, Integer> playedCount = countCards(played);

// 计算剩余可用牌
Map<String, Integer> available = new HashMap<>();
for (String card : handCount.keySet()) {
int total = handCount.get(card);
int used = playedCount.getOrDefault(card, 0);
int left = total – used;
if (left > 0 && rankToIndex.containsKey(card)) { // 只保留3~A
available.put(card, left);
}
}

// 寻找最长顺子
String bestChain = null;
int maxLength = 0;
int maxStartIndex = -1;

// 枚举起始位置（0~11对应3~A）
for (int start = 0; start < ranks.length; start++) {
// 尝试从start开始，最长延伸到min(start+11, 11)
for (int len = 5; len <= Math.min(12, ranks.length – start); len++) {
boolean valid = true;
for (int i = 0; i < len; i++) {
String card = ranks[start + i];
if (!available.containsKey(card) || available.get(card) == 0) {
valid = false;
break;
}
}
if (valid) {
// 更新最优解：优先长度长，其次起始牌大（即start大）
if (len > maxLength || (len == maxLength && start > maxStartIndex)) {
maxLength = len;
maxStartIndex = start;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < len; i++) {
if (i > 0) sb.append("-");
sb.append(ranks[start + i]);
}
bestChain = sb.toString();
}
}
}
}

if (bestChain != null) {
System.out.println(bestChain);
} else {
System.out.println("NO-CHAIN");
}
}

private static Map<String, Integer> countCards(String cardsStr) {
Map<String, Integer> count = new HashMap<>();
String[] cards = cardsStr.split("-");
for (String card : cards) {
count.put(card, count.getOrDefault(card, 0) + 1);
}
return count;
}
}

2、Go ✅️

package main

import (
"fmt"
"strings"
)

func main() {
var hand, played string
fmt.Scanln(&hand)
fmt.Scanln(&played)

// 牌值映射
ranks := []string{"3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A"}
rankToIndex := make(map[string]int)
for i, r := range ranks {
rankToIndex[r] = i
}

// 统计手牌
handCount := countCards(hand)
playedCount := countCards(played)

// 计算剩余可用牌（只保留3~A）
available := make(map[string]int)
for card, total := range handCount {
used := playedCount[card]
left := total – used
if left > 0 {
if _, ok := rankToIndex[card]; ok {
available[card] = left
}
}
}

bestChain := ""
maxLength := 0
maxStartIndex := -1

// 枚举起始位置
for start := 0; start < len(ranks); start++ {
for length := 5; length <= 12 && start+length <= len(ranks); length++ {
valid := true
for i := 0; i < length; i++ {
card := ranks[start+i]
if available[card] == 0 {
valid = false
break
}
}
if valid {
if length > maxLength || (length == maxLength && start > maxStartIndex) {
maxLength = length
maxStartIndex = start
chain := strings.Join(ranks[start:start+length], "-")
bestChain = chain
}
}
}
}

if bestChain != "" {
fmt.Println(bestChain)
} else {
fmt.Println("NO-CHAIN")
}
}

func countCards(cardsStr string) map[string]int {
count := make(map[string]int)
cards := strings.Split(cardsStr, "-")
for _, card := range cards {
count[card]++
}
return count
}

四、 复杂度分析📈

时间复杂度：O(12×12) ≈ O(1)，因为牌种类固定
空间复杂度：O(1)，哈希表大小恒定

🚀 总结

强调本题考察的是“模拟+贪心”，适合练习字符串处理和状态统计。