当前位置：首页 > news >正文

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

news 2026/3/26 22:57:36

一、真题

题目描述：
手里给一副手牌，数字从0-9，有(红色)，g(绿色)，b(蓝色)，y(黄色)四种颜色，出牌规则为每次打出的牌必须跟上一张的数
字或者颜色相同，否则不能抽选。
选手应该怎么选才能使得抽选的次数最大，并且输出这个最大次数。
输入描述
第一行牌的数值n(1<=n<=9)·第二行牌的颜色(r,g,b,y四种颜色表示)
输出描述
输出最大出牌数量0
示例1：
【输入输出示例仅供调试，后台判题数据一般不包含示例】
输入
1 4 3 4 5
r 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 # 设置递归深度，虽然 N=9 不需要，但养成好习惯 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 的策略，彻底规避了行对齐的问题。
边界条件：
- N=1 时，循环执行一次，输出 1，逻辑正确。
- 没有任何牌能相连时，最大值应为 1（因为至少可以出一张牌），代码逻辑天然支持这一点。

七、复杂度分析📊

时间复杂度： O(N!) 。
- 在最坏情况下（所有牌都能互连），算法需要遍历全排列。
- 对于 N=9 ，9!≈3.6×105 ，在现代 CPU 上，Python 和 JS 都能在几十毫秒内完成计算，完全满足机考的时间限制（通常为 1-2 秒）。
空间复杂度： O(N) 。
- 主要用于递归调用栈（深度最大为 N ）和used数组。