- 端口合并（Java JS Python）)
(100分)- 端口合并（Java & JS & Python）
题目描述
有M个端口组(1<=M<=10)，
每个端口组是长度为N的整数数组(1<=N<=100)，
如果端口组间存在2个及以上不同端口相同，则认为这2个端口组互相关联，可以合并。
输入描述
第一行输入端口组个数M，再输入M行，每行逗号分割，代表端口组。
备注：端口组内数字可以重复。
输出描述
输出合并后的端口组，用二维数组表示。
- 组内相同端口仅保留一个，从小到达排序。
- 组外顺序保持输入顺序
备注：M,N不在限定范围内，统一输出一组空数组[[]]
用例
| 输入 | 4 4 2,3,2 1,2 5 |
| 输出 | [[4],[2,3],[1,2],[5]] |
| 说明 | 仅有一个端口2相同，不可以合并。 |
| 输入 | 3 2,3,1 4,3,2 5 |
| 输出 | [[1,2,3,4],[5]] |
| 说明 | 无 |
| 输入 | 6 10 4,2,1 9 3,6,9,2 6,3,4 8 |
| 输出 | [[10],[1,2,3,4,6,9],[9],[8]] |
| 说明 | 无 |
| 输入 | 11 |
| 输出 | [[]] |
| 说明 | 无 |
题目解析
本题有一个疑点：
如果端口组间存在2个及以上不同端口相同，则认为这2个端口组互相关联，可以合并。
关于"不同端口"的具体含义：
以您提供的用例为例，两个端口组都包含端口3和3，这种情况是否可以合并呢？
2
3 3 5
1 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接收端口组，是为了后面更方便进行端口组之间的合并 ArrayList<ArrayList<Integer>> 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; } ArrayList<Integer> tmpList = new ArrayList<>(Arrays.asList(tmp)); ports.add(tmpList); } System.out.println(getResult(ports)); } // 算法入口 public static String getResult(ArrayList<ArrayList<Integer>> 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 (ArrayList<Integer> port : ports) { StringJoiner in = new StringJoiner(",", "[", "]"); for (Integer v : new TreeSet<Integer>(port)) { // 这里使用TreeSet是为了实现：组内相同端口仅保留一个，从小到达排序。 in.add(v + ""); } out.add(in.toString()); } return out.toString(); } // 如果端口组间存在2个及以上不同端口相同，则认为这2个端口组互相关联，可以合并。 // 下面方法实现中：对于“不同端口”的理解是：端口位置不同，端口值可以相同，即以不同位置的端口视为不同端口 public static boolean canUnion(ArrayList<Integer> port1, ArrayList<Integer> 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接收端口组，是为了后面更方便进行端口组之间的合并 ArrayList<ArrayList<Integer>> 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; } ArrayList<Integer> tmpList = new ArrayList<>(Arrays.asList(tmp)); ports.add(tmpList); } System.out.println(getResult(ports)); } // 算法入口 public static String getResult(ArrayList<ArrayList<Integer>> 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 (ArrayList<Integer> port : ports) { StringJoiner in = new StringJoiner(",", "[", "]"); for (Integer v : new TreeSet<Integer>(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(ArrayList<Integer> port1, ArrayList<Integer> port2) { HashSet<Integer> set1 = new HashSet<>(port1); HashSet<Integer> 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))
