|

2026 华为OD机试真题 7月1日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

某分布式数据库系统需要将 SQL 操作日志拆分到多个文件中，现给定一组 SQL 语句输入（数组格式），请按要求将 SQL 语句拆分到不同文件中并返回拆分后的文件数量。拆分规则如下：

1. 单个数组成员的 SQL 语句（可能包含多条，按 ; 分隔）按同一行完整保存，不可跨文件拆分，且同一行的语句必须在同一个文件中。
2. 部分语句带事务标签 [Tn]（n 为正整数），如 [T1]A；相同事务标签的 SQL 语句必须保存于同一文件中。
3. 当单个文件保存的行数超出限制时，需要新建文件；按语句组首次出现的行号顺序处理，优先放入当前文件，超出限制则新建文件；
4. 特殊场景约束：若语句 A 与语句 B 必须同文件，语句 B 与语句 C 必须同文件，则语句 A、B、C 必须在同一文件（约束传递性）。约束合并后语句组计数即便超过限制也必须放在同一文件；
5. SQL 数组为空时返回 0。

2026 华为OD机试真题 7月1日华为OD上机新系统考试真题 100 分题型

输入描述

参数1：单个文件限定可保存的最大 SQL 语句行数 split_line；\ 参数2：SQL 语句数组 sql_text，每个数组成员可能包含多条 SQL 语句，用符号 ; 分隔；

输出描述

SQL 语句数组按规则拆分后的文件个数。

补充说明

• split_line 取值范围 [1, 10000]，无效值返回 0；
• sql_text 每行最多 1000 字符，总语句最多 100000 条；
• 事务标签的范围 [1, 1000]；
• 最后一条语句可以没有分号结尾；
• 空语句（仅含分号）按 1 行计算。

示例1

输入

3,["[T1]A;[T2]B;","[T1]C;"]

输出

1

说明

• 语句 [T1]A 和 [T2]B 共享 1 行，必须同文件；
• [T1]A 和 [T1]C 同属 T1 事务，必须同文件；
• 传递约束下三条语句同属一组，数组成员下标 {0,1} 共 2 行，不超过 3，故 1 个文件。

示例2

输入

2,["[T1]A;","[T2]B;","[T1]C;","[T2]D;"]

输出

2

说明

• T1 事务包含 A 和 C，数组成员下标 {0,2} 占 2 行；
• T2 事务包含 B 和 D，数组成员下标 {1,3} 占 2 行；
• T1 先出现，放入文件 1（2 行），T2 另建文件 2（2 行），共 2 个文件。

示例4

输入

1,[]

输出

说明

空输入返回 。

解题思路

核心思想

本题本质上是一个图的连通分量划分问题，通过并查集处理事务标签的传递约束，然后采用贪心算法分配文件。

算法步骤

1. 合法性校验：检查 split_line 是否在 [1, 10000] 范围内，以及数组是否为空。

2. 提取事务标签：遍历每一行 SQL，解析每条语句中的 [Tn] 标签，建立 tag → {行号集合} 的映射。

3. 并查集合并：对于每个事务标签，包含该标签的所有行号需要合并到同一集合，利用并查集的 union 操作处理传递约束。

4. 分组统计：遍历所有行，按并查集的根节点分组，每个连通分量内的行必须放在同一文件。

5. 贪心分配文件：按各组首次出现的行号排序，依次尝试放入当前文件；若放入后超过 split_line 限制，则新建文件。

复杂度分析

• 时间复杂度：O(n × m)，其中 n 为 SQL 行数，m 为每行的平均语句数。并查集操作近乎常数时间。
• 空间复杂度：O(n) 用于存储并查集和分