OD机试的算法题库里斗地主这个系列一直挺有意思。它们披着牌类游戏的外衣内核全是数据结构与基础算法今天要聊的“最长顺子判定”就是典型代表。题目要求在一组手牌里找出能组成的最长顺子C语言实现。很多人的第一反应是先把牌排序再扫一遍能做但C语言版本真正的分水岭在于处理多字符牌面10、J、Q、K、A的输入解析、牌面到数组下标的映射以及顺子边界条件的判断。这道题本质上考的是计数数组加最长连续区间的扫描先把3到A映射成12个计数位2和大小王直接剔除然后线性扫描找出连续非零的最长片段长度不足5张就判定无顺子。思路清晰代码量不大但埋了不少坑。这篇文章我把完整思路、C语言代码、边界用例和常见翻车点全部拆开讲清楚机试前刷到这道题的朋友可以直接照着复现。1. 考题拆解跑得快规则里的算法信号1.1 顺子规则帮你限定了数据范围跑得快和斗地主里的顺子规则基本一致至少5张点数连续的牌3是最小端A是最大端2和大小王都不参与顺子。这个规则直接带来一个关键结论——合法参与顺子的牌面只有3、4、5、6、7、8、9、10、J、Q、K、A这12种。12这个数字很微妙。它意味着我们可以用固定长度的数组来装手牌信息而不需要引入HashMap这种结构。C语言里数组就是天然的哈希表把牌面字符映射成下标用一个长度为12的int数组记录每个点数是否出现空间开销几乎可以忽略。另外要注意一个细节顺子是需要“连续点数”的而不是随便凑几张不同牌。比如手牌是3、5、7、9、J、K、A虽然点数都不重复但它们不连续无法构成任何顺子。所以核心逻辑不是“有多少种不同的牌”而是“这些牌在点数轴上能连成多长的一段”。1.2 题目真正想考的三种能力这类题目在机试里属于“中等偏易”的定位但它一次考察了三个基本功。第一个是输入解析。牌面不是单纯的一个字符10是两个字符J、Q、K、A又是字母如果用scanf(%c)去读非常容易出错。正确姿势是用scanf(%s)按字符串读取然后逐个比较。这个环节看起来简单实际考场上不少人在这里丢分尤其是C语言新手对字符串处理不熟缓冲区越界、比较逻辑写错的情况屡见不鲜。第二个是哈希统计。把牌面字符映射到数组下标本质上是设计一个转换函数。这个小函数写对了后面全部顺理成章写错了连续区间判断就全乱套。第三个是区间扫描。给定一个01数组0代表该点数未出现1代表出现找最长连续1的段。这个逻辑用双指针或分段扫描都行关键是要注意多个等长区间时取哪一个——题目通常会要求输出牌面最小的一组也就是从前往后第一个找到的最长区间。这三个能力串起来就是整道题的解题框架。我后面详细拆每一步。2. 思路选型计数数组加区间扫描为何最稳2.1 为什么不先排序再判断如果手牌是纯数字很多人会想到排序后遍历遇到相邻差值为1就累计长度否则断开重来。排序法的问题在于第一牌面里有J、Q、K、A这种字符牌字符的ASCII码并不等于牌面的大小顺序。比如字符A的ASCII码是65小于J的74如果直接按字符排序A会被排到3前面完全错误。你需要先做一层映射把所有牌面转换成数值这个转换本身就等于构建了一张哈希表。第二排序法对重复牌的处理很别扭。手牌里可能出现同一点数的牌不止一张多副牌混用或题目设定允许重复输入排序后连续的重复牌会干扰断点判断你得专门跳过重复项。而计数数组天然把相同点数的牌合并成一个存在位逻辑上简洁得多。第三排序的时间复杂度是O(n log n)虽然n不超过几十张但完全没有必要。计数数组扫一遍O(n)统计再扫一遍长度12的数组找区间总复杂度O(n 12)在机试场景里是更优解。2.2 区间扫描的核心逻辑核心逻辑可以写成这样用一个长度为12的计数数组cntcnt[i]为1表示点数为i3的牌在手牌中存在0表示31表示4以此类推为0表示不存在。然后从头开始扫跳过cnt为0的位置遇到cnt为1时就继续往右看能连续走到多远记录下这段的起始位置和长度最后在所有连续段里挑最长的那段。这里有一个非常容易忽略的细节多个等长连续段时题目一般要求输出数值较小的一组。由于牌面是从3递增到A我们在扫描时从左往右遍历如果条件是len maxLen才更新那么等长的段不会覆盖前一个保留下来的一定是更靠左、数值更小的那一段。如果写成len maxLen就会取到更靠右的段输出就错了。这个失误在失分点上排名很高。扫描完成后如果最长段长度小于5按规则不能构成顺子输出无顺子的约定标志否则把该段所有牌面拼成一行输出。2.3 复杂度账要算清楚时间上读入每张牌做一次映射O(n)扫描12个计数位最多12次循环常数级别。总时间复杂度O(n)n是手牌数量题目最多几十张牌跑起来是微秒级。空间上一个长度12的int数组存计数几个临时变量空间复杂度O(1)固定12个单元不随输入规模变化。相比排序法需要额外数组存储转换后的数值这版方案在内存上也更干净。这道题如果放在LeetCode里难度大概在简单到中等之间。但在OD机试里它考的是“能不能一次写对”而不是“能不能想出解法”。因为思路并不难难的是C语言实现细节不翻车。3. C语言实现全解析3.1 输入解析与牌面映射函数先把输入这块拿下。牌面有12种合法值加上2、小王、大王这些不参与顺子的牌。我建议用字符串逐个读取每个字符串存到一个缓冲区里然后调用映射函数判断。注意10这个牌面占两个字符缓冲区至少要能装3个字节两个字符加结尾的\0。#include stdio.h #include string.h int cardIndex(const char *s) { if (strcmp(s, 3) 0) return 0; if (strcmp(s, 4) 0) return 1; if (strcmp(s, 5) 0) return 2; if (strcmp(s, 6) 0) return 3; if (strcmp(s, 7) 0) return 4; if (strcmp(s, 8) 0) return 5; if (strcmp(s, 9) 0) return 6; if (strcmp(s, 10) 0) return 7; if (strcmp(s, J) 0) return 8; if (strcmp(s, Q) 0) return 9; if (strcmp(s, K) 0) return 10; if (strcmp(s, A) 0) return 11; return -1; // 2、小王、大王等不参与顺子 }这里用了一长串strcmp判断看起来有点笨但机试环境下这是最稳的写法逻辑直白不容易写错。你也可以用switch配合单个字符判断但10这个两位字符串会让switch变得别扭反而增加出错概率。映射函数返回-1的分支要处理干净。跑得快里2是单牌里最大的但它不能出现在顺子中大小王同样不能所以这些牌读入后直接忽略不写入计数数组。在机试的测试数据里大小王通常不会出现但万一出现返回-1的逻辑也能兜住。紧接着在主函数里循环读入手牌逐张处理int main() { char buf[8]; int cnt[12] {0}; while (scanf(%s, buf) ! EOF) { int idx cardIndex(buf); if (idx 0) { cnt[idx] 1; } } // 后面接区间扫描逻辑 }cnt[idx] 1这行有个隐含语义我们只关心这个点数是否存在不关心它有几张。因为顺子由不同点数各一张组成手牌里有3张7和手牌里有1张7对顺子的贡献是一样的。如果题目改成“连对”或者“飞机带翅膀”那就另当别论但最长顺子判定不需要这个维度。scanf读到EOF结束天然适合OJ的管道输入模式。有些机试环境输入带换行和尾部空格这种循环写法都能正确处理。3.2 核心扫描逻辑统计完成后进入本题的心脏找最长连续非零段。完整代码片段如下int maxLen 0; int start -1; int i 0; while (i 12) { if (cnt[i] 0) { i; continue; } int j i; while (j 12 cnt[j] 0) { j; } int len j - i; if (len maxLen) { maxLen len; start i; } i j; }这个双循环的结构外层负责定位每段连续1的起点内层负责从起点一路推进到这段的终点。因为内层跳过的位置不会重复扫描整体是线性时间。注意len maxLen用的是严格大于。这样当出现两个长度相同的顺子候选时靠左的先被记录靠右的不会覆盖它。按题目要求输出牌面最小的那组顺子这个细节很关键。还有一个细节j循环结束后直接把i赋值为j。这是必要的优化也是逻辑完备性的体现——i到j-1这一段已经被扫过不可能再成为新的候选起点。如果不这么做i每次只加1就会出现大量重复扫描虽然12个元素影响不大但代码习惯不好遇到更长的数组时容易出性能问题。扫描结束后对结果做有效性判断if (maxLen 5) { printf(No\n); return 0; }顺子最少5张牌这是规则底线。有些变体题目可能要求输出-1或空行以题目输出说明为准我这里按常见的No处理。3.3 输出格式控制输出是这道题另一个容易翻车的位置。要求输出的牌面之间用空格分隔行尾不能有多余空格很多OJ对行尾空格判错。const char *names[] { 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A }; for (int k start; k start maxLen; k) { if (k start) { printf( ); } printf(%s, names[k]); } printf(\n);if (k start)这个判断确保第一个牌面前不输出空格后续每张牌前补一个空格。这个手法比先拼字符串再统一输出简单也不容易出错。有人喜欢在循环里先输出牌再输出空格结果最后多了一个尾随空格提交后提示Presentation Error非常冤枉。names数组的下标与cardIndex的返回值一一对应这是整套方案能跑通的关键。映射进去是数字输出时映射回字符串两次映射是反向但同构的。完整代码拼起来就是前面几个片段合集约50行。这类长度在机试里属于非常友好留出大量时间给后面的难题。4. 用例实测与避坑记录4.1 五组边界用例跑一遍我在本地实际编译运行了几组数据这里直接列出来对照分析。输入手牌统计后关键情况预期输出3 4 5 6 7 8 9 10 J Q K A 23到A全部出现2被忽略连续12位3 4 5 6 7 8 9 10 J Q K A3 4 5 6 8 9 10 J Q K A3-6连续4张8-A连续7张8 9 10 J Q K AA 2 3 4 5 6 7 8 9 10 J Q KA单独3-K连续11张3 4 5 6 7 8 9 10 J Q K3 4 5 6 2 J Q K A3-6四张J-A四张均不足5No3 3 4 5 6 7 7 8 9 10 J Q K A重复3和7不额外增长顺子长度3 4 5 6 7 8 9 10 J Q K A第一组是最基础的完整顺子测试代码的映射和扫描主链路。第二组验证两点之间的断点能否正确切割结果应该取右边更长的8-A段。第三组很有意思因为2不能进顺子把A和3-K隔成了两段A单独长度13-K长度11输出较长的那段。第四组验证长度不足5时的处理两个连续段都只有4张输出No。第五组带重复牌3有两张、7有两张计数数组把它们折叠成一个存在位顺子长度不变仍然是完整的12张。第二组和第三组是用来验证“从前往后扫描保留靠左最长段”逻辑的好用例。如果代码里错写成第一组不受影响但遇到两个等长段时就会选靠右的丢失正确性。4.2 高频报错与排查思路我在练习和帮别人review代码时发现这道题的报错高度集中在几个地方基本可以总结成一张速查表。第一个高频坑把2当顺子牌。有些版本规则中2可以和A连成A-2-3的循环顺子但斗地主和跑得快明确不允许2是单牌里最大的不参与顺子。如果映射函数里给2返回了12计数数组长度就要变13输出阶段还得考虑2的位置整套逻辑全乱。处理方式就是映射函数对2返回-1直接忽略。第二个高频坑统计时写成cnt[idx]而不是cnt[idx] 1。这两个在“判断是否存在”的语义下结果一致因为后续判断用的是cnt[j] 0。但如果你不小心用cnt[j] 1判断连续手牌里某点数出现两次就会导致判断失败。我的建议是统计阶段直接 1语义更精准不给后续留隐患。第三个高频坑char buf开小了。char buf[3]装不下字符串10因为还需要一个字节存\0至少要char buf[4]或更大。这个错误属于C语言经典越界机试编译器不一定报错但内存里相邻数据被覆盖后可能出现各种诡异现象比如cnt数组里的值莫名变化。排查时先看缓冲区大小。第四个高频坑忘了#include string.hstrcmp和strlen编译不过。机试环境通常是Linux GCC头文件缺失会在编译阶段直接报错心态容易崩。提前在本地把完整代码编译好再提交。第五个高频坑连续区间判断时越界。内层while循环的条件j 12 cnt[j] 0顺序不能反。如果把cnt[j] 0放前面当j等于12时会发生数组越界读取读到的可能是上一次循环残留的脏数据导致偶发错误。这个错误有时候能通过大部分测试用例只在特定输入下暴露排查起来非常恶心。养成把下标判断写在最前面的习惯。4.3 机试环境下的提分细节关于OD机试的C语言版本有几点经验对新人有帮助。输入读取上用while (scanf(%s, buf) ! EOF)是最省心的选择不要用gets。gets在C11标准里已经被移除机试环境不一定支持而且它不检查缓冲区长度很容易越界。scanf配合%s天然按空白字符切分正好应对带空格的手牌输入。测试策略上写完代码不要急着提交。先在本地跑一遍我上面列的五组用例再自己补几组极端数据比如全部是2和大小王、只有4张连续牌、一张牌都没有空输入。空输入时cnt全零maxLen保持0输出No代码不会崩。这些极端数据能提前暴露大部分边界问题。代码风格上变量名用有意义的单词cnt、start、maxLen一眼能看懂。机试改卷虽然不看你代码风格但实际调试时作用巨大。我见过不少人用a、b、c这种命名出问题后自己都看不懂更别提快速定位了。时间分配上这道题正常应该15分钟内写完并测试完。如果卡住超过20分钟建议先跳过做后面的题最后再回来补。机试是整体算分不要在单题上无限消耗。5. 踩坑后的个人体会这类牌类题做多了会发现一个规律游戏规则越复杂算法核心往往越简单。斗地主系列看着唬人剥掉外壳后就是哈希统计加区间扫描的组合拳。把这道最长顺子判定吃透同系列的“连对判断”“飞机判定”思路都是相通的区别只在统计维度从单张变成成对、成三张。我个人练习这类题时习惯先把牌面映射表写在纸上再动手敲代码确保3到A的12个映射没有错位。这个准备工作看起来多余实际能省下大量调试时间。另一个习惯是每次写完扫描逻辑都会问自己一句如果存在两个等长顺子这段代码取的是哪一个时刻把题目输出要求放在嘴边就不容易写出方向性错误的代码。最后给正在备考的朋友一个建议机试的题量和难度都在一个可控范围内真正拉开差距的不是会不会做而是能不能稳定一次做对。把边界条件当成一等公民对待每道题都在本地过一遍极端用例再交这个习惯会让你少丢很多冤枉分。