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

一、题目

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. 输出描述

• 输出最长的顺子。
• 判定规则：
  1. 优先选择长度最长的顺子。
  2. 如果有多个相同长度的顺子，输出牌面最大的那一个（即起始牌最大的那个）。
  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 张连续的牌，故无法构成顺子。

二、核心解题思路 (C 语言特化)💡

1. 牌面数字化 (Mapping)

C 语言无法直接比较'J'和'10'的大小。我们需要建立一个映射表，将字符串转换为0~11的整数索引：

• 3→0,4→1, ...,9→6,10→7,J→8,Q→9,K→10,A→11。
• 技巧：使用两个平行数组CARD_STR[]和查找函数，或者简单的if-else/switch进行转换。

2. 布尔标记数组 (Boolean Flag Array)

由于牌面种类固定且很少（仅12种），我们不需要动态链表或哈希表。

• 定义一个长度为 12 的整型数组int has_card[12]。
• 去重逻辑：
  1. 解析手牌，将对应的索引位置标记为1(has_card[idx] = 1)。重复标记无所谓，天然去重。
  2. 解析已出牌，将对应的索引位置标记为0(has_card[idx] = 0)。
• 结果：has_card数组变成了一个连续性位图，1代表该点数的牌可用，0代表不可用。

3. 线性扫描找最长连续段

遍历has_card[0...11]：

• 维护current_len(当前连续长度) 和current_start(当前起点)。
• 遇到1：长度 +1。
• 遇到0或结束：结算上一段。
  • 若current_len >= 5，则对比最优解。
  • 优先级策略：
    • 若current_len > best_len：更新最优解。
    • 若current_len == best_len：由于我们是从左向右（从小到大）遍历，后遇到的连续段起点一定更大。因此，只要长度相等，直接覆盖即可满足“起始牌最大”的要求。
    • 简化逻辑：if (current_len >= best_len)即可更新。

三、C 语言完整代码实现

#include <stdio.h> #include <string.h> #include <stdlib.h> // 1. 定义牌面映射表 const char *CARD_STR[] = {"3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A"}; #define CARD_COUNT 12 // 辅助函数：将字符串牌面转为索引 (0-11)，失败返回 -1 int get_card_index(const char *card) { for (int i = 0; i < CARD_COUNT; i++) { if (strcmp(card, CARD_STR[i]) == 0) { return i; } } return -1; } // 辅助函数：解析字符串并更新标记数组 // flag: 1 表示添加手牌，0 表示移除已出牌 void parse_and_update(const char *input_str, int *available, int flag) { if (input_str == NULL || strlen(input_str) == 0) return; // 复制字符串以便 strtok 修改 (strtok 会破坏原字符串) char *buffer = strdup(input_str); if (!buffer) return; char *token = strtok(buffer, "-"); while (token != NULL) { int idx = get_card_index(token); if (idx != -1) { available[idx] = flag; // 注意：如果是添加手牌，多次出现设为1即可（去重） // 如果是移除，设为0即可（即使原本没有也不影响） } token = strtok(NULL, "-"); } free(buffer); } void solve() { char hand_line[1024]; char played_line[1024]; // 读取两行输入 if (!fgets(hand_line, sizeof(hand_line), stdin)) return; if (!fgets(played_line, sizeof(played_line), stdin)) return; // 去除换行符 hand_line[strcspn(hand_line, "\n")] = 0; played_line[strcspn(played_line, "\n")] = 0; // 2. 初始化可用牌标记数组 (0:不可用, 1:可用) int available[CARD_COUNT] = {0}; // 3. 处理手牌 (标记为 1) parse_and_update(hand_line, available, 1); // 4. 处理已出牌 (标记为 0) parse_and_update(played_line, available, 0); // 5. 线性扫描寻找最长顺子 int best_len = 0; int best_start = -1; int current_len = 0; int current_start = -1; for (int i = 0; i < CARD_COUNT; i++) { if (available[i] == 1) { if (current_len == 0) { current_start = i; } current_len++; } else { // 连续性中断，结算 if (current_len >= 5) { // 核心逻辑：长度更长，或者长度相等（此时当前起点一定更大） if (current_len >= best_len) { best_len = current_len; best_start = current_start; } } current_len = 0; current_start = -1; } } // 处理末尾连续的片段 if (current_len >= 5) { if (current_len >= best_len) { best_len = current_len; best_start = current_start; } } // 6. 输出结果 if (best_len == 0) { printf("NO-CHAIN\n"); } else { // 构造输出字符串 // 题目限制最多12张，这里直接输出找到的连续段即可 for (int i = 0; i < best_len; i++) { printf("%s", CARD_STR[best_start + i]); if (i < best_len - 1) { printf("-"); } } printf("\n"); } } int main() { solve(); return 0; }

