全网最全面的华为OD机试真题汇总,100%原题题库,不需要开会员即可查看全部内容,更多考题请查看真题库。
真题库:https://www.yuque.com/codernav.com/od
题目:关联端口组合并
时间限制:1s 空间限制:256MB 限定语言:不限
题目描述:
有M(1<=M<=10)个端口组,每个端口组是长度为N(1<=N<=100)的整数数组,如果端口组间存在2个及以上不同端口相同,则认为这两个端口组互相关联,可以合并。
第一行输入端口组个数M,再输入M行,每行逗号分隔,代表端口组,输出合并后的端口组用二维数组表示
输入描述:
端口组内数字可以重复
输出描述:
1.组内相同端口仅保留一个,从小到大排序。
2.组外顺序保持输入顺序
补充说明:
M,N不再限定范围内,统一输出一组空数组[[]]
示例1
输入:
4
4
2,3,2
1,2
5
输出:
[[4],[2,3],[1,2],[5]]
说明:
仅有一个端口2相同,不可以合并
示例2
输入:
3
2,3,1
4,3,2
5
输出:
[[1,2,3,4],[5]]
说明:
存在两个2,3有交集,可以合并
示例3
输入:
6
10
4,2,1
9
3,6,9,2
6,3,4
8
输出:
[[10],[1,2,3,4,6,9],[9],[8]]
示例4
输入:
11
输出:
[[]]
说明:
11超出范围,输出[[]]
解题思路:
将输入的组合转化为set集合(有去重和排序的功能),加入list集合中
每输入一个组合,则对list进行遍历,找出其中有两个并集的集合进行合并,合并完加入原来list集合中。再次执行步骤2
注意:两个需要合并的集合都需要从list中删除,且并集需要加在靠前的位置(题目要求组外保持输入顺序)
代码实现一:
package com.codernav.demo.hwod.exam; import java.util.*; /** * @title 关联端口组合并 * @Description 有M(1<=M<=10)个端口组,每个端口组是长度为N(1<=N<=100)的整数数组,如果端口组间存在2个及以上不同端口相同,则认为这两个端口组互相关联,可以合并。 * 第一行输入端口组个数M,再输入M行,每行逗号分隔,代表端口组,输出合并后的端口组用二维数组表示 * @Author 开发者导航 * @website https://codernav.com * @date 2023/5/13 */ public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int M = sc.nextInt(); if (M > 10) { System.out.println("[[]]"); } else { List<Set<String>> list = new ArrayList<>(); sc.nextLine(); for (int i = 0; i < M; i++) { String[] strings = sc.nextLine().split(","); Set<String> set = new TreeSet<>(); if (strings.length == 1) { //只有一个元素直接添加 set.add(strings[0]); list.add(set); } else { //数组转化为set集合 set.addAll(Arrays.asList(strings)); list.add(set); merge(set, list, list.size() - 1); } } System.out.println(list); } } /** * 合并关联端口组合 * * @param set 进行合并的端口组合 * @param list 端口组合集合 * @param index 需要进行合并的组合索引 */ public static void merge(Set<String> set, List<Set<String>> list, int index) { for (int i = 0; i < list.size(); i++) { if (i == index) { continue; } Set<String> setIndex = list.get(i); //当前索引的set集合 Set<String> setTemp = new TreeSet<>(); setTemp.addAll(set); setTemp.retainAll(setIndex); //求出set和setIndex的交集 if (setTemp.size() >= 2) { //交集大于等于2则合并 set.addAll(setIndex); //set与setIndex合并 int beforeIndex = Math.min(index, i); //求出排在前面的index int afterIndex = beforeIndex == index ? i : index; //靠后的位置 list.remove(afterIndex); //合并的两个set进行删除,先删除后面的一个 list.remove(beforeIndex); list.add(beforeIndex, set); //将新的set放在前面位置 merge(set, list, beforeIndex); //将新建的组合再进行判断合并 } } } }