1. 项目概述从一道题看华为OD机试的“通关密码”最近在技术社区和求职论坛里“华为OD机试”的热度一直居高不下。无论是应届生还是寻求职业转换的开发者都把通过OD机试视为进入华为技术体系的一道重要门槛。而机试题目本身也因其贴近实际业务场景、注重算法与工程能力结合的特点成为了大家讨论和准备的焦点。今天我们就来深度拆解一道经典的华为OD机试题——“最长的顺子”并不仅仅满足于给出答案而是要透过这道题剖析其背后的考察意图、解题的核心思想并一次性提供C、Java、JavaScript、Python四种主流语言的实现方案。这道题看似是简单的扑克牌游戏逻辑实则是对开发者数据结构运用、边界条件处理、多情况枚举以及代码简洁性的一次综合考验。理解它你收获的将不仅是一个题解更是一套应对类似“查找最长连续序列”问题的通用方法论。2. 题目深度解析与核心思路拆解2.1 问题场景还原与需求定义“最长的顺子”问题通常描述如下我们手中有一定数量的扑克牌仅考虑点数忽略花色扑克牌的点数范围一般是1-13对应A, 2, 3, ..., 10, J, Q, K有时A也可能被当作14或1需根据题目具体说明本题我们按1-13处理。同时我们还有一个“癞子”或“百搭”牌的概念它可以用作任意点数的牌来填补顺子的空缺。题目会给定我们手中已有的牌可能包含重复以及可用癞子牌的数量。目标是找出利用这些牌和癞子能够组成的最长顺子的长度。顺子要求点数连续且每个点数在顺子中至多出现一次。例如手中牌为[1, 3, 4, 5, 6, 7, 9]癞子数量为2。那么最长的顺子可能是[3, 4, 5, 6, 7]长度为5无需癞子但如果我们用癞子补上2和8则可以组成[1, 2, 3, 4, 5, 6, 7, 8, 9]长度为9。显然后者更长。核心需求拆解输入处理接收已有的牌面点数列表可能无序、有重复和癞子数量。数据预处理去重、排序。因为顺子关心的是点数的有无而非多少张且需要在有序序列上查找连续区间。问题转化在排序去重后的点数序列上寻找一个最长的连续区间使得区间内缺失的点数数量不超过癞子数量。这里的“缺失”是指区间起点到终点之间本该连续但实际没有牌的点位。算法选择这本质上是一个在有序数组上的“滑动窗口”问题。窗口左右边界移动动态计算窗口内缺失的牌数并与癞子数比较。输出最长的顺子长度。2.2 解题思路与算法选型论证为什么选择滑动窗口双指针这是由问题特性决定的。我们需要寻找的是一段连续的区间。暴力枚举所有子区间是O(n²)的复杂度。而滑动窗口可以在O(n)的时间内解决问题因为左右指针left和right都只向右移动每个元素最多被访问两次。滑动窗口的具体逻辑将手中的牌点数去重并排序得到数组cards。初始化left 0,right 0maxLen 0记录最长顺子长度wildcard为给定的癞子数。让right指针不断向右移动尝试扩大窗口。对于当前[left, right]窗口计算要形成从cards[left]到cards[right]的连续序列中间缺失的点数有多少。理想情况下如果完全连续点数差应为cards[right] - cards[left]。实际我们有的牌数是(right - left 1)张。因此缺失的牌数missing (cards[right] - cards[left]) - (right - left)。这个公式是核心它计算了区间首尾跨度与实际拥有牌数之间的“空洞”数量。如果missing wildcard说明当前窗口内的空洞可以用癞子填补这是一个有效的顺子窗口。更新maxLen max(maxLen, cards[right] - cards[left] 1 (wildcard - missing))。这里注意最终顺子长度是区间实际跨度(cards[right] - cards[left] 1)加上富余的癞子。富余癞子可以加在序列的两端继续延伸长度但需要小心不要超出1-13的范围限制这是一个关键的边界条件很多实现会忽略。如果missing wildcard说明当前窗口缺失太多癞子不够用。此时需要收缩左边界left向右移动直到missing wildcard重新满足。重复步骤3-6直到right遍历完整个数组。注意步骤5中关于“富余癞子”的处理是易错点。更严谨的做法是在找到有效窗口[cards[left], cards[right]]后计算窗口内实际点数个数actualCount right - left 1可用癞子wildcard那么理论上这个窗口能构建的顺子最大长度是actualCount wildcard。但是这个长度不能无限制增长它受到两个限制一是扑克牌点数范围如1-13二是窗口的边界。更安全的计算方式是potentialLen min(13, cards[right] (wildcard - missing)) - max(1, cards[left] - (wildcard - missing)) 1然后取potentialLen和actualCount wildcard的较小值不这样太复杂。实际上因为窗口是连续的富余癞子(wildcard - missing)只能用于向窗口的左侧或右侧扩展。所以最大长度 actualCount wildcard但同时必须满足扩展后的最小点 1且扩展后的最大点 13。因此maxLen max(maxLen, min(actualCount wildcard, 13 - cards[left] 1 (wildcard - missing)?))。一个更清晰且不易错的实现策略是在滑动窗口维护有效性的同时直接计算当前窗口能覆盖的最大连续长度。我们可以认为癞子先用于填补窗口内的空洞消耗missing个剩下的wildcard - missing个可以附加在序列的前后。那么这个窗口能表示的最长顺子就是从cards[left] - (wildcard - missing)到cards[right] (wildcard - missing)的区间但这个区间必须被裁剪到[1,13]范围内。所以长度是min(13, cards[right] remain) - max(1, cards[left] - remain) 1其中remain wildcard - missing。边界条件与特殊情况空手牌如果手中无牌那么最长顺子就是癞子数量本身但不超过13。点数范围始终牢记点数有上下界通常是1和13。计算潜在长度时不能超出。去重输入牌可能有重复必须先处理。排序滑动窗口前提是数据有序。3. 多语言实现详解与代码对比理解了核心算法我们来看具体实现。不同语言在数据结构、语法特性上各有优劣实现同一算法的代码风格和性能表现也会略有差异。下面我们分别用C、Java、JavaScript和Python实现并附上关键注释。3.1 C实现效率与控制力的典范C以其高效的运行速度和精细的内存控制著称适合对性能要求高的场景。#include iostream #include vector #include algorithm #include unordered_set using namespace std; int longestStraight(vectorint hand, int wildcards) { if (hand.empty()) { return min(wildcards, 13); // 无手牌时顺子最大长度为癞子数但不超过13 } // 1. 去重并排序 unordered_setint uniqueCards(hand.begin(), hand.end()); vectorint cards(uniqueCards.begin(), uniqueCards.end()); sort(cards.begin(), cards.end()); int n cards.size(); int left 0; int maxLen 0; // 2. 滑动窗口 for (int right 0; right n; right) { // 计算当前窗口 [left, right] 内缺失的牌数 // 缺失数 (区间终点值 - 区间起点值) - (区间内牌的张数 - 1) // 即缺失数 (cards[right] - cards[left]) - (right - left) // 当缺失数 癞子数时需要收缩左边界 while ((cards[right] - cards[left]) - (right - left) wildcards) { left; } // 此时窗口有效计算当前窗口能构成的最长顺子 int missing (cards[right] - cards[left]) - (right - left); int remainingWildcards wildcards - missing; // 富余的癞子 int currentMin cards[left] - remainingWildcards; int currentMax cards[right] remainingWildcards; // 确保顺子范围在1-13之间 currentMin max(currentMin, 1); currentMax min(currentMax, 13); int currentLength currentMax - currentMin 1; maxLen max(maxLen, currentLength); } // 3. 特别考虑如果癞子很多可能完全不需要手牌就能组成很长顺子 // 但上述循环已经通过“空手牌”和窗口计算覆盖了这种情况。 // 另一种极端手牌点数很分散癞子全用来连接两个点可能不如直接用癞子自己组成顺子长。 // 因此最终结果还需要和“仅用癞子”的长度比较。 maxLen max(maxLen, min(wildcards, 13)); return maxLen; } int main() { // 示例1 vectorint hand1 {1, 3, 4, 5, 6, 7, 9}; int wildcards1 2; cout 手牌: ; for (int card : hand1) cout card ; cout , 癞子: wildcards1 endl; cout 最长顺子长度: longestStraight(hand1, wildcards1) endl; // 应输出9 // 示例2: 有重复牌 vectorint hand2 {5, 5, 5, 8, 8, 9, 10}; int wildcards2 1; cout \n手牌: ; for (int card : hand2) cout card ; cout , 癞子: wildcards2 endl; cout 最长顺子长度: longestStraight(hand2, wildcards2) endl; // 可能输出5 (5,6,7,8,9) 或 (8,9,10,J,Q)? 需要看点数映射假设8,9,10,11,12癞子补11则长度5。 return 0; }C实现要点使用unordered_set去重比先排序后去重更直观平均O(n)时间复杂度。滑动窗口的循环条件内层while循环用于调整左边界确保窗口内缺失数不超过癞子数。这是滑动窗口的典型模式。边界裁剪max(currentMin, 1)和min(currentMax, 13)至关重要防止计算出的顺子超出合法范围。与“纯癞子”方案比较最后max(maxLen, min(wildcards, 13))是一个安全补丁处理了手牌极度分散时可能不如直接用全部癞子组成一个从1开始的短顺子的情况。但通常滑动窗口算法能覆盖。3.2 Java实现严谨与生态的平衡Java在企业级开发中广泛应用其代码风格强调健壮性和可读性。import java.util.*; public class LongestStraight { public static int longestStraight(int[] hand, int wildcards) { if (hand null || hand.length 0) { return Math.min(wildcards, 13); } // 1. 去重 SetInteger cardSet new HashSet(); for (int num : hand) { cardSet.add(num); } // 2. 排序 ListInteger cards new ArrayList(cardSet); Collections.sort(cards); int n cards.size(); int left 0; int maxLen 0; // 3. 滑动窗口 for (int right 0; right n; right) { // 收缩左边界直到窗口内缺失数 wildcards while ((cards.get(right) - cards.get(left)) - (right - left) wildcards) { left; } // 计算当前有效窗口能构成的最长顺子 int missing (cards.get(right) - cards.get(left)) - (right - left); int remaining wildcards - missing; int currentMin cards.get(left) - remaining; int currentMax cards.get(right) remaining; // 约束到[1,13]范围 currentMin Math.max(currentMin, 1); currentMax Math.min(currentMax, 13); int currentLength currentMax - currentMin 1; maxLen Math.max(maxLen, currentLength); } // 4. 考虑仅使用癞子的情况 maxLen Math.max(maxLen, Math.min(wildcards, 13)); return maxLen; } public static void main(String[] args) { int[] hand1 {1, 3, 4, 5, 6, 7, 9}; int wildcards1 2; System.out.println(手牌: Arrays.toString(hand1) , 癞子: wildcards1); System.out.println(最长顺子长度: longestStraight(hand1, wildcards1)); // 9 int[] hand2 {5, 5, 5, 8, 8, 9, 10}; int wildcards2 1; System.out.println(\n手牌: Arrays.toString(hand2) , 癞子: wildcards2); System.out.println(最长顺子长度: longestStraight(hand2, wildcards2)); // 5 } }Java实现要点集合类的使用HashSet用于去重ArrayList用于存储和排序这是Java标准做法。泛型与类型安全集合明确了Integer类型避免了拆装箱的隐式操作虽然会有自动装箱但代码清晰。方法调用使用Math.max/min和Collections.sort代码意图明确。空值检查对输入参数hand进行了null检查体现了Java的防御式编程风格。3.3 JavaScript实现灵活与全栈的便捷JavaScript作为全栈语言其实现更注重简洁和函数式编程的可能。function longestStraight(hand, wildcards) { if (!hand || hand.length 0) { return Math.min(wildcards, 13); } // 1. 去重并排序 const cards [...new Set(hand)].sort((a, b) a - b); const n cards.length; let left 0; let maxLen 0; // 2. 滑动窗口 for (let right 0; right n; right) { // 调整左边界使窗口内缺失数不超过癞子数 while ((cards[right] - cards[left]) - (right - left) wildcards) { left; } // 计算当前窗口能形成的最大顺子长度 const missing (cards[right] - cards[left]) - (right - left); const remaining wildcards - missing; let currentMin cards[left] - remaining; let currentMax cards[right] remaining; // 确保范围在1到13之间 currentMin Math.max(currentMin, 1); currentMax Math.min(currentMax, 13); const currentLength currentMax - currentMin 1; maxLen Math.max(maxLen, currentLength); } // 3. 考虑纯癞子情况 maxLen Math.max(maxLen, Math.min(wildcards, 13)); return maxLen; } // 测试示例 const hand1 [1, 3, 4, 5, 6, 7, 9]; const wildcards1 2; console.log(手牌: [${hand1}], 癞子: ${wildcards1}); console.log(最长顺子长度: ${longestStraight(hand1, wildcards1)}); // 9 const hand2 [5, 5, 5, 8, 8, 9, 10]; const wildcards2 1; console.log(\n手牌: [${hand2}], 癞子: ${wildcards2}); console.log(最长顺子长度: ${longestStraight(hand2, wildcards2)}); // 5JavaScript实现要点利用Set和扩展运算符快速去重[...new Set(hand)]是ES6之后非常简洁的去重写法。排序函数sort((a, b) a - b)确保是数值排序默认的sort()会按字符串排序导致[1, 10, 2]这样的结果。语法简洁使用const和let定义变量箭头函数代码非常紧凑。直接浏览器或Node环境运行无需复杂环境配置适合快速原型验证。3.4 Python实现简洁与表达力的胜利Python以其极致的简洁和强大的表达能力常常能用最少的代码完成算法逻辑。def longest_straight(hand, wildcards): 计算可使用癞子牌的最长顺子长度。 Args: hand: List[int], 手中的牌点数列表。 wildcards: int, 可用的癞子牌数量。 Returns: int, 最长顺子的长度。 if not hand: return min(wildcards, 13) # 1. 去重并排序 cards sorted(set(hand)) n len(cards) left 0 max_len 0 # 2. 滑动窗口 for right in range(n): # 当窗口内缺失牌数超过癞子数时收缩左边界 while (cards[right] - cards[left]) - (right - left) wildcards: left 1 # 当前窗口有效计算能扩展的最大长度 missing (cards[right] - cards[left]) - (right - left) remaining wildcards - missing current_min max(cards[left] - remaining, 1) current_max min(cards[right] remaining, 13) current_len current_max - current_min 1 max_len max(max_len, current_len) # 3. 考虑完全使用癞子的情况 max_len max(max_len, min(wildcards, 13)) return max_len if __name__ __main__: # 测试用例 hand1 [1, 3, 4, 5, 6, 7, 9] wildcards1 2 print(f手牌: {hand1}, 癞子: {wildcards1}) print(f最长顺子长度: {longest_straight(hand1, wildcards1)}) # 输出 9 hand2 [5, 5, 5, 8, 8, 9, 10] wildcards2 1 print(f\n手牌: {hand2}, 癞子: {wildcards2}) print(f最长顺子长度: {longest_straight(hand2, wildcards2)}) # 输出 5 # 边界测试空手牌很多癞子 hand3 [] wildcards3 5 print(f\n手牌: {hand3}, 癞子: {wildcards3}) print(f最长顺子长度: {longest_straight(hand3, wildcards3)}) # 输出 5 # 边界测试手牌分散癞子少 hand4 [1, 5, 10, 13] wildcards4 1 print(f\n手牌: {hand4}, 癞子: {wildcards4}) print(f最长顺子长度: {longest_straight(hand4, wildcards4)}) # 输出 2 (例如[1,2]或[12,13])Python实现要点极致简洁sorted(set(hand))一行完成去重排序充分体现了Python的内建函数优势。清晰的循环for right in range(n):和while ...:逻辑与算法描述高度一致。可读性极强的表达式计算missing和current_len的公式一目了然。丰富的测试用例在main函数中包含了多种边界情况测试便于验证。4. 算法核心滑动窗口的变体与复杂度分析4.1 为何是滑动窗口与其他算法的对比除了滑动窗口我们可能会想到其他方法比如动态规划(DP)或回溯搜索。我们来简单分析一下动态规划DP通常适用于具有最优子结构的问题。对于“最长顺子”一个区间的最优解并不直接依赖于其子区间的最优解因为癞子是可以全局调配的稀缺资源子区间用掉癞子会影响父区间。定义状态以哪个点结尾用了多少癞子会比较复杂且状态转移不直观。时间复杂度也可能较高。回溯/DFS可以枚举每张癞子牌替换成什么点数但癞子数量稍多比如5个搜索空间就会爆炸13^5不可行。排序后贪心一种贪心思路是从每个点开始尽可能往后延伸。这本质上就是滑动窗口的单向移动因为窗口右边界拓展时左边界没必要回退回退只会让窗口变小。所以滑动窗口是这种贪心策略的高效实现。因此滑动窗口是解决此类“在有序序列上寻找满足某条件的最长连续子区间”问题的最优解之一。它的时间复杂度是O(n log n)主要消耗在排序上滑动窗口过程本身是O(n)。空间复杂度是O(n)或O(1)如果允许修改原数组并去重但通常需要额外空间存储去重排序后的数组。4.2 滑动窗口中的关键公式推导再探讨我们反复使用的公式missing (cards[right] - cards[left]) - (right - left)是算法的灵魂。我们来彻底理解它cards[right] - cards[left]表示从cards[left]到cards[right]这个数值范围的跨度。例如cards[left]3,cards[right]9那么跨度是6意味着完美的连续序列应该是3,4,5,6,7,8,9共7个数。right - left表示在cards数组中从索引left到right之间实际拥有的不同点数的数量。因为数组已排序去重这个值就是区间内不同牌的张数减1不对应该是(right - left)。当left0, right2时区间有3张牌right-left2。所以(right - left)是区间内“间隔”的数量比牌数少1。那么(cards[right] - cards[left]) - (right - left)计算的是什么呢(cards[right] - cards[left])是数值跨度的长度(right - left)是实际拥有的“步数”。它们的差值就是数值跨度长度与实际步数之间的“差额”这个差额正好等于区间内缺失的连续整数的个数。举例cards [3, 5, 9],left0,right2。cards[right]-cards[left] 9-36。right-left 2-02。missing 6 - 2 4。 检查从3到9连续整数是3,4,5,6,7,8,9。我们实际有3,5,9。缺失了4,6,7,8。确实是4个。公式正确。4.3 多语言实现的细微差异与选择建议虽然四份代码算法核心一致但语言特性带来了细微差别去重排序Cunordered_setvectorsort。步骤清晰性能可控。JavaHashSetArrayListCollections.sort。面向对象风格稳健。JavaScript[...new Set(arr)]sort((a,b)a-b)。极其简洁但要注意排序回调。Pythonsorted(set(hand))。简洁之王表达力无敌。代码风格与性能C追求极致性能时首选尤其当hand很大时。手动控制内存和循环。Java大型项目、团队协作时的安全选择有完善的异常处理和生态工具。JavaScript全栈开发、快速原型、Web相关场景的必然选择。代码短小精悍。Python算法面试、数据分析、脚本编写的利器。代码几乎就是伪代码开发效率最高。选择建议如果你在准备华为OD机试官方通常支持C/Java/Python/JavaScript。根据你最熟悉的语言选择。从解题速度看Python往往是首选因为写起来快不容易在语法上出错。如果题目对时间复杂度要求极其苛刻可能C更有优势。如果是在实际工程项目中需要类似逻辑考虑团队的技术栈和项目的性能要求。5. 常见陷阱、调试技巧与扩展思考5.1 实战中容易踩的“坑”忽略去重这是最常见的错误。手中有多张相同点数的牌在顺子中只能算一张。不去重会导致missing计算错误。忘记排序滑动窗口的前提是数据有序。如果直接对原数组滑动结果毫无意义。边界条件处理不当空输入手牌列表为空时应直接返回min(wildcards, 13)。点数越界计算currentMin和currentMax时一定要用max(1, ...)和min(13, ...)卡住边界。否则可能出现0或14这样的非法点数导致长度计算错误。癞子数很多如果癞子数量wildcards大于等于12理论上可以直接组成从1到13的顺子长度为13。我们的算法中最后的max(maxLen, min(wildcards, 13))能覆盖这种情况但窗口计算过程中也可能得出更大值受限于手牌位置。需要确保逻辑一致。“富余癞子”使用错误在计算当前窗口最大长度时错误地认为长度就是(right-left1) wildcards。这是不对的因为wildcards中的一部分已经用于填补missing了富余的是wildcards - missing。而且富余的癞子可以加在两边但受限于1-13范围。滑动窗口收缩条件while循环里的条件是(cards[right] - cards[left]) - (right - left) wildcards。注意是而不是。如果缺失数等于癞子数窗口仍然是有效的可以继续尝试扩展右边界或计算长度。5.2 调试与验证方法构造极端测试用例手牌为空癞子为0、5、20。手牌为[1,13]癞子为0、11、12。手牌密集[1,2,3,4,5,6,7,8,9,10,11,12,13]癞子为0。手牌极度分散[1, 13]癞子为1。最长顺子应该是2[1,2]或[12,13]而不是3因为一个癞子无法连接1和13。包含重复牌[2,2,2,2,5,5,5]癞子为2。打印中间变量在循环中打印left,right,missing,currentMin,currentMax,currentLength观察其变化是否符合预期。手动模拟对于小规模例子用纸笔走一遍算法流程这是理解算法和发现逻辑错误的最佳方式。对拍用两种不同的思路比如一种朴素的贪心枚举写一个暴力但正确的程序用于验证滑动窗口算法在小数据规模下的正确性。5.3 问题扩展与变种如果A可以当作14即点数范围是1-14只需要修改边界条件将上界13改为14即可。但需要注意A作为1和14有时可能同时存在题目通常会明确说明如何处理。在我们的模型中如果A是1那么它就在数组里如果A是14那就是另一个值。不会同时存在。如果癞子牌有不同类型如可以代替任何牌但每种点数最多代替一张这和我们当前模型一致。如果要求输出最长的顺子具体是什么算法需要稍作修改。在记录maxLen的同时还需要记录取得最大长度时的currentMin和currentMax。最后生成从currentMin到currentMax的序列即可注意有些位置是癞子填补的。如果手牌是字符串如[“A”, “2”, “J”, “Q”, “K”]需要先建立一个映射关系将牌面字符映射到数字A-1, J-11, Q-12, K-13然后套用上述算法。更一般的“最长连续序列”问题LeetCode 128. Longest Consecutive Sequence那道题不允许有“癞子”且要求O(n)时间复杂度。解法是利用哈希集合HashSet实现O(1)查找然后对于每个序列的起始数字即num-1不在集合中的数字不断查找num1是否存在。我们的问题因为允许填补空缺癞子所以解法不同。6. 在华为OD机试中的应试策略与总结回到最初的场景——华为OD机试。这道“最长的顺子”题考察点非常明确基础数据结构能力对数组进行去重、排序的操作。算法应用能力识别出这是滑动窗口/双指针问题并正确实现。边界处理与细节实现正确处理去重、排序、点数边界、癞子计算等细节。代码健壮性考虑空输入、极端值等情况。时间复杂度分析能够说明算法的时间复杂度O(n log n)和空间复杂度O(n)或O(1)。应试建议优先选择Python或Java除非你C非常熟练否则Python的简洁语法能帮你节省大量编码时间减少低级错误。Java的严谨性也有助于写出健壮的代码。先写思路注释在代码开头或关键步骤前用注释写明算法步骤这有助于阅卷如果是人工阅卷和自己在编码时理清逻辑。写完先跑样例利用题目给出的示例快速验证。华为OD的机试环境通常允许运行和调试。检查边界专门用几分钟思考并测试边界情况。时间与空间复杂度即使题目没要求也最好在注释中写明展示你的专业素养。这道题本身不难但完美实现需要细心。它很像一个缩影华为OD的很多机试题都具备这种特点题目背景易于理解如扑克牌但需要你将实际问题抽象为恰当的算法模型并严谨地实现。通过这道题的多语言解法和深度剖析希望你能掌握的不只是这一个问题的答案更是解决一类问题的方法和应对机试的实战策略。在真正的考场上冷静分析把问题拆解为你熟悉的数据结构和算法模型然后像我们上面所做的那样一步步用代码构建起你的解决方案。
华为OD机试“最长的顺子”题解：滑动窗口算法与多语言实现
1. 项目概述从一道题看华为OD机试的“通关密码”最近在技术社区和求职论坛里“华为OD机试”的热度一直居高不下。无论是应届生还是寻求职业转换的开发者都把通过OD机试视为进入华为技术体系的一道重要门槛。而机试题目本身也因其贴近实际业务场景、注重算法与工程能力结合的特点成为了大家讨论和准备的焦点。今天我们就来深度拆解一道经典的华为OD机试题——“最长的顺子”并不仅仅满足于给出答案而是要透过这道题剖析其背后的考察意图、解题的核心思想并一次性提供C、Java、JavaScript、Python四种主流语言的实现方案。这道题看似是简单的扑克牌游戏逻辑实则是对开发者数据结构运用、边界条件处理、多情况枚举以及代码简洁性的一次综合考验。理解它你收获的将不仅是一个题解更是一套应对类似“查找最长连续序列”问题的通用方法论。2. 题目深度解析与核心思路拆解2.1 问题场景还原与需求定义“最长的顺子”问题通常描述如下我们手中有一定数量的扑克牌仅考虑点数忽略花色扑克牌的点数范围一般是1-13对应A, 2, 3, ..., 10, J, Q, K有时A也可能被当作14或1需根据题目具体说明本题我们按1-13处理。同时我们还有一个“癞子”或“百搭”牌的概念它可以用作任意点数的牌来填补顺子的空缺。题目会给定我们手中已有的牌可能包含重复以及可用癞子牌的数量。目标是找出利用这些牌和癞子能够组成的最长顺子的长度。顺子要求点数连续且每个点数在顺子中至多出现一次。例如手中牌为[1, 3, 4, 5, 6, 7, 9]癞子数量为2。那么最长的顺子可能是[3, 4, 5, 6, 7]长度为5无需癞子但如果我们用癞子补上2和8则可以组成[1, 2, 3, 4, 5, 6, 7, 8, 9]长度为9。显然后者更长。核心需求拆解输入处理接收已有的牌面点数列表可能无序、有重复和癞子数量。数据预处理去重、排序。因为顺子关心的是点数的有无而非多少张且需要在有序序列上查找连续区间。问题转化在排序去重后的点数序列上寻找一个最长的连续区间使得区间内缺失的点数数量不超过癞子数量。这里的“缺失”是指区间起点到终点之间本该连续但实际没有牌的点位。算法选择这本质上是一个在有序数组上的“滑动窗口”问题。窗口左右边界移动动态计算窗口内缺失的牌数并与癞子数比较。输出最长的顺子长度。2.2 解题思路与算法选型论证为什么选择滑动窗口双指针这是由问题特性决定的。我们需要寻找的是一段连续的区间。暴力枚举所有子区间是O(n²)的复杂度。而滑动窗口可以在O(n)的时间内解决问题因为左右指针left和right都只向右移动每个元素最多被访问两次。滑动窗口的具体逻辑将手中的牌点数去重并排序得到数组cards。初始化left 0,right 0maxLen 0记录最长顺子长度wildcard为给定的癞子数。让right指针不断向右移动尝试扩大窗口。对于当前[left, right]窗口计算要形成从cards[left]到cards[right]的连续序列中间缺失的点数有多少。理想情况下如果完全连续点数差应为cards[right] - cards[left]。实际我们有的牌数是(right - left 1)张。因此缺失的牌数missing (cards[right] - cards[left]) - (right - left)。这个公式是核心它计算了区间首尾跨度与实际拥有牌数之间的“空洞”数量。如果missing wildcard说明当前窗口内的空洞可以用癞子填补这是一个有效的顺子窗口。更新maxLen max(maxLen, cards[right] - cards[left] 1 (wildcard - missing))。这里注意最终顺子长度是区间实际跨度(cards[right] - cards[left] 1)加上富余的癞子。富余癞子可以加在序列的两端继续延伸长度但需要小心不要超出1-13的范围限制这是一个关键的边界条件很多实现会忽略。如果missing wildcard说明当前窗口缺失太多癞子不够用。此时需要收缩左边界left向右移动直到missing wildcard重新满足。重复步骤3-6直到right遍历完整个数组。注意步骤5中关于“富余癞子”的处理是易错点。更严谨的做法是在找到有效窗口[cards[left], cards[right]]后计算窗口内实际点数个数actualCount right - left 1可用癞子wildcard那么理论上这个窗口能构建的顺子最大长度是actualCount wildcard。但是这个长度不能无限制增长它受到两个限制一是扑克牌点数范围如1-13二是窗口的边界。更安全的计算方式是potentialLen min(13, cards[right] (wildcard - missing)) - max(1, cards[left] - (wildcard - missing)) 1然后取potentialLen和actualCount wildcard的较小值不这样太复杂。实际上因为窗口是连续的富余癞子(wildcard - missing)只能用于向窗口的左侧或右侧扩展。所以最大长度 actualCount wildcard但同时必须满足扩展后的最小点 1且扩展后的最大点 13。因此maxLen max(maxLen, min(actualCount wildcard, 13 - cards[left] 1 (wildcard - missing)?))。一个更清晰且不易错的实现策略是在滑动窗口维护有效性的同时直接计算当前窗口能覆盖的最大连续长度。我们可以认为癞子先用于填补窗口内的空洞消耗missing个剩下的wildcard - missing个可以附加在序列的前后。那么这个窗口能表示的最长顺子就是从cards[left] - (wildcard - missing)到cards[right] (wildcard - missing)的区间但这个区间必须被裁剪到[1,13]范围内。所以长度是min(13, cards[right] remain) - max(1, cards[left] - remain) 1其中remain wildcard - missing。边界条件与特殊情况空手牌如果手中无牌那么最长顺子就是癞子数量本身但不超过13。点数范围始终牢记点数有上下界通常是1和13。计算潜在长度时不能超出。去重输入牌可能有重复必须先处理。排序滑动窗口前提是数据有序。3. 多语言实现详解与代码对比理解了核心算法我们来看具体实现。不同语言在数据结构、语法特性上各有优劣实现同一算法的代码风格和性能表现也会略有差异。下面我们分别用C、Java、JavaScript和Python实现并附上关键注释。3.1 C实现效率与控制力的典范C以其高效的运行速度和精细的内存控制著称适合对性能要求高的场景。#include iostream #include vector #include algorithm #include unordered_set using namespace std; int longestStraight(vectorint hand, int wildcards) { if (hand.empty()) { return min(wildcards, 13); // 无手牌时顺子最大长度为癞子数但不超过13 } // 1. 去重并排序 unordered_setint uniqueCards(hand.begin(), hand.end()); vectorint cards(uniqueCards.begin(), uniqueCards.end()); sort(cards.begin(), cards.end()); int n cards.size(); int left 0; int maxLen 0; // 2. 滑动窗口 for (int right 0; right n; right) { // 计算当前窗口 [left, right] 内缺失的牌数 // 缺失数 (区间终点值 - 区间起点值) - (区间内牌的张数 - 1) // 即缺失数 (cards[right] - cards[left]) - (right - left) // 当缺失数 癞子数时需要收缩左边界 while ((cards[right] - cards[left]) - (right - left) wildcards) { left; } // 此时窗口有效计算当前窗口能构成的最长顺子 int missing (cards[right] - cards[left]) - (right - left); int remainingWildcards wildcards - missing; // 富余的癞子 int currentMin cards[left] - remainingWildcards; int currentMax cards[right] remainingWildcards; // 确保顺子范围在1-13之间 currentMin max(currentMin, 1); currentMax min(currentMax, 13); int currentLength currentMax - currentMin 1; maxLen max(maxLen, currentLength); } // 3. 特别考虑如果癞子很多可能完全不需要手牌就能组成很长顺子 // 但上述循环已经通过“空手牌”和窗口计算覆盖了这种情况。 // 另一种极端手牌点数很分散癞子全用来连接两个点可能不如直接用癞子自己组成顺子长。 // 因此最终结果还需要和“仅用癞子”的长度比较。 maxLen max(maxLen, min(wildcards, 13)); return maxLen; } int main() { // 示例1 vectorint hand1 {1, 3, 4, 5, 6, 7, 9}; int wildcards1 2; cout 手牌: ; for (int card : hand1) cout card ; cout , 癞子: wildcards1 endl; cout 最长顺子长度: longestStraight(hand1, wildcards1) endl; // 应输出9 // 示例2: 有重复牌 vectorint hand2 {5, 5, 5, 8, 8, 9, 10}; int wildcards2 1; cout \n手牌: ; for (int card : hand2) cout card ; cout , 癞子: wildcards2 endl; cout 最长顺子长度: longestStraight(hand2, wildcards2) endl; // 可能输出5 (5,6,7,8,9) 或 (8,9,10,J,Q)? 需要看点数映射假设8,9,10,11,12癞子补11则长度5。 return 0; }C实现要点使用unordered_set去重比先排序后去重更直观平均O(n)时间复杂度。滑动窗口的循环条件内层while循环用于调整左边界确保窗口内缺失数不超过癞子数。这是滑动窗口的典型模式。边界裁剪max(currentMin, 1)和min(currentMax, 13)至关重要防止计算出的顺子超出合法范围。与“纯癞子”方案比较最后max(maxLen, min(wildcards, 13))是一个安全补丁处理了手牌极度分散时可能不如直接用全部癞子组成一个从1开始的短顺子的情况。但通常滑动窗口算法能覆盖。3.2 Java实现严谨与生态的平衡Java在企业级开发中广泛应用其代码风格强调健壮性和可读性。import java.util.*; public class LongestStraight { public static int longestStraight(int[] hand, int wildcards) { if (hand null || hand.length 0) { return Math.min(wildcards, 13); } // 1. 去重 SetInteger cardSet new HashSet(); for (int num : hand) { cardSet.add(num); } // 2. 排序 ListInteger cards new ArrayList(cardSet); Collections.sort(cards); int n cards.size(); int left 0; int maxLen 0; // 3. 滑动窗口 for (int right 0; right n; right) { // 收缩左边界直到窗口内缺失数 wildcards while ((cards.get(right) - cards.get(left)) - (right - left) wildcards) { left; } // 计算当前有效窗口能构成的最长顺子 int missing (cards.get(right) - cards.get(left)) - (right - left); int remaining wildcards - missing; int currentMin cards.get(left) - remaining; int currentMax cards.get(right) remaining; // 约束到[1,13]范围 currentMin Math.max(currentMin, 1); currentMax Math.min(currentMax, 13); int currentLength currentMax - currentMin 1; maxLen Math.max(maxLen, currentLength); } // 4. 考虑仅使用癞子的情况 maxLen Math.max(maxLen, Math.min(wildcards, 13)); return maxLen; } public static void main(String[] args) { int[] hand1 {1, 3, 4, 5, 6, 7, 9}; int wildcards1 2; System.out.println(手牌: Arrays.toString(hand1) , 癞子: wildcards1); System.out.println(最长顺子长度: longestStraight(hand1, wildcards1)); // 9 int[] hand2 {5, 5, 5, 8, 8, 9, 10}; int wildcards2 1; System.out.println(\n手牌: Arrays.toString(hand2) , 癞子: wildcards2); System.out.println(最长顺子长度: longestStraight(hand2, wildcards2)); // 5 } }Java实现要点集合类的使用HashSet用于去重ArrayList用于存储和排序这是Java标准做法。泛型与类型安全集合明确了Integer类型避免了拆装箱的隐式操作虽然会有自动装箱但代码清晰。方法调用使用Math.max/min和Collections.sort代码意图明确。空值检查对输入参数hand进行了null检查体现了Java的防御式编程风格。3.3 JavaScript实现灵活与全栈的便捷JavaScript作为全栈语言其实现更注重简洁和函数式编程的可能。function longestStraight(hand, wildcards) { if (!hand || hand.length 0) { return Math.min(wildcards, 13); } // 1. 去重并排序 const cards [...new Set(hand)].sort((a, b) a - b); const n cards.length; let left 0; let maxLen 0; // 2. 滑动窗口 for (let right 0; right n; right) { // 调整左边界使窗口内缺失数不超过癞子数 while ((cards[right] - cards[left]) - (right - left) wildcards) { left; } // 计算当前窗口能形成的最大顺子长度 const missing (cards[right] - cards[left]) - (right - left); const remaining wildcards - missing; let currentMin cards[left] - remaining; let currentMax cards[right] remaining; // 确保范围在1到13之间 currentMin Math.max(currentMin, 1); currentMax Math.min(currentMax, 13); const currentLength currentMax - currentMin 1; maxLen Math.max(maxLen, currentLength); } // 3. 考虑纯癞子情况 maxLen Math.max(maxLen, Math.min(wildcards, 13)); return maxLen; } // 测试示例 const hand1 [1, 3, 4, 5, 6, 7, 9]; const wildcards1 2; console.log(手牌: [${hand1}], 癞子: ${wildcards1}); console.log(最长顺子长度: ${longestStraight(hand1, wildcards1)}); // 9 const hand2 [5, 5, 5, 8, 8, 9, 10]; const wildcards2 1; console.log(\n手牌: [${hand2}], 癞子: ${wildcards2}); console.log(最长顺子长度: ${longestStraight(hand2, wildcards2)}); // 5JavaScript实现要点利用Set和扩展运算符快速去重[...new Set(hand)]是ES6之后非常简洁的去重写法。排序函数sort((a, b) a - b)确保是数值排序默认的sort()会按字符串排序导致[1, 10, 2]这样的结果。语法简洁使用const和let定义变量箭头函数代码非常紧凑。直接浏览器或Node环境运行无需复杂环境配置适合快速原型验证。3.4 Python实现简洁与表达力的胜利Python以其极致的简洁和强大的表达能力常常能用最少的代码完成算法逻辑。def longest_straight(hand, wildcards): 计算可使用癞子牌的最长顺子长度。 Args: hand: List[int], 手中的牌点数列表。 wildcards: int, 可用的癞子牌数量。 Returns: int, 最长顺子的长度。 if not hand: return min(wildcards, 13) # 1. 去重并排序 cards sorted(set(hand)) n len(cards) left 0 max_len 0 # 2. 滑动窗口 for right in range(n): # 当窗口内缺失牌数超过癞子数时收缩左边界 while (cards[right] - cards[left]) - (right - left) wildcards: left 1 # 当前窗口有效计算能扩展的最大长度 missing (cards[right] - cards[left]) - (right - left) remaining wildcards - missing current_min max(cards[left] - remaining, 1) current_max min(cards[right] remaining, 13) current_len current_max - current_min 1 max_len max(max_len, current_len) # 3. 考虑完全使用癞子的情况 max_len max(max_len, min(wildcards, 13)) return max_len if __name__ __main__: # 测试用例 hand1 [1, 3, 4, 5, 6, 7, 9] wildcards1 2 print(f手牌: {hand1}, 癞子: {wildcards1}) print(f最长顺子长度: {longest_straight(hand1, wildcards1)}) # 输出 9 hand2 [5, 5, 5, 8, 8, 9, 10] wildcards2 1 print(f\n手牌: {hand2}, 癞子: {wildcards2}) print(f最长顺子长度: {longest_straight(hand2, wildcards2)}) # 输出 5 # 边界测试空手牌很多癞子 hand3 [] wildcards3 5 print(f\n手牌: {hand3}, 癞子: {wildcards3}) print(f最长顺子长度: {longest_straight(hand3, wildcards3)}) # 输出 5 # 边界测试手牌分散癞子少 hand4 [1, 5, 10, 13] wildcards4 1 print(f\n手牌: {hand4}, 癞子: {wildcards4}) print(f最长顺子长度: {longest_straight(hand4, wildcards4)}) # 输出 2 (例如[1,2]或[12,13])Python实现要点极致简洁sorted(set(hand))一行完成去重排序充分体现了Python的内建函数优势。清晰的循环for right in range(n):和while ...:逻辑与算法描述高度一致。可读性极强的表达式计算missing和current_len的公式一目了然。丰富的测试用例在main函数中包含了多种边界情况测试便于验证。4. 算法核心滑动窗口的变体与复杂度分析4.1 为何是滑动窗口与其他算法的对比除了滑动窗口我们可能会想到其他方法比如动态规划(DP)或回溯搜索。我们来简单分析一下动态规划DP通常适用于具有最优子结构的问题。对于“最长顺子”一个区间的最优解并不直接依赖于其子区间的最优解因为癞子是可以全局调配的稀缺资源子区间用掉癞子会影响父区间。定义状态以哪个点结尾用了多少癞子会比较复杂且状态转移不直观。时间复杂度也可能较高。回溯/DFS可以枚举每张癞子牌替换成什么点数但癞子数量稍多比如5个搜索空间就会爆炸13^5不可行。排序后贪心一种贪心思路是从每个点开始尽可能往后延伸。这本质上就是滑动窗口的单向移动因为窗口右边界拓展时左边界没必要回退回退只会让窗口变小。所以滑动窗口是这种贪心策略的高效实现。因此滑动窗口是解决此类“在有序序列上寻找满足某条件的最长连续子区间”问题的最优解之一。它的时间复杂度是O(n log n)主要消耗在排序上滑动窗口过程本身是O(n)。空间复杂度是O(n)或O(1)如果允许修改原数组并去重但通常需要额外空间存储去重排序后的数组。4.2 滑动窗口中的关键公式推导再探讨我们反复使用的公式missing (cards[right] - cards[left]) - (right - left)是算法的灵魂。我们来彻底理解它cards[right] - cards[left]表示从cards[left]到cards[right]这个数值范围的跨度。例如cards[left]3,cards[right]9那么跨度是6意味着完美的连续序列应该是3,4,5,6,7,8,9共7个数。right - left表示在cards数组中从索引left到right之间实际拥有的不同点数的数量。因为数组已排序去重这个值就是区间内不同牌的张数减1不对应该是(right - left)。当left0, right2时区间有3张牌right-left2。所以(right - left)是区间内“间隔”的数量比牌数少1。那么(cards[right] - cards[left]) - (right - left)计算的是什么呢(cards[right] - cards[left])是数值跨度的长度(right - left)是实际拥有的“步数”。它们的差值就是数值跨度长度与实际步数之间的“差额”这个差额正好等于区间内缺失的连续整数的个数。举例cards [3, 5, 9],left0,right2。cards[right]-cards[left] 9-36。right-left 2-02。missing 6 - 2 4。 检查从3到9连续整数是3,4,5,6,7,8,9。我们实际有3,5,9。缺失了4,6,7,8。确实是4个。公式正确。4.3 多语言实现的细微差异与选择建议虽然四份代码算法核心一致但语言特性带来了细微差别去重排序Cunordered_setvectorsort。步骤清晰性能可控。JavaHashSetArrayListCollections.sort。面向对象风格稳健。JavaScript[...new Set(arr)]sort((a,b)a-b)。极其简洁但要注意排序回调。Pythonsorted(set(hand))。简洁之王表达力无敌。代码风格与性能C追求极致性能时首选尤其当hand很大时。手动控制内存和循环。Java大型项目、团队协作时的安全选择有完善的异常处理和生态工具。JavaScript全栈开发、快速原型、Web相关场景的必然选择。代码短小精悍。Python算法面试、数据分析、脚本编写的利器。代码几乎就是伪代码开发效率最高。选择建议如果你在准备华为OD机试官方通常支持C/Java/Python/JavaScript。根据你最熟悉的语言选择。从解题速度看Python往往是首选因为写起来快不容易在语法上出错。如果题目对时间复杂度要求极其苛刻可能C更有优势。如果是在实际工程项目中需要类似逻辑考虑团队的技术栈和项目的性能要求。5. 常见陷阱、调试技巧与扩展思考5.1 实战中容易踩的“坑”忽略去重这是最常见的错误。手中有多张相同点数的牌在顺子中只能算一张。不去重会导致missing计算错误。忘记排序滑动窗口的前提是数据有序。如果直接对原数组滑动结果毫无意义。边界条件处理不当空输入手牌列表为空时应直接返回min(wildcards, 13)。点数越界计算currentMin和currentMax时一定要用max(1, ...)和min(13, ...)卡住边界。否则可能出现0或14这样的非法点数导致长度计算错误。癞子数很多如果癞子数量wildcards大于等于12理论上可以直接组成从1到13的顺子长度为13。我们的算法中最后的max(maxLen, min(wildcards, 13))能覆盖这种情况但窗口计算过程中也可能得出更大值受限于手牌位置。需要确保逻辑一致。“富余癞子”使用错误在计算当前窗口最大长度时错误地认为长度就是(right-left1) wildcards。这是不对的因为wildcards中的一部分已经用于填补missing了富余的是wildcards - missing。而且富余的癞子可以加在两边但受限于1-13范围。滑动窗口收缩条件while循环里的条件是(cards[right] - cards[left]) - (right - left) wildcards。注意是而不是。如果缺失数等于癞子数窗口仍然是有效的可以继续尝试扩展右边界或计算长度。5.2 调试与验证方法构造极端测试用例手牌为空癞子为0、5、20。手牌为[1,13]癞子为0、11、12。手牌密集[1,2,3,4,5,6,7,8,9,10,11,12,13]癞子为0。手牌极度分散[1, 13]癞子为1。最长顺子应该是2[1,2]或[12,13]而不是3因为一个癞子无法连接1和13。包含重复牌[2,2,2,2,5,5,5]癞子为2。打印中间变量在循环中打印left,right,missing,currentMin,currentMax,currentLength观察其变化是否符合预期。手动模拟对于小规模例子用纸笔走一遍算法流程这是理解算法和发现逻辑错误的最佳方式。对拍用两种不同的思路比如一种朴素的贪心枚举写一个暴力但正确的程序用于验证滑动窗口算法在小数据规模下的正确性。5.3 问题扩展与变种如果A可以当作14即点数范围是1-14只需要修改边界条件将上界13改为14即可。但需要注意A作为1和14有时可能同时存在题目通常会明确说明如何处理。在我们的模型中如果A是1那么它就在数组里如果A是14那就是另一个值。不会同时存在。如果癞子牌有不同类型如可以代替任何牌但每种点数最多代替一张这和我们当前模型一致。如果要求输出最长的顺子具体是什么算法需要稍作修改。在记录maxLen的同时还需要记录取得最大长度时的currentMin和currentMax。最后生成从currentMin到currentMax的序列即可注意有些位置是癞子填补的。如果手牌是字符串如[“A”, “2”, “J”, “Q”, “K”]需要先建立一个映射关系将牌面字符映射到数字A-1, J-11, Q-12, K-13然后套用上述算法。更一般的“最长连续序列”问题LeetCode 128. Longest Consecutive Sequence那道题不允许有“癞子”且要求O(n)时间复杂度。解法是利用哈希集合HashSet实现O(1)查找然后对于每个序列的起始数字即num-1不在集合中的数字不断查找num1是否存在。我们的问题因为允许填补空缺癞子所以解法不同。6. 在华为OD机试中的应试策略与总结回到最初的场景——华为OD机试。这道“最长的顺子”题考察点非常明确基础数据结构能力对数组进行去重、排序的操作。算法应用能力识别出这是滑动窗口/双指针问题并正确实现。边界处理与细节实现正确处理去重、排序、点数边界、癞子计算等细节。代码健壮性考虑空输入、极端值等情况。时间复杂度分析能够说明算法的时间复杂度O(n log n)和空间复杂度O(n)或O(1)。应试建议优先选择Python或Java除非你C非常熟练否则Python的简洁语法能帮你节省大量编码时间减少低级错误。Java的严谨性也有助于写出健壮的代码。先写思路注释在代码开头或关键步骤前用注释写明算法步骤这有助于阅卷如果是人工阅卷和自己在编码时理清逻辑。写完先跑样例利用题目给出的示例快速验证。华为OD的机试环境通常允许运行和调试。检查边界专门用几分钟思考并测试边界情况。时间与空间复杂度即使题目没要求也最好在注释中写明展示你的专业素养。这道题本身不难但完美实现需要细心。它很像一个缩影华为OD的很多机试题都具备这种特点题目背景易于理解如扑克牌但需要你将实际问题抽象为恰当的算法模型并严谨地实现。通过这道题的多语言解法和深度剖析希望你能掌握的不只是这一个问题的答案更是解决一类问题的方法和应对机试的实战策略。在真正的考场上冷静分析把问题拆解为你熟悉的数据结构和算法模型然后像我们上面所做的那样一步步用代码构建起你的解决方案。
