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

一、题目1. 题目描述斗地主起源于湖北十堰房县据说是一位叫吴修全的年轻人根据当地流行的扑克玩法“跑得快”改编的如今已风靡整个中国并流行于互联网上。牌型定义顺子又称顺子最少 5 张牌最多 12 张牌。牌面范围3...A。限制条件不能包含 2也不能包含大小王。花色规则不计花色即只看牌面值。示例顺子3-4-5-6-7-87-8-9-10-J-Q3-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×4213×42 张牌。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 张连续的牌故无法构成顺子。二、核心解题思路1. 牌面映射 (Mapping)计算机无法直接比较J,Q,K的大小。我们需要建立映射关系将字符转换为数字索引3→ 04→ 1...10→ 7J→ 8Q→ 9K→ 10A→ 11数组长度共 12 种牌。2. 构建“可用牌”集合统计手牌使用Set或布尔数组记录手牌中有哪些牌去重因为顺子不需要对子。剔除已出牌遍历已出牌列表如果在手牌中存在则从可用集合中移除。结果得到一个长度为 12 的布尔数组available[0...11]true表示该点数的牌可用。3. 滑动窗口查找连续段遍历available数组寻找连续的true片段维护currentStart(当前连续段起点) 和currentLen(当前长度)。当遇到false或到达数组末尾时结算当前连续段若currentLen 5则是一个候选顺子。截断处理题目限制顺子最多 12 张。由于总牌型只有 12 张实际上只要连续长度 ≥5 取从起点开始的min(currentLen, 12)即可本题全范围也就12张所以直接取整个连续段。4. 优先级判定 (关键)我们需要在多个候选顺子中选出最优解规则 1长度 (len) 越大越好。规则 2若长度相同起始牌索引 (start) 越大越好因为索引越大牌面越大。策略初始化bestLen 0,bestStart -1。每发现一个有效连续段(len, start)如果len bestLen更新最优解。如果len bestLen且start bestStart更新最优解。技巧由于我们是从左向右从小到大遍历如果遇到长度相同的后面的start天然比前面的大。所以逻辑可以简化为if (len bestLen)就更新注意必须是严格大于长度或者长度相等时自动覆盖因为后遍历到的起点更大。修正如果是len bestLen肯定更新。如果len bestLen因为遍历顺序是从小到大的后遇到的start一定更大所以直接if (len bestLen)即可覆盖旧答案。但是要注意题目要求最长优先。如果先遇到一个长度为 6 的后面遇到一个长度为 5 的不能覆盖。最终逻辑if (len bestLen) { update(); } else if (len bestLen) { // 因为是从左往右扫后来的 start 一定更大直接覆盖即可满足“起始牌最大” update(); }合并为if (len bestLen)(前提是len 5)。三、JavaScript 实现const readline require(readline); // 1. 定义牌面映射 const CARD_ORDER [3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A]; const CARD_TO_IDX {}; CARD_ORDER.forEach((card, idx) { CARD_TO_IDX[card] idx; }); function solve() { const rl readline.createInterface({ input: process.stdin, output: process.stdout }); const lines []; rl.on(line, (line) { lines.push(line.trim()); }); rl.on(close, () { if (lines.length 2) { console.log(NO-CHAIN); return; } const handStr lines[0]; const playedStr lines[1]; // 2. 解析手牌构建可用集合 (Set 去重) const handCards handStr ? [] : handStr.split(-); const availableSet new Set(handCards); // 3. 剔除已出牌 const playedCards playedStr ? [] : playedStr.split(-); for (const card of playedCards) { if (availableSet.has(card)) { availableSet.delete(card); } } // 4. 转换为布尔数组 (索引 0-11) // true 表示该牌可用 const isAvailable new Array(12).fill(false); for (const card of availableSet) { if (CARD_TO_IDX.hasOwnProperty(card)) { isAvailable[CARD_TO_IDX[card]] true; } } // 5. 滑动窗口查找最长顺子 let bestLen 0; let bestStart -1; let currentLen 0; let currentStart -1; for (let i 0; i 12; i) { if (isAvailable[i]) { if (currentLen 0) { currentStart i; } currentLen; } else { // 连续性中断结算上一段 if (currentLen 5) { // 判定逻辑长度更长或者长度相同但起点更大(由于是从左向右长度相同时当前的start必然更小不对) // 等等遍历是从 0 到 11。 // 第一次遇到 len6, start0 (3-8) // 第二次遇到 len6, start5 (8-K) - 此时 i 到了断点。 // 后遍历到的连续段其 start 一定比之前的大吗是的。 // 所以如果 len bestLen就可以更新因为新的 start 一定 旧的 start (实际上如果不重叠则严格大于) if (currentLen bestLen) { bestLen currentLen; bestStart currentStart; } } currentLen 0; currentStart -1; } } // 处理最后一段如果数组以 true 结尾 if (currentLen 5) { if (currentLen bestLen) { bestLen currentLen; bestStart currentStart; } } // 6. 输出结果 if (bestLen 0) { console.log(NO-CHAIN); } else { // 构造结果字符串 // 题目限制最多12张这里 total 只有12张所以直接取 bestLen 长度即可 const resultCards []; for (let i 0; i bestLen; i) { resultCards.push(CARD_ORDER[bestStart i]); } console.log(resultCards.join(-)); } }); } solve();四、代码关键点解析1. 映射表的建立const CARD_ORDER [3, 4, ..., A];使用数组下标天然代表大小关系避免了复杂的if-else或switch判断牌面大小。10作为字符串处理时需特别注意映射表中直接写10即可完美匹配输入。2. 集合操作去重const availableSet new Set(handCards); // ... delete ...顺子只关心“有没有这张牌”不关心“有几张”。Set数据结构能高效地完成去重和删除操作时间复杂度 O(1) 。3. 优先级逻辑的简化很多同学在处理“长度相同取起始牌最大”时会感到困惑。逻辑推导我们是从牌面小到大索引 0 到 11遍历的。假设发现了第一段顺子长度 6起点 0 (3-8)。继续遍历又发现第二段顺子长度 6起点 5 (8-K)。显然后发现的顺子起点更大。结论只要currentLen bestLen就无条件更新。这样既保证了长度优先时更新也保证了同长度时起点最大时后来的覆盖先来的。4. 边界处理空输入代码中增加了lines.length 2的判断。尾部连续循环结束后需要单独检查currentLen防止最长的顺子正好在数组末尾A结尾而被漏掉。五、避坑指南⚠️牌面 10 的处理输入是用-分隔的split(-)会自动把10作为一个整体字符串不会拆成1和0。但在映射时确保字典里有10这个键。顺子长度限制题目说“最多 12 张”。在本题的牌面定义3 到 A中总共就只有 12 种牌。所以理论上找到的连续段最长也就是 12不需要额外做slice(0, 12)的操作自然满足条件。无解情况务必初始化bestLen 0最后判断若仍为 0 则输出NO-CHAIN。已出牌不在手牌中Set.delete()方法即使删除不存在的元素也不会报错无需额外判断has代码更简洁。六、复杂度分析时间复杂度解析输入和构建 Set O(NM) 其中 N 是手牌数 M 是已出牌数。遍历固定长度的牌面数组12个元素 O(1) 常数级因为牌型总数固定。总计 O(NM) 线性时间效率极高。空间复杂度存储手牌 Set 和布尔数组 O(1) 因为牌型种类固定为 12手牌数量虽多但去重后最多 12。七、总结这道题看似是扑克牌游戏实则是数组连续区间查找问题。核心转化将字符牌面转化为数字索引。核心算法一次线性扫描滑动窗口思想。JS 优势利用Set和数组方法代码极其简洁逻辑清晰。掌握这种“映射 标记数组 线性扫描”的模式可以解决绝大多数类似的连续子序列问题。祝大家在机考中顺利 AC