(100分)- 端口合并Java JS Python题目描述有M个端口组(1M10)每个端口组是长度为N的整数数组(1N100)如果端口组间存在2个及以上不同端口相同则认为这2个端口组互相关联可以合并。输入描述第一行输入端口组个数M再输入M行每行逗号分割代表端口组。备注端口组内数字可以重复。输出描述输出合并后的端口组用二维数组表示。组内相同端口仅保留一个从小到达排序。组外顺序保持输入顺序备注M,N不在限定范围内统一输出一组空数组[[]]用例输入442,3,21,25输出[[4],[2,3],[1,2],[5]]说明仅有一个端口2相同不可以合并。输入32,3,14,3,25输出[[1,2,3,4],[5]]说明无输入6104,2,193,6,9,26,3,48输出[[10],[1,2,3,4,6,9],[9],[8]]说明无输入11输出[[]]说明无题目解析本题有一个疑点如果端口组间存在2个及以上不同端口相同则认为这2个端口组互相关联可以合并。关于不同端口的具体含义以您提供的用例为例两个端口组都包含端口3和3这种情况是否可以合并呢23 3 51 3 3假设数组 a [3,3,5]b [1,3,3]其中a[0]与b[1]的值相同a[1]与b[2]的值也相同。这种情况下虽然端口位置不同但数值相同是否可以视为两个不同的端口匹配这个问题会导致两种不同的解题思路若两个端口组能形成两对数值相同的端口匹配即可进行合并必须形成两对数值不同的端口匹配才能进行合并如果能形成2个端口值相同的端口对那么也可以合并JavaScript算法源码/* JavaScript Node ACM模式 控制台输入获取 */ const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines []; let m; rl.on(line, (line) { lines.push(line); if (lines.length 1) { m lines[0] - 0; // M,N不在限定范围内统一输出一组空数组[[]] if (m 10 || m 1) { console.log([[]]); lines.length 0; return; } } if (m lines.length m 1) { lines.shift(); const ports lines.map((line) line.split(,).map(Number)); for (let port of ports) { const n port.length; // M,N不在限定范围内统一输出一组空数组[[]] if (n 1 || n 100) { console.log([[]]); lines.length 0; return; } } console.log(getResult(ports)); lines.length 0; } }); // 算法入口 function getResult(ports) { outer: while (true) { // 这里倒序遍历端口组是为了实现组外顺序保持输入顺序 for (let i ports.length - 1; i 0; i--) { for (let j i - 1; j 0; j--) { // 判断两个端口是否可以合并 if (canUnion(ports[i], ports[j])) { // 将后面的端口组并入前面的端口组这样就不会破坏组外顺序 ports[j].push(...ports[i]); ports.splice(i, 1); continue outer; } } } break; } const ans ports.map((port) [...new Set(port)].sort((a, b) a - b)); return JSON.stringify(ans); } // 如果端口组间存在2个及以上不同端口相同则认为这2个端口组互相关联可以合并。 // 下面方法实现中对于“不同端口”的理解是端口位置不同端口值可以相同即以不同位置的端口视为不同端口 function canUnion(port1, port2) { port1.sort((a, b) a - b); port2.sort((a, b) a - b); let same 0; let i 0; let j 0; while (i port1.length j port2.length) { if (port1[i] port2[j]) { i; j; if (same 2) return true; } else if (port1[i] port2[j]) { j; } else { i; } } return false; }Java算法源码import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int m Integer.parseInt(sc.nextLine()); // M,N不在限定范围内统一输出一组空数组[[]] if (m 10 || m 1) { System.out.println([[]]); return; } // 这里使用ArrayList接收端口组是为了后面更方便进行端口组之间的合并 ArrayListArrayListInteger ports new ArrayList(); for (int i 0; i m; i) { Integer[] tmp Arrays.stream(sc.nextLine().split(,)).map(Integer::parseInt).toArray(Integer[]::new); // M,N不在限定范围内统一输出一组空数组[[]] int n tmp.length; if (n 1 || n 100) { System.out.println([[]]); return; } ArrayListInteger tmpList new ArrayList(Arrays.asList(tmp)); ports.add(tmpList); } System.out.println(getResult(ports)); } // 算法入口 public static String getResult(ArrayListArrayListInteger ports) { outer: while (true) { // 这里倒序遍历端口组是为了实现组外顺序保持输入顺序 for (int i ports.size() - 1; i 0; i--) { for (int j i - 1; j 0; j--) { // 判断两个端口是否可以合并 if (canUnion(ports.get(i), ports.get(j))) { // 将后面的端口组并入前面的端口组这样就不会破坏组外顺序 ports.get(j).addAll(ports.get(i)); ports.remove(i); continue outer; } } } break; } StringJoiner out new StringJoiner(,, [, ]); for (ArrayListInteger port : ports) { StringJoiner in new StringJoiner(,, [, ]); for (Integer v : new TreeSetInteger(port)) { // 这里使用TreeSet是为了实现组内相同端口仅保留一个从小到达排序。 in.add(v ); } out.add(in.toString()); } return out.toString(); } // 如果端口组间存在2个及以上不同端口相同则认为这2个端口组互相关联可以合并。 // 下面方法实现中对于“不同端口”的理解是端口位置不同端口值可以相同即以不同位置的端口视为不同端口 public static boolean canUnion(ArrayListInteger port1, ArrayListInteger port2) { port1.sort((a, b) - a - b); port2.sort((a, b) - a - b); int same 0; int i 0; int j 0; while (i port1.size() j port2.size()) { if (port1.get(i) - port2.get(j) 0) { i; j; if (same 2) return true; } else if (port1.get(i) port2.get(j)) { j; } else { i; } } return false; } }Python算法源码import re # 如果端口组间存在2个及以上不同端口相同则认为这2个端口组互相关联可以合并。 # 下面方法实现中对于“不同端口”的理解是端口位置不同端口值可以相同即以不同位置的端口视为不同端口 def canUnion(port1, port2): port1.sort() port2.sort() same 0 i 0 j 0 while i len(port1) and j len(port2): if port1[i] port2[j]: i 1 j 1 same 1 if same 2: return True elif port1[i] port2[j]: j 1 else: i 1 return False # 从头开始尝试合并端口组 def forPorts(ports): # 这里倒序遍历端口组是为了实现组外顺序保持输入顺序 for i in range(len(ports) - 1, -1, -1): for j in range(i - 1, -1, -1): # 判断两个端口是否可以合并 if canUnion(ports[i], ports[j]): # 将后面的端口组并入前面的端口组这样就不会破坏组外顺序 ports[j].extend(ports[i]) ports.pop(i) return True # 继续尝试合并 return False # 合并尝试结束 # 组内相同端口仅保留一个从小到达排序 def distinctAndSort(port): tmp list(set(port)) tmp.sort() return tmp # 算法入口 def getResult(ports): while True: if not forPorts(ports): break # return list(map(distinctAndSort, ports)) # 如果输出内容不去除空格可得83.33%通过率 return re.sub(f\\s, , str(list(map(distinctAndSort, ports)))) # 输入获取 m int(input()) if m 1 or m 10: print([[]]) else: ports [list(map(int, input().split(,))) for _ in range(m)] if len(list(filter(lambda p: len(p) 1 or len(p) 100, ports))) 0: print([[]]) else: print(getResult(ports))只有形成2对端口值不同的端口对那么才可以合并Java算法源码import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int m Integer.parseInt(sc.nextLine()); // M,N不在限定范围内统一输出一组空数组[[]] if (m 10 || m 1) { System.out.println([[]]); return; } // 这里使用ArrayList接收端口组是为了后面更方便进行端口组之间的合并 ArrayListArrayListInteger ports new ArrayList(); for (int i 0; i m; i) { Integer[] tmp Arrays.stream(sc.nextLine().split(,)).map(Integer::parseInt).toArray(Integer[]::new); // M,N不在限定范围内统一输出一组空数组[[]] int n tmp.length; if (n 1 || n 100) { System.out.println([[]]); return; } ArrayListInteger tmpList new ArrayList(Arrays.asList(tmp)); ports.add(tmpList); } System.out.println(getResult(ports)); } // 算法入口 public static String getResult(ArrayListArrayListInteger ports) { outer: while (true) { // 这里倒序遍历端口组是为了实现组外顺序保持输入顺序 for (int i ports.size() - 1; i 0; i--) { for (int j i - 1; j 0; j--) { // 判断两个端口是否可以合并 if (canUnion(ports.get(i), ports.get(j))) { // 将后面的端口组并入前面的端口组这样就不会破坏组外顺序 ports.get(j).addAll(ports.get(i)); ports.remove(i); continue outer; } } } break; } StringJoiner out new StringJoiner(,, [, ]); for (ArrayListInteger port : ports) { StringJoiner in new StringJoiner(,, [, ]); for (Integer v : new TreeSetInteger(port)) { // 这里使用TreeSet是为了实现组内相同端口仅保留一个从小到达排序。 in.add(v ); } out.add(in.toString()); } return out.toString(); } // 如果端口组间存在2个及以上不同端口相同则认为这2个端口组互相关联可以合并。 // 下面方法实现中要形成两对“端口值不同的端口对”即 a [1,2,3]b[2,3,4]可以合并但是a [1,3,3]b[3,3,4]不可以合并 public static boolean canUnion(ArrayListInteger port1, ArrayListInteger port2) { HashSetInteger set1 new HashSet(port1); HashSetInteger set2 new HashSet(port2); int same 0; for (Integer v1 : set1) { if (set2.contains(v1)) { if (same 2) return true; } } return false; } }JavaScript算法源码/* JavaScript Node ACM模式 控制台输入获取 */ const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines []; let m; rl.on(line, (line) { lines.push(line); if (lines.length 1) { m lines[0] - 0; // M,N不在限定范围内统一输出一组空数组[[]] if (m 10 || m 1) { console.log([[]]); lines.length 0; return; } } if (m lines.length m 1) { lines.shift(); const ports lines.map((line) line.split(,).map(Number)); for (let port of ports) { const n port.length; // M,N不在限定范围内统一输出一组空数组[[]] if (n 1 || n 100) { console.log([[]]); lines.length 0; return; } } console.log(getResult(ports)); lines.length 0; } }); // 算法入口 function getResult(ports) { outer: while (true) { // 这里倒序遍历端口组是为了实现组外顺序保持输入顺序 for (let i ports.length - 1; i 0; i--) { for (let j i - 1; j 0; j--) { // 判断两个端口是否可以合并 if (canUnion(ports[i], ports[j])) { // 将后面的端口组并入前面的端口组这样就不会破坏组外顺序 ports[j].push(...ports[i]); ports.splice(i, 1); continue outer; } } } break; } const ans ports.map((port) [...new Set(port)].sort((a, b) a - b)); return JSON.stringify(ans); } // 如果端口组间存在2个及以上不同端口相同则认为这2个端口组互相关联可以合并。 // 下面方法实现中要形成两对“端口值不同的端口对”即 a [1,2,3]b[2,3,4]可以合并但是a [1,3,3]b[3,3,4]不可以合并 function canUnion(port1, port2) { const set1 new Set(port1); const set2 new Set(port2); let same 0; for (let v1 of set1) { if (set2.has(v1)) { if (same 2) return true; } } return false; }Python算法源码import re # 如果端口组间存在2个及以上不同端口相同则认为这2个端口组互相关联可以合并。 # 下面方法实现中要形成两对“端口值不同的端口对”即 a [1,2,3]b[2,3,4]可以合并但是a [1,3,3]b[3,3,4]不可以合并 def canUnion(port1, port2): set1 set(port1) set2 set(port2) same 0 for v in set1: if v in set2: same 1 if same 2: return True return False # 从头开始尝试合并端口组 def forPorts(ports): # 这里倒序遍历端口组是为了实现组外顺序保持输入顺序 for i in range(len(ports) - 1, -1, -1): for j in range(i - 1, -1, -1): # 判断两个端口是否可以合并 if canUnion(ports[i], ports[j]): # 将后面的端口组并入前面的端口组这样就不会破坏组外顺序 ports[j].extend(ports[i]) ports.pop(i) return True # 继续尝试合并 return False # 合并尝试结束 # 组内相同端口仅保留一个从小到达排序 def distinctAndSort(port): tmp list(set(port)) tmp.sort() return tmp # 算法入口 def getResult(ports): while True: if not forPorts(ports): break # return list(map(distinctAndSort, ports)) return re.sub(f\\s, , str(list(map(distinctAndSort, ports)))) # 输入获取 m int(input()) if m 1 or m 10: print([[]]) else: ports [list(map(int, input().split(,))) for _ in range(m)] if len(list(filter(lambda p: len(p) 1 or len(p) 100, ports))) 0: print([[]]) else: print(getResult(ports))