【2024年华为OD机试】 (A卷,100分)- 端口合并（Java JS PythonC/C++）
一、问题描述
题目描述
有 M 个端口组 (1 <= M <= 10)，
每个端口组是长度为 N 的整数数组 (1 <= N <= 100)，
如果端口组间存在 2 个及以上不同端口相同，则认为这 2 个端口组互相关联，可以合并。
输入描述
第一行输入端口组个数 M，再输入 M 行，每行逗号分割，代表端口组。
备注
- 端口组内数字可以重复。
- 如果
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,1 和 4,3,2 有 2 个及以上不同端口相同，可以合并。
用例 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,2,1 和 3,6,9,2 有 2 个及以上不同端口相同，可以合并。
用例 4
输入:
11
输出:
[[]]
说明:
M 超出范围，输出空数组。
解题思路
- 读取输入：读取端口组个数
M和每个端口组的内容。 - 检查范围：如果
M或N超出范围，直接输出[[]]。 - 处理每个端口组：将每个端口组转换为集合，去除重复元素，并排序。
- 合并端口组：使用并查集或图的连通分量算法来合并互相关联的端口组。
- 输出结果：将合并后的端口组按输入顺序输出。
题目解析
题目中的描述“如果端口组间存在2个及以上不同端口相同，则认为这2个端口组互相关联，可以合并”确实存在一定的歧义。这里的“不同端口”可以有两种理解：
-
两个端口组，如果可以形成2对端口值相同的端口对，那么也可以合并：
- 例如，端口组
a = [3, 3, 5]和b = [1, 3, 3]，虽然a[0]和b[1]相同，a[1]和b[2]相同，但这些相同的端口值都是3，因此可以认为这两个端口组可以合并。
- 例如，端口组
-
两个端口组，只有形成2对端口值不同的端口对，那么才可以合并：
- 例如，端口组
a = [3, 3, 5]和b = [1, 3, 3]，虽然a[0]和b[1]相同，a[1]和b[2]相同，但这些相同的端口值都是3，因此不能认为这两个端口组可以合并。只有当两个端口组中有两个不同的端口值相同，例如a = [3, 5]和b = [3, 5]，才可以合并。
- 例如，端口组
解题思路
为了确保代码的通用性和正确性，我们假设采用第一种理解，即两个端口组如果可以形成2对端口值相同的端口对，那么也可以合并。这种理解更符合题目的描述，也更符合实际应用中的需求。
二、JavaScript算法源码
以下是 JavaScript 代码的详细中文注释和逻辑讲解：
JavaScript 代码实现
/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
// 创建 readline 接口，用于从控制台读取输入
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
// 存储输入的行数据
const lines = [];
let m; // 端口组的数量
// 监听输入事件
rl.on("line", (line) => {
lines.push(line); // 将输入的行存入 lines 数组
// 当输入的第一行是端口组数量 m 时
if (lines.length === 1) {
m = lines[0] - 0; // 将字符串转换为数字
// 如果 m 不在限定范围内（1 <= m <= 10），输出空数组 [[]] 并重置 lines
if (m > 10 || m < 1) {
console.log("[[]]");
lines.length = 0; // 清空 lines 数组
return;
}
}
// 当输入的行数等于 m + 1 时（第一行是 m，后面是 m 个端口组）
if (m && lines.length === m + 1) {
lines.shift(); // 移除第一行（m）
const ports = lines.map((line) => line.split(",").map(Number)); // 将每行转换为数字数组
// 检查每个端口组的长度是否在限定范围内（1 <= n <= 100）
for (let port of ports) {
const n = port.length;
if (n < 1 || n > 100) {
console.log("[[]]"); // 如果不在范围内，输出空数组 [[]]
lines.length = 0; // 清空 lines 数组
return;
}
}
// 调用算法入口函数，输出结果
console.log(getResult(ports));
lines.length = 0; // 清空 lines 数组
}
});
// 算法入口函数
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[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); // 将结果转换为 JSON 字符串
}
// 判断两个端口组是否可以合并
function canUnion(port1, port2) {
// 对两个端口组进行升序排序
port1.sort((a, b) => a - b);
port2.sort((a, b) => a - b);
let same = 0; // 记录相同端口的数量
let i = 0; // port1 的指针
let j = 0; // port2 的指针
// 双指针遍历两个端口组
while (i < port1.length && j < port2.length) {
if (port1[i] == port2[j]) {
i++;
j++;
if (++same >= 2) return true; // 如果有 2 个及以上相同端口，返回 true
} else if (port1[i] > port2[j]) {
j++; // port2 的当前值较小，移动 port2 的指针
} else {
i++; // port1 的当前值较小，移动 port1 的指针
}
}
return false; // 如果没有 2 个及以上相同端口，返回 false
}
代码讲解
1. 输入处理
- 使用
readline模块从控制台读取输入。 - 第一行是端口组的数量
m，后续每行是一个端口组，用逗号分隔。 - 检查
m和每个端口组的长度是否在限定范围内（1 <= m <= 10，1 <= n <= 100），如果不在范围内，输出空数组[[]]。
2. 主逻辑：getResult 函数
- 倒序遍历端口组，确保组外顺序保持输入顺序。
- 对于每一对端口组，调用
canUnion函数判断是否可以合并。 - 如果可以合并，将后面的端口组并入前面的端口组，并移除被合并的端口组。
- 最终对每个端口组去重并排序，返回结果。
3. 判断是否可以合并：canUnion 函数
- 对两个端口组进行升序排序。
- 使用双指针遍历两个端口组，统计相同端口的数量。
- 如果有 2 个及以上相同端口，返回
true，表示可以合并；否则返回false。
示例解析
输入
3
1,2,3
2,3,4
5,6,7
运行结果
[[1,2,3,4],[5,6,7]]
- 解析：
- 端口组
[1,2,3]和[2,3,4]有 2 个相同端口（2和3），可以合并为[1,2,3,4]。 - 端口组
[5,6,7]没有与其他端口组相同的端口，保持不变。 - 最终结果为
[[1,2,3,4],[5,6,7]]。
- 端口组
总结
- 该代码通过双指针和排序的方式，判断端口组是否可以合并。
- 使用倒序遍历确保组外顺序保持输入顺序。
- 代码逻辑清晰，适用于解决类似合并问题的场景。
如果有其他问题，欢迎随时提问！
三、Java算法源码
以下是 Java 代码的详细中文注释和逻辑讲解：
Java 代码实现
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取端口组的数量 m
int m = Integer.parseInt(sc.nextLine());
// 如果 m 不在限定范围内（1 <= m <= 10），输出空数组 [[]] 并结束程序
if (m > 10 || m < 1) {
System.out.println("[[]]");
return;
}
// 使用 ArrayList 存储端口组，方便后续合并操作
ArrayList<ArrayList<Integer>> ports = new ArrayList<>();
// 读取每个端口组
for (int i = 0; i < m; i++) {
// 将输入的端口组按逗号分隔，并转换为 Integer 数组
Integer[] tmp =
Arrays.stream(sc.nextLine().split(","))
.map(Integer::parseInt)
.toArray(Integer[]::new);
// 检查端口组的长度是否在限定范围内（1 <= n <= 100）
int n = tmp.length;
if (n < 1 || n > 100) {
System.out.println("[[]]"); // 如果不在范围内，输出空数组 [[]]
return;
}
// 将 Integer 数组转换为 ArrayList 并存入 ports
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(i)）并入前面的端口组（ports.get(j)）
ports.get(j).addAll(ports.get(i));
ports.remove(i); // 移除被合并的端口组
continue outer; // 继续外层循环
}
}
}
break; // 如果没有可以合并的端口组，退出循环
}
// 使用 StringJoiner 构建输出结果
StringJoiner out = new StringJoiner(",", "[", "]");
for (ArrayList<Integer> port : ports) {
// 对每个端口组去重并排序
StringJoiner in = new StringJoiner(",", "[", "]");
for (Integer v : new TreeSet<Integer>(port)) { // 使用 TreeSet 去重并排序
in.add(v + ""); // 将端口值转换为字符串并加入 in
}
out.add(in.toString()); // 将处理后的端口组加入 out
}
return out.toString(); // 返回最终的 JSON 字符串
}
// 判断两个端口组是否可以合并
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; // port1 的指针
int j = 0; // port2 的指针
// 双指针遍历两个端口组
while (i < port1.size() && j < port2.size()) {
if (port1.get(i) - port2.get(j) == 0) { // 如果当前端口值相同
i++;
j++;
if (++same >= 2) return true; // 如果有 2 个及以上相同端口，返回 true
} else if (port1.get(i) > port2.get(j)) {
j++; // port2 的当前值较小，移动 port2 的指针
} else {
i++; // port1 的当前值较小，移动 port1 的指针
}
}
return false; // 如果没有 2 个及以上相同端口，返回 false
}
}
代码讲解
1. 输入处理
- 使用
Scanner从控制台读取输入。 - 第一行是端口组的数量
m，后续每行是一个端口组，用逗号分隔。 - 检查
m和每个端口组的长度是否在限定范围内（1 <= m <= 10，1 <= n <= 100），如果不在范围内，输出空数组[[]]。
2. 主逻辑：getResult 函数
- 倒序遍历端口组，确保组外顺序保持输入顺序。
- 对于每一对端口组，调用
canUnion函数判断是否可以合并。 - 如果可以合并，将后面的端口组并入前面的端口组，并移除被合并的端口组。
- 最终对每个端口组去重并排序，返回结果。
3. 判断是否可以合并：canUnion 函数
- 对两个端口组进行升序排序。
- 使用双指针遍历两个端口组，统计相同端口的数量。
- 如果有 2 个及以上相同端口，返回
true，表示可以合并；否则返回false。
4. 结果格式化
- 使用
StringJoiner构建输出结果。 - 对每个端口组去重并排序，使用
TreeSet实现。
示例解析
输入
3
1,2,3
2,3,4
5,6,7
运行结果
[[1,2,3,4],[5,6,7]]
- 解析：
- 端口组
[1,2,3]和[2,3,4]有 2 个相同端口（2和3），可以合并为[1,2,3,4]。 - 端口组
[5,6,7]没有与其他端口组相同的端口，保持不变。 - 最终结果为
[[1,2,3,4],[5,6,7]]。
- 端口组
总结
- 该代码通过双指针和排序的方式，判断端口组是否可以合并。
- 使用倒序遍历确保组外顺序保持输入顺序。
- 代码逻辑清晰，适用于解决类似合并问题的场景。
如果有其他问题，欢迎随时提问！
四、Python算法源码
以下是 Python 代码的详细中文注释和逻辑讲解：
Python 代码实现
import re
# 判断两个端口组是否可以合并
def canUnion(port1, port2):
# 对两个端口组进行升序排序
port1.sort()
port2.sort()
same = 0 # 记录相同端口的数量
i = 0 # port1 的指针
j = 0 # port2 的指针
# 双指针遍历两个端口组
while i < len(port1) and j < len(port2):
if port1[i] == port2[j]: # 如果当前端口值相同
i += 1
j += 1
same += 1
if same >= 2: # 如果有 2 个及以上相同端口，返回 True
return True
elif port1[i] > port2[j]: # port2 的当前值较小，移动 port2 的指针
j += 1
else: # port1 的当前值较小，移动 port1 的指针
i += 1
return False # 如果没有 2 个及以上相同端口，返回 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[i]）并入前面的端口组（ports[j]）
ports[j].extend(ports[i])
ports.pop(i) # 移除被合并的端口组
return True # 继续尝试合并
return False # 合并尝试结束
# 对端口组去重并排序
def distinctAndSort(port):
tmp = list(set(port)) # 使用 set 去重
tmp.sort() # 对端口组进行升序排序
return tmp
# 算法入口函数
def getResult(ports):
while True:
if not forPorts(ports): # 尝试合并端口组，直到无法合并为止
break
# 返回处理后的端口组，去除空格
return re.sub(r"\s", "", str(list(map(distinctAndSort, ports))))
# 输入获取
m = int(input()) # 读取端口组的数量 m
# 如果 m 不在限定范围内（1 <= m <= 10），输出空数组 [[]]
if m < 1 or m > 10:
print("[[]]")
else:
# 读取每个端口组，并将其转换为整数列表
ports = [list(map(int, input().split(","))) for _ in range(m)]
# 检查每个端口组的长度是否在限定范围内（1 <= n <= 100）
if len(list(filter(lambda p: len(p) < 1 or len(p) > 100, ports))) > 0:
print("[[]]") # 如果不在范围内，输出空数组 [[]]
else:
# 调用算法入口函数，输出结果
print(getResult(ports))
代码讲解
1. 输入处理
- 使用
input()函数从控制台读取输入。 - 第一行是端口组的数量
m，后续每行是一个端口组，用逗号分隔。 - 检查
m和每个端口组的长度是否在限定范围内（1 <= m <= 10，1 <= n <= 100），如果不在范围内，输出空数组[[]]。
2. 主逻辑：getResult 函数
- 调用
forPorts函数尝试合并端口组，直到无法合并为止。 - 对每个端口组去重并排序，使用
distinctAndSort函数实现。 - 使用
re.sub去除结果中的空格，返回最终的 JSON 字符串。
3. 合并端口组：forPorts 函数
- 倒序遍历端口组，确保组外顺序保持输入顺序。
- 对于每一对端口组，调用
canUnion函数判断是否可以合并。 - 如果可以合并，将后面的端口组并入前面的端口组，并移除被合并的端口组。
4. 判断是否可以合并：canUnion 函数
- 对两个端口组进行升序排序。
- 使用双指针遍历两个端口组，统计相同端口的数量。
- 如果有 2 个及以上相同端口，返回
True，表示可以合并；否则返回False。
5. 去重并排序：distinctAndSort 函数
- 使用
set对端口组去重。 - 对去重后的端口组进行升序排序。
示例解析
输入
3
1,2,3
2,3,4
5,6,7
运行结果
[[1,2,3,4],[5,6,7]]
- 解析：
- 端口组
[1,2,3]和[2,3,4]有 2 个相同端口（2和3），可以合并为[1,2,3,4]。 - 端口组
[5,6,7]没有与其他端口组相同的端口，保持不变。 - 最终结果为
[[1,2,3,4],[5,6,7]]。
- 端口组
总结
- 该代码通过双指针和排序的方式，判断端口组是否可以合并。
- 使用倒序遍历确保组外顺序保持输入顺序。
- 代码逻辑清晰，适用于解决类似合并问题的场景。
如果有其他问题，欢迎随时提问！
五、C/C++算法源码：
以下为 C++ 代码的实现，并附上详细的中文注释和逻辑讲解：
C++ 代码实现
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <sstream>
#include <regex>
using namespace std;
// 判断两个端口组是否可以合并
bool canUnion(vector<int>& port1, vector<int>& port2) {
// 对两个端口组进行升序排序
sort(port1.begin(), port1.end());
sort(port2.begin(), port2.end());
int same = 0; // 记录相同端口的数量
int i = 0; // port1 的指针
int j = 0; // port2 的指针
// 双指针遍历两个端口组
while (i < port1.size() && j < port2.size()) {
if (port1[i] == port2[j]) { // 如果当前端口值相同
i++;
j++;
same++;
if (same >= 2) return true; // 如果有 2 个及以上相同端口，返回 true
} else if (port1[i] > port2[j]) { // port2 的当前值较小，移动 port2 的指针
j++;
} else { // port1 的当前值较小，移动 port1 的指针
i++;
}
}
return false; // 如果没有 2 个及以上相同端口，返回 false
}
// 从头开始尝试合并端口组
bool forPorts(vector<vector<int>>& ports) {
// 倒序遍历端口组，确保组外顺序保持输入顺序
for (int i = ports.size() - 1; i >= 0; i--) {
for (int j = i - 1; j >= 0; j--) {
// 判断两个端口组是否可以合并
if (canUnion(ports[i], ports[j])) {
// 将后面的端口组（ports[i]）并入前面的端口组（ports[j]）
ports[j].insert(ports[j].end(), ports[i].begin(), ports[i].end());
ports.erase(ports.begin() + i); // 移除被合并的端口组
return true; // 继续尝试合并
}
}
}
return false; // 合并尝试结束
}
// 对端口组去重并排序
vector<int> distinctAndSort(vector<int>& port) {
set<int> tmp(port.begin(), port.end()); // 使用 set 去重
vector<int> result(tmp.begin(), tmp.end()); // 转换为 vector
sort(result.begin(), result.end()); // 对端口组进行升序排序
return result;
}
// 算法入口函数
string getResult(vector<vector<int>>& ports) {
while (true) {
if (!forPorts(ports)) { // 尝试合并端口组，直到无法合并为止
break;
}
}
// 构建输出结果
stringstream ss;
ss << "[";
for (size_t i = 0; i < ports.size(); i++) {
vector<int> tmp = distinctAndSort(ports[i]); // 去重并排序
ss << "[";
for (size_t j = 0; j < tmp.size(); j++) {
ss << tmp[j];
if (j < tmp.size() - 1) ss << ",";
}
ss << "]";
if (i < ports.size() - 1) ss << ",";
}
ss << "]";
// 去除空格
string result = ss.str();
result.erase(remove(result.begin(), result.end(), ' '), result.end());
return result;
}
// 输入获取
int main() {
int m;
cin >> m; // 读取端口组的数量 m
// 如果 m 不在限定范围内（1 <= m <= 10），输出空数组 [[]]
if (m < 1 || m > 10) {
cout << "[[]]" << endl;
return 0;
}
vector<vector<int>> ports(m);
for (int i = 0; i < m; i++) {
string line;
cin >> line; // 读取一行输入
stringstream ss(line);
string token;
while (getline(ss, token, ',')) { // 按逗号分隔
ports[i].push_back(stoi(token)); // 将字符串转换为整数并存入 ports
}
}
// 检查每个端口组的长度是否在限定范围内（1 <= n <= 100）
for (const auto& port : ports) {
if (port.size() < 1 || port.size() > 100) {
cout << "[[]]" << endl; // 如果不在范围内，输出空数组 [[]]
return 0;
}
}
// 调用算法入口函数，输出结果
cout << getResult(ports) << endl;
return 0;
}
代码讲解
1. 输入处理
- 使用
cin从控制台读取输入。 - 第一行是端口组的数量
m，后续每行是一个端口组，用逗号分隔。 - 检查
m和每个端口组的长度是否在限定范围内（1 <= m <= 10，1 <= n <= 100），如果不在范围内，输出空数组[[]]。
2. 主逻辑：getResult 函数
- 调用
forPorts函数尝试合并端口组，直到无法合并为止。 - 对每个端口组去重并排序，使用
distinctAndSort函数实现。 - 使用
stringstream构建输出结果，并去除空格。
3. 合并端口组：forPorts 函数
- 倒序遍历端口组，确保组外顺序保持输入顺序。
- 对于每一对端口组，调用
canUnion函数判断是否可以合并。 - 如果可以合并，将后面的端口组并入前面的端口组，并移除被合并的端口组。
4. 判断是否可以合并：canUnion 函数
- 对两个端口组进行升序排序。
- 使用双指针遍历两个端口组，统计相同端口的数量。
- 如果有 2 个及以上相同端口，返回
true，表示可以合并；否则返回false。
5. 去重并排序：distinctAndSort 函数
- 使用
set对端口组去重。 - 对去重后的端口组进行升序排序。
示例解析
输入
3
1,2,3
2,3,4
5,6,7
运行结果
[[1,2,3,4],[5,6,7]]
- 解析：
- 端口组
[1,2,3]和[2,3,4]有 2 个相同端口（2和3），可以合并为[1,2,3,4]。 - 端口组
[5,6,7]没有与其他端口组相同的端口，保持不变。 - 最终结果为
[[1,2,3,4],[5,6,7]]。
- 端口组
总结
- 该代码通过双指针和排序的方式，判断端口组是否可以合并。
- 使用倒序遍历确保组外顺序保持输入顺序。
- 代码逻辑清晰，适用于解决类似合并问题的场景。
如果有其他问题，欢迎随时提问！