1. 项目背景与核心需求斗地主和跑得快作为国内最流行的扑克牌游戏其算法实现一直是编程面试中的经典题型。华为OD机试真题选择这个题材既考察了候选人的基础编码能力也检验了对游戏规则的理解和逻辑抽象水平。这道题的核心在于给定一组牌型可能包含重复牌如何高效判断其中能够组成的最长顺子。顺子是指连续数字组成的牌组比如3-4-5-6-7。在实际游戏中掌握这个判断技巧能帮助玩家快速评估手牌价值。2. 问题分析与算法选型2.1 牌型表示与预处理首先需要将扑克牌转换为可计算的数字形式。标准做法是数字牌直接取数值3→3J→11特殊牌做映射A→142→15大小王通常不计入顺子unordered_mapchar, int cardValue { {3,3}, {4,4}, {5,5}, {6,6}, {7,7}, {8,8}, {9,9}, {T,10}, {J,11}, {Q,12}, {K,13}, {A,14}, {2,15} };注意跑得快规则中A通常作为1使用需要根据题目要求确认。这里假设A作为14处理。2.2 关键算法思路最长顺子问题可以转化为在给定的数字序列中找出最长的连续数字段。这与LeetCode 128题最长连续序列高度相似但需要考虑以下特殊点牌可能有重复如多张5顺子通常要求至少5张连续牌需要处理牌型的特殊规则如2不参与顺子推荐采用排序滑动窗口的解法时间复杂度O(nlogn)空间复杂度O(1)适合机试场景。3. C实现详解3.1 完整代码实现#include iostream #include vector #include algorithm #include unordered_map using namespace std; vectorint getLongestStraight(vectorint cards) { if (cards.size() 5) return {}; sort(cards.begin(), cards.end()); int maxLen 1, currentLen 1; int start 0, maxStart 0; for (int i 1; i cards.size(); i) { if (cards[i] cards[i-1]) continue; // 跳过重复牌 if (cards[i] cards[i-1] 1) { currentLen; if (currentLen maxLen) { maxLen currentLen; maxStart start; } } else { currentLen 1; start i; } } if (maxLen 5) return {}; vectorint result; for (int i maxStart; i maxStart maxLen; i) { result.push_back(cards[i]); } return result; } int main() { vectorint input {3,4,5,5,6,7,8,9,10,J,Q,K,A}; vectorint longest getLongestStraight(input); if (!longest.empty()) { cout 最长顺子: ; for (int card : longest) cout card ; cout endl; } else { cout 无有效顺子 endl; } return 0; }3.2 关键代码解析排序处理使用sort()将乱序牌组变为有序序列这是后续滑动窗口处理的基础滑动窗口逻辑currentLen记录当前连续序列长度maxLen跟踪最大长度遇到不连续数字时重置窗口起点边界条件处理输入牌数不足5张直接返回空最终结果长度不足5张视为无效4. 算法优化与变种4.1 时间复杂度优化当牌型范围有限时如扑克牌仅13个数字可以使用哈希表实现O(n)解法vectorint getLongestStraightOpt(vectorint cards) { unordered_setint cardSet(cards.begin(), cards.end()); int maxLen 0, maxStart 0; for (int num : cardSet) { if (!cardSet.count(num-1)) { // 确保从序列起点开始 int currentNum num; int currentLen 1; while (cardSet.count(currentNum1)) { currentNum; currentLen; } if (currentLen maxLen) { maxLen currentLen; maxStart num; } } } if (maxLen 5) return {}; vectorint result; for (int i 0; i maxLen; i) { result.push_back(maxStart i); } return result; }4.2 规则变种处理不同游戏规则需要调整跑得快规则A作为1使用2不参与顺子// 预处理时过滤2 cards.erase(remove_if(cards.begin(), cards.end(), [](int x){return x 15;}), cards.end());双顺子判断需要连续对子如33-44-55修改判断条件为cards[i] cards[i-1] 1 count(cards[i]) 25. 测试用例设计全面的测试应包含以下场景测试场景输入示例预期输出基础顺子[3,4,5,6,7][3,4,5,6,7]含重复牌[3,4,5,5,6,7][3,4,5,6,7]多段顺子[3,4,5,9,10,J,Q][9,10,J,Q]含2和A[2,A,3,4,5,6][3,4,5,6]不足5张[3,4,5,6][]6. 常见问题与调试技巧6.1 典型错误排查重复牌处理不当症状顺子长度计算错误修复在滑动窗口比较时跳过相同数字边界条件遗漏症状空输入或短输入导致崩溃修复开头添加长度检查特殊牌型规则混淆症状A/2处理不符合题目要求修复明确题目对特殊牌的说明6.2 调试建议打印中间变量cout Current: cards[i] Len: currentLen endl;使用小型测试用例先验证[3,4,5,6,7]等简单情况再逐步增加复杂度可视化牌型void printCards(const vectorint cards) { for (int c : cards) { if (c 10) cout c; else if (c 11) cout J; else if (c 12) cout Q; // 其他牌型... } }7. 工程实践建议代码结构优化将牌型转换单独封装使用枚举定义牌值常量enum CardValue { THREE 3, FOUR, FIVE, ..., ACE 14 };性能考量对于固定牌型如标准54张算法复杂度差异不大大规模数据时优选哈希表解法扩展性设计支持不同游戏规则通过策略模式注入抽象顺子判断为独立接口在实际机试中建议先实现基础版本确保正确性有时间再优化。华为OD通常更关注问题分析和基础编码能力而非极致优化。