华为OD机试 - SQL记录拆分 - 并查集（Java 新系统 200分）

华为OD机试 新系统 题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

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

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

二、输入描述

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

三、输出描述

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

补充说明：

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

测试用例1：

1、输入

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

2、输出

1

3、说明

第一行同时存在 T1、T2，第二行存在 T1，因此两行属于同一约束组，共 2 行。2 <= 3，只需要 1 个文件。

测试用例2：

1、输入

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

2、输出

2

3、说明

T1 对应第 1、3 行，共 2 行；T2 对应第 2、4 行，共 2 行。第一个组装满第一个文件，第二个组必须创建第二个文件。

五、解题思路

把sql_text中的每个数组成员看作一个“行节点”。同一数组成员无论包含多少个用;分隔的 SQL，都必须完整保存，因此它始终只占 1 行，不需要按分号再次拆分；像;、;;这样的空语句所在数组成员同样按 1 行计算。

核心难点是事务标签产生的传递约束。例如第 1 行含[T1]，第 2 行同时含[T1]、[T2]，第 3 行含[T2]，那么三行必须全部位于同一个文件。这个问题本质上是在求“必须同文件”关系形成的连通分量，因此使用并查集 DSU。

扫描每一行，用正则提取[Tn]。用 HashMap 记录每个事务标签第一次出现的行号；后续再次遇到同一标签时，将当前行和第一次出现的行执行 union。若一行包含多个事务标签，该行会同时参与多个 union，从而自然完成传递合并。

所有事务处理完后，统计每个并查集连通分量包含多少行，即一个不可拆分语句组的大小。

接下来必须按照“语句组首次出现的行号”处理。无需排序：直接再次按照原始行号从前往后扫描，某个并查集根节点第一次被访问时，就代表该语句组第一次出现。然后采用贪心策略：当前文件能完整容纳该组就加入；否则新建文件。若某个组自身行数已经超过 split_line，也不能拆分，仍整体占用一个文件。

时间复杂度约为O(L + N·α(N))，其中 L 为所有 SQL 文本总字符数，N 为数组行数；空间复杂度为O(N + T)，T 为事务标签数量。

六、Java算法源码

publicclassOdTest{publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);StringfirstLine=scanner.nextLine().trim();intsplitLine=Integer.parseInt(firstLine);List<String>sqlText=newArrayList<>();/* * split_line 后面的每一行都视为 sql_text 的一个数组成员。 * * 这里不能根据 ';' 再拆分，因为题目明确规定： * 一个数组成员中的 SQL 必须作为完整的一行保存。 * * 空白行本身也可以表示一个数组成员。 */while(scanner.hasNextLine()){Stringinput=scanner.nextLine();if(!input.contains(";")){break;}sqlText.add(input);}System.out.println(splitFileCount(splitLine,sqlText));}/** * 并查集： * 用于维护哪些 SQL 行由于事务约束而必须放在同一个文件中。 */privatestaticclassDSU{int[]parent;int[]rank;DSU(intn){parent=newint[n];rank=newint[n];for(inti=0;i<n;i++){parent[i]=i;}}/** * 查找节点所属集合的根节点。 * 使用路径压缩降低后续查询开销。 */intfind(intx){if(parent[x]!=x){parent[x]=find(parent[x]);}returnparent[x];}/** * 合并两个 SQL 行所在的集合。 */voidunion(inta,intb){introotA=find(a);introotB=find(b);if(rootA==rootB){return;}// 按秩合并，避免并查集退化成链表if(rank[rootA]<rank[rootB]){parent[rootA]=rootB;}elseif(rank[rootA]>rank[rootB]){parent[rootB]=rootA;}else{parent[rootB]=rootA;rank[rootA]++;}}}/** * 计算最终需要拆分成多少个文件。 */publicstaticintsplitFileCount(intsplitLine,List<String>sqlText){// split_line 不合法，或者 SQL 数组为空，直接返回 0if(splitLine<1||splitLine>10000||sqlText==null||sqlText.isEmpty()){return0;}intn=sqlText.size();// 每个数组成员都是一个不可拆分的“SQL 行节点”DSUdsu=newDSU(n);/* * key : 事务编号，例如 [T10] 中的 10 * value : 该事务第一次出现在哪一行 * * 后续再次遇到同一个事务时，只需要和第一次出现的行合并。 */Map<Integer,Integer>firstLineByTransaction=newHashMap<>();// 匹配 [T1]、[T23]、[T1000] 等事务标签PatterntagPattern=Pattern.compile("\\[T(\\d+)\\]");for(inti=0;i<n;i++){Stringline=sqlText.get(i);if(line==null){line="";}Matchermatcher=tagPattern.matcher(line);while(matcher.find()){inttag;try{tag=Integer.parseInt(matcher.group(1));}catch(NumberFormatExceptione){continue;}// 题目规定事务标签范围为 [1, 1000]if(tag<1||tag>1000){continue;}IntegerfirstLine=firstLineByTransaction.get(tag);if(firstLine==null){// 当前事务第一次出现firstLineByTransaction.put(tag,i);}else{/* * 同一事务的 SQL 行必须保存在同一个文件中， * 因此将当前行和该事务第一次出现的行合并。 * * 如果当前一行同时出现 [T1]、[T2]， * 那么当前行会分别和 T1、T2 对应的行执行 union， * 从而自动完成 A-B、B-C => A-B-C 的传递约束。 */dsu.union(i,firstLine);}}}/* * 统计每个连通分量包含多少个数组成员。 * 每个连通分量就是一个绝对不能拆开的 SQL 语句组。 */int[]groupSize=newint[n];for(inti=0;i<n;i++){introot=dsu.find(i);groupSize[root]++;}/* * 题目要求按照“语句组首次出现的行号”处理。 * * 不需要额外排序： * 直接按照原数组 0、1、2... 顺序扫描， * 某个根节点第一次被遇到的位置， * 天然就是该语句组首次出现的位置。 */boolean[]processed=newboolean[n];intfileCount=0;intusedLines=0;for(inti=0;i<n;i++){introot=dsu.find(i);// 该事务组之前已经处理过if(processed[root]){continue;}processed[root]=true;intsize=groupSize[root];if(fileCount==0){// 第一个语句组创建第一个文件fileCount=1;usedLines=size;}elseif(usedLines+size<=splitLine){/* * 当前文件能够完整容纳整个语句组， * 根据题目“优先放入当前文件”的要求直接加入。 */usedLines+=size;}else{/* * 当前文件装不下整个组，只能创建新文件。 * * 注意：如果 size 本身已经大于 splitLine， * 根据题目规则也不能拆分，仍然整体放进一个新文件。 */fileCount++;usedLines=size;}}returnfileCount;}}

七、效果展示

1、输入

2
;
A;
;;
B;
C;

2、输出

3

3、说明

共有 5 个数组成员，每个成员都按 1 行计算。; 和 ;; 虽然是空语句，但所在数组成员仍然占 1 行。每个文件最多 2 行，因此需要 2 + 2 + 1，共 3 个文件。

🏆下一篇：华为OD机试 - 简易内存池 - 逻辑分析（Java 新系统 200分）

🏆本专栏收录于《华为OD机试（JAVA）真题》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。