四、代码深度解析🔍

1. 字符串解析 (strtok)

C 语言处理-分隔的字符串，标准做法是使用<string.h>中的strtok函数。

• 注意：strtok会修改原字符串，所以先用strdup复制一份输入字符串到堆内存，处理完后记得free，防止内存泄漏。
• 兼容性：strdup是 POSIX 标准函数，大多数 OJ 环境（包括华为 OD）都支持。如果环境极其严格不支持strdup，可以手动malloc+strcpy。

2. 标记数组的去重魔法

int available[CARD_COUNT] = {0}; // 手牌来了：available[idx] = 1; // 又一张同样的牌：available[idx] = 1; (值不变，天然去重) // 已出牌来了：available[idx] = 0; (无论之前是几，现在都没了)

这种状态标记法避免了复杂的计数逻辑，完美契合“顺子只看有无，不看数量”的规则。

3. 优先级判定的巧妙简化

题目要求：长度相同，起始牌越大越好。

• 我们的循环是for (int i = 0; i < 12; i++)，即从3扫到A。
• 假设先发现3-4-5-6-7(len=5, start=0)。
• 后发现9-10-J-Q-K(len=5, start=5)。
• 当扫到第二段时，current_len (5) >= best_len (5)成立。
• 执行更新：best_start变为 5。
• 结论：因为遍历方向是从小到大，后出现的同长度顺子，其起点必然更大。所以直接用>=覆盖，即可同时满足“最长”和“同长取大”两个条件。

4. 内存安全

• 使用fgets替代scanf读取整行，避免缓冲区溢出和处理空格分隔的麻烦。
• strcspn用于快速去除末尾的换行符\n。

五、避坑指南⚠️

1. "10" 的特殊性：
   • 10是两个字符，不能用char存储，必须用char*或string比较。代码中使用strcmp完美解决。
2. 输入为空或格式错误：
   • 代码中增加了strlen检查和fgets返回值检查，增强鲁棒性。
3. 边界情况：
   • 如果最长顺子一直延续到数组最后一个元素 (A, index 11)，循环内的else分支不会触发。必须在循环结束后单独判断一次current_len，否则会漏掉以A结尾的顺子。
4. 无解输出：
   • 务必检查best_len是否仍为 0，若是则输出NO-CHAIN。

六、复杂度分析📊

• 时间复杂度：
  • 字符串解析： O(N+M) ，其中 N,M 分别为手牌和已出牌的字符串长度。
  • 查找顺子：固定循环 12 次， O(1) 。
  • 总计： O(N+M) ，线性效率。
• 空间复杂度：
  • 标记数组固定 12 个整数， O(1) 。
  • 字符串缓冲区取决于输入长度，但在处理过程中是线性的。

七、总结

这道题在 C 语言中考察了三个关键点：

1. 数据映射：如何将非数字的枚举类型（扑克牌）转化为可计算的整数索引。
2. 状态压缩：利用小规模固定数组代替复杂的集合数据结构。
3. 逻辑简化：利用遍历顺序的特性，将复杂的多条件排序简化为单次扫描覆盖。

掌握这种“映射 + 标记数组 + 一次扫描”的模式，不仅能解决扑克牌问题，还能应对各类“最长连续子序列”、“区间合并”等算法题。祝各位 C 语言选手机考顺利，代码一次 AC！