【华为OD机试真题】手牌接龙 · 最大出牌次数（Python /JS）

一、真题题目描述手里给一副手牌数字从0-9有(红色)g(绿色)b(蓝色)y(黄色)四种颜色出牌规则为每次打出的牌必须跟上一张的数字或者颜色相同否则不能抽选。选手应该怎么选才能使得抽选的次数最大并且输出这个最大次数。输入描述第一行牌的数值n(1n9)·第二行牌的颜色(r,g,b,y四种颜色表示)输出描述输出最大出牌数量0示例1【输入输出示例仅供调试后台判题数据一般不包含示例】输入1 4 3 4 5r y b b r输出3说明如果打(1,r)-(5,r)那么能打两张。如果打(4,y)-(4,b)-(3,b)那么能打三张。二、题目深度解析这道题的本质是在一个无向图或者是根据规则构建的有向图中寻找最长简单路径。节点每一张手牌。边如果两张牌数字相同或颜色相同则存在连接。约束每个节点只能访问一次。 解题思路由于 N 非常小最大为 9全排列的数量 9!362,880 对计算机来说微不足道。因此我们不需要复杂的动态规划或剪枝优化直接使用回溯法 (Backtracking)即可枚举起点最长序列的起始牌可能是任意一张因此我们需要外层循环遍历所有牌作为起点。深度搜索 (DFS)从当前牌出发遍历所有未使用的牌。检查是否满足接龙规则数字同 OR 颜色同。若满足标记该牌为“已使用”递归进入下一层路径长度 1。状态回溯递归返回后必须将该牌标记回“未使用”。这是回溯法的灵魂确保其他分支也能尝试使用这张牌。更新全局最大值在搜索的每一步都尝试更新记录到的最大长度。三、Python 实现 (简洁优雅风)Python 的代码极其精炼利用列表推导式和元组 unpacking可以让逻辑一目了然。import sys # 设置递归深度虽然 N9 不需要但养成好习惯 sys.setrecursionlimit(2000) def solve(): # 读取所有输入令牌 input_data sys.stdin.read().split() if not input_data: return iterator iter(input_data) try: n int(next(iterator)) except StopIteration: return numbers [] for _ in range(n): numbers.append(int(next(iterator))) colors [] for _ in range(n): colors.append(next(iterator)) # 组合成手牌列表: [(num, color), ...] cards list(zip(numbers, colors)) # 标记数组记录每张牌是否被使用 used [False] * n max_len 0 def dfs(last_idx, current_count): nonlocal max_len # 更新最大值 if current_count max_len: max_len current_count # 尝试接下一张牌 last_num, last_col cards[last_idx] for i in range(n): if not used[i]: curr_num, curr_col cards[i] # 规则判断数字相同 或 颜色相同 if curr_num last_num or curr_col last_col: used[i] True dfs(i, current_count 1) used[i] False # 回溯 # 枚举每一张牌作为起点 for i in range(n): used[i] True dfs(i, 1) used[i] False # 恢复状态以便下一次循环作为起点 print(max_len) if __name__ __main__: solve()✅ Python 版亮点输入处理sys.stdin.read().split()一次性读取并分割所有输入完美处理数字和颜色分两行输入的格式无需关心换行符。数据结构使用zip将数字和颜色打包成元组列表访问方便。闭包与 Nonlocal内部函数dfs直接访问外部变量max_len和used代码结构紧凑无需传过多的参数。逻辑清晰used[i] True-dfs-used[i] False的回溯三部曲非常直观。四、JavaScript (Node.js) 实现 (异步流处理)在 Node.js 中处理标准输入通常是异步的。我们需要确保所有数据读取完毕后再开始计算。const readline require(readline); function main() { const rl readline.createInterface({ input: process.stdin, output: process.stdout }); const lines []; // 监听每一行输入 rl.on(line, (line) { lines.push(line.trim()); }); // 输入结束时处理逻辑 rl.on(close, () { // 将所有行合并并按空格分割成令牌数组 const tokens lines.join( ).split(/\s/).filter(t t ! ); if (tokens.length 0) return; let idx 0; const n parseInt(tokens[idx], 10); const numbers []; for (let i 0; i n; i) { numbers.push(parseInt(tokens[idx], 10)); } const colors []; for (let i 0; i n; i) { colors.push(tokens[idx]); } // 组合手牌 const cards []; for (let i 0; i n; i) { cards.push({ num: numbers[i], col: colors[i] }); } const used new Array(n).fill(false); let maxLen 0; // DFS 函数 function dfs(lastIdx, currentCount) { if (currentCount maxLen) { maxLen currentCount; } const lastCard cards[lastIdx]; for (let i 0; i n; i) { if (!used[i]) { const currCard cards[i]; // 规则判断 if (currCard.num lastCard.num || currCard.col lastCard.col) { used[i] true; dfs(i, currentCount 1); used[i] false; // 回溯 } } } } // 枚举起点 for (let i 0; i n; i) { used[i] true; dfs(i, 1); used[i] false; } console.log(maxLen); }); } main();✅ JavaScript 版亮点健壮的输入流通过rl.on(close)确保所有数据包括跨行的数字和颜色都读取完毕后再统一解析。避免了异步读取导致的数据缺失问题。对象数组使用{ num, col }对象存储手牌语义清晰。作用域链dfs函数作为内部函数可以直接访问cards,used,maxLen等变量保持了代码的整洁性。严格相等使用进行比较符合 JS 最佳实践。五、深度解析回溯法的“现场恢复”这道题最容易出错的地方在于回溯步骤的遗漏。错误示范if condition: used[i] True dfs(i, count 1) # 忘记写 used[i] False后果假设路径 A 使用了牌 X递归结束后如果没有将 X 标记回False那么当算法尝试探索路径 B 时会发现 X 已经被占用从而跳过 X。这会导致很多合法的长路径被错误地截断最终结果偏小。正确逻辑想象你在走迷宫每走过一个路口插上一面旗帜used True。当你发现这条路走不通或者想尝试另一条路时必须拔掉旗帜used False把路口恢复原状这样后续的探索者其他递归分支才能再次通过这个路口。六、常见陷阱与注意事项⚠️起点的选择题目没有规定第一张出什么牌。很多人只从第 0 张牌开始 DFS这是错误的。必须在外层循环遍历0到n-1让每一张牌都有机会做“领头羊”。输入解析输入分为两行第一行全是数字第二行全是颜色。Python 的input().split()如果只调用两次会分别得到两行数据。需要小心处理索引对应关系第 ii 个数字对应第 ii 个颜色。本代码采用“扁平化”读取所有 token 的策略彻底规避了行对齐的问题。边界条件N1 时循环执行一次输出 1逻辑正确。没有任何牌能相连时最大值应为 1因为至少可以出一张牌代码逻辑天然支持这一点。七、复杂度分析时间复杂度 O(N!) 。在最坏情况下所有牌都能互连算法需要遍历全排列。对于 N9 9!≈3.6×105 在现代 CPU 上Python 和 JS 都能在几十毫秒内完成计算完全满足机考的时间限制通常为 1-2 秒。空间复杂度 O(N) 。主要用于递归调用栈深度最大为 N 和used数组。八、总结无论是Python的极简主义还是JavaScript的异步流处理解决这类问题的核心都在于对回溯状态的精准控制。Python 选手享受列表操作和闭包带来的便利用最少代码解决复杂问题。JS 选手掌握readline模块处理多行输入的技巧是前端/全栈工程师应对后端算法题的关键。这道题虽然数据规模小但它完美展示了暴力搜索 剪枝/回溯的思想。在数据规模允许的情况下这往往是最快写出且最不容易出错的方案。希望这篇博文能助你顺利拿下华为 OD 机考如果觉得有用请点赞、收藏⭐、评论支持一下