(A卷,100分)- 端口合并（Java & JS & Python）

题目描述

有M个端口组(1<=M<=10)，
每个端口组是长度为N的整数数组(1<=N<=100)，
如果端口组间存在2个及以上不同端口相同，则认为这2个端口组互相关联，可以合并。

输入描述

第一行输入端口组个数M，再输入M行，每行逗号分割，代表端口组。

备注：端口组内数字可以重复。

输出描述

输出合并后的端口组，用二维数组表示。

• 组内相同端口仅保留一个，从小到达排序。
• 组外顺序保持输入顺序

备注：M,N不在限定范围内，统一输出一组空数组[[]]

用例

题目解析

本题有一个疑点：

如果端口组间存在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个不同端口相同呢？

这里搞不清楚，就会产生两种解题思路：

1、两个端口组，如果可以形成2对端口值相同的端口对，那么也可以合并

2、两个端口组，只有形成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))