华为OD机试 新系统 题库疯狂收录中刷题点这里专栏导读本专栏收录于《华为OD机试JAVA真题》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。一、题目描述某分布式数据库 Q 系统需要将 SQL 操作日志拆分到多个文件中现给定一组 SQL 语句输入数组格式请按要求将 SQL 语句拆分到不同文件中并返回拆分后的文件数量。拆分规则如下单个数组成员的 SQL 语句可能包含多条按;分隔按同一行完整保存不可跨文件拆分且同一行的语句必须在同一个文件中。部分语句带事务标签[Tn]n为正整数如[T1]A相同事务标签的 SQL 语句必须保存于同一文件中。当单个文件保存的行数超出限制时需要新建文件按语句组首次出现的行号顺序处理优先放入当前文件超出限制则新建文件特殊场景约束若语句 A 与语句 B 必须同文件语句 B 与语句 C 必须同文件则语句 A、B、C 必须在同一文件约束传递性。约束合并后语句组计数即便超过限制也必须放在同一文件SQL 数组为空时返回 0。二、输入描述输入参数1单个文件限定可保存的最大 SQL 语句行数split_line参数2SQL 语句数组sql_text每个数组成员可能包含多条 SQL 语句用符号;分隔三、输出描述SQL 语句数组按规则拆分后的文件个数。补充说明split_line取值范围[1, 10000]无效值返回 0sql_text每行最多 1000 字符总语句最多 100000 条事务标签的范围[1, 1000]最后一条语句可以没有分号结尾空语句仅含分号按 1 行计算。## 四、测试用例测试用例11、输入3[T1]A;[T2]B;[T1]C;2、输出13、说明第一行同时存在 T1、T2第二行存在 T1因此两行属于同一约束组共 2 行。2 3只需要 1 个文件。测试用例21、输入2[T1]A;[T2]B;[T1]C;[T2]D;2、输出23、说明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){ScannerscannernewScanner(System.in);StringfirstLinescanner.nextLine().trim();intsplitLineInteger.parseInt(firstLine);ListStringsqlTextnewArrayList();/* * split_line 后面的每一行都视为 sql_text 的一个数组成员。 * * 这里不能根据 ; 再拆分因为题目明确规定 * 一个数组成员中的 SQL 必须作为完整的一行保存。 * * 空白行本身也可以表示一个数组成员。 */while(scanner.hasNextLine()){Stringinputscanner.nextLine();if(!input.contains(;)){break;}sqlText.add(input);}System.out.println(splitFileCount(splitLine,sqlText));}/** * 并查集 * 用于维护哪些 SQL 行由于事务约束而必须放在同一个文件中。 */privatestaticclassDSU{int[]parent;int[]rank;DSU(intn){parentnewint[n];ranknewint[n];for(inti0;in;i){parent[i]i;}}/** * 查找节点所属集合的根节点。 * 使用路径压缩降低后续查询开销。 */intfind(intx){if(parent[x]!x){parent[x]find(parent[x]);}returnparent[x];}/** * 合并两个 SQL 行所在的集合。 */voidunion(inta,intb){introotAfind(a);introotBfind(b);if(rootArootB){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,ListStringsqlText){// split_line 不合法或者 SQL 数组为空直接返回 0if(splitLine1||splitLine10000||sqlTextnull||sqlText.isEmpty()){return0;}intnsqlText.size();// 每个数组成员都是一个不可拆分的“SQL 行节点”DSUdsunewDSU(n);/* * key : 事务编号例如 [T10] 中的 10 * value : 该事务第一次出现在哪一行 * * 后续再次遇到同一个事务时只需要和第一次出现的行合并。 */MapInteger,IntegerfirstLineByTransactionnewHashMap();// 匹配 [T1]、[T23]、[T1000] 等事务标签PatterntagPatternPattern.compile(\\[T(\\d)\\]);for(inti0;in;i){StringlinesqlText.get(i);if(linenull){line;}MatchermatchertagPattern.matcher(line);while(matcher.find()){inttag;try{tagInteger.parseInt(matcher.group(1));}catch(NumberFormatExceptione){continue;}// 题目规定事务标签范围为 [1, 1000]if(tag1||tag1000){continue;}IntegerfirstLinefirstLineByTransaction.get(tag);if(firstLinenull){// 当前事务第一次出现firstLineByTransaction.put(tag,i);}else{/* * 同一事务的 SQL 行必须保存在同一个文件中 * 因此将当前行和该事务第一次出现的行合并。 * * 如果当前一行同时出现 [T1]、[T2] * 那么当前行会分别和 T1、T2 对应的行执行 union * 从而自动完成 A-B、B-C A-B-C 的传递约束。 */dsu.union(i,firstLine);}}}/* * 统计每个连通分量包含多少个数组成员。 * 每个连通分量就是一个绝对不能拆开的 SQL 语句组。 */int[]groupSizenewint[n];for(inti0;in;i){introotdsu.find(i);groupSize[root];}/* * 题目要求按照“语句组首次出现的行号”处理。 * * 不需要额外排序 * 直接按照原数组 0、1、2... 顺序扫描 * 某个根节点第一次被遇到的位置 * 天然就是该语句组首次出现的位置。 */boolean[]processednewboolean[n];intfileCount0;intusedLines0;for(inti0;in;i){introotdsu.find(i);// 该事务组之前已经处理过if(processed[root]){continue;}processed[root]true;intsizegroupSize[root];if(fileCount0){// 第一个语句组创建第一个文件fileCount1;usedLinessize;}elseif(usedLinessizesplitLine){/* * 当前文件能够完整容纳整个语句组 * 根据题目“优先放入当前文件”的要求直接加入。 */usedLinessize;}else{/* * 当前文件装不下整个组只能创建新文件。 * * 注意如果 size 本身已经大于 splitLine * 根据题目规则也不能拆分仍然整体放进一个新文件。 */fileCount;usedLinessize;}}returnfileCount;}}七、效果展示1、输入2;A;;;B;C;2、输出33、说明共有 5 个数组成员每个成员都按 1 行计算。; 和 ;; 虽然是空语句但所在数组成员仍然占 1 行。每个文件最多 2 行因此需要 2 2 1共 3 个文件。下一篇华为OD机试 - 简易内存池 - 逻辑分析Java 新系统 200分本专栏收录于《华为OD机试JAVA真题》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。