(B卷,100分)- 数组拼接（Java & JS & Python & C）

题目描述

现在有多组整数数组，需要将它们合并成一个新的数组。

合并规则，从每个数组里按顺序取出固定长度的内容合并到新的数组中，取完的内容会删除掉，如果该行不足固定长度或者已经为空，则直接取出剩余部分的内容放到新的数组中，继续下一行。

输入描述

第一行是每次读取的固定长度，0 < 长度 < 10

第二行是整数数组的数目，0 < 数目 < 1000

第3-n行是需要合并的数组，不同的数组用回车换行分隔，数组内部用逗号分隔，最大不超过100个元素。

输出描述

输出一个新的数组，用逗号分隔。

用例

题目解析

（C语言解析请直接看代码注释，以下是其他语言解析）

假设，第一行输入的固定长度是subLen。

我的解题思路如下：

首先，定义一个动态数组ans，来记录题解。

然后，将输入的3~n行对应的数组，放到一个链表中。

每次取出链表的头部，然后删除该头部数组前subLen个元素，并这subLen元素记录按顺序录入ans中：

• 如果删除后，该头部数组长度依旧大于0，则将该头部数组重新连接到链表尾部
• 如果删除后，该头部数组的长度为0，则不做操作

直到链表长度为0时，停止。

此时ans中记录的就是题解。

本题，主要难点在于，如何删除数组（或其他容器）的前subLen个元素，其实就是删除容器中某个范围的所有元素。在下面代码中，我针对不同语言，各附带了一个链接，里面有说明如何删除对应容器的某个范围的元素的策略。

2023.08.29

本题根据考友实际考试反馈，机考系统输入用例存在如下：

3
2
2,5,6,7,,,9,5,7
1,7,4,3,,4

Java算法源码

import java.util.*;
import java.util.stream.Collectors;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int subLen = Integer.parseInt(sc.nextLine());

    int n = Integer.parseInt(sc.nextLine());

    LinkedList<LinkedList<Integer>> lists = new LinkedList<>();
    for (int i = 0; i < n; i++) {
      lists.add(
          new LinkedList<>(
              Arrays.stream(sc.nextLine().split(","))
                  // 输入用例中的数组存在 4,,6 这种情况，所以这里需要过滤掉空串
                  .filter(a -> !"".equals(a))
                  .map(Integer::parseInt)
                  .collect(Collectors.toList())));
    }

    System.out.println(getResult(subLen, lists));
  }

  public static String getResult(int subLen, LinkedList<LinkedList<Integer>> lists) {
    ArrayList<Integer> ans = new ArrayList<>();

    while (lists.size() > 0) {
      LinkedList<Integer> list = lists.removeFirst();
      ans.addAll(removeRange(list, 0, subLen));
      if (list.size() > 0) lists.addLast(list);
    }

    StringJoiner sj = new StringJoiner(",");
    for (Integer an : ans) {
      sj.add(an + "");
    }
    return sj.toString();
  }

  public static List<Integer> removeRange(LinkedList<Integer> list, int start, int end) {
    if (end > list.size()) end = list.size();

    List<Integer> tmp = list.subList(start, end);

    List<Integer> ans = new ArrayList<>(tmp);
    tmp.clear();

    return ans;
  }
}

JS算法源码

Array.prototype.splice() – JavaScript | MDN (mozilla.org)

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines[1] && lines.length === 2 + parseInt(lines[1])) {
    const subLen = lines.shift() - 0;
    lines.shift();
    const lists = lines.map((line) =>
      line
        .split(",")
        // 输入用例中的数组存在 4,,6 这种情况，所以这里需要过滤掉空串
        .filter((a) => a != "")
        .map(Number)
    );

    console.log(getResult(subLen, lists));

    lines.length = 0;
  }
});

function getResult(subLen, lists) {
  const ans = [];

  while (lists.length > 0) {
    const list = lists.shift();
    ans.push(...list.splice(0, subLen));
    if (list.length > 0) lists.push(list);
  }

  return ans.join(",");
}

Python算法源码

python删除列表的指定一段区域_坑货两只的博客-CSDN博客

# 输入获取
subLen = int(input())
n = int(input())
# 输入用例中的数组存在 4,,6 这种情况，所以这里需要过滤掉空串
lists = [list(filter(lambda x: x != "", input().split(","))) for _ in range(n)]


# 算法入口
def getResult():
    ans = []

    while len(lists) > 0:
        lst = lists.pop(0)
        tmp = lst[:subLen]
        del lst[:subLen]
        ans.extend(tmp)
        if len(lst) > 0:
            lists.append(lst)

    return ",".join(ans)


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MIN(a, b) (a) < (b) ? (a) : (b)

// 链表元素类型
typedef int E;

// 链表节点类型
typedef struct ListNode {
    E ele;
    struct ListNode *next;
} Node;

// 链表结构
typedef struct List {
    Node *head;
    Node *tail;
    int size;
} LinkedList;

// 链表函数声明
LinkedList *new_LinkedList();

void addLast_LinkedList(LinkedList *link, E ele);

E removeFirst_LinkedList(LinkedList *link);

LinkedList *parseToLink(char *s, char *delimiter);

char *parseToStr(LinkedList *link, char *delimiter);

// 算法入口
char *getResult(int subLen, LinkedList **links, int links_size);


int main() {
    // 每次读取的固定长度
    int subLen;
    scanf("%d", &subLen);

    // 整数数组的数目
    int n;
    scanf("%d", &n);

    LinkedList **links = (LinkedList **) malloc(sizeof(LinkedList *) * n);
    for (int i = 0; i < n; i++) {
        // 需要合并的数组
        char line[10000];
        scanf("%s", line);
        // 将输入的每组数列按照“,”分割，存入链表中
        links[i] = parseToLink(line, ",");
    }

    printf("%s", getResult(subLen, links, n));

    return 0;
}

char *getResult(int subLen, LinkedList **links, int links_size) {
    LinkedList *ans = new_LinkedList();

    // 已空的链表个数
    int complete_count = 0;

    // 如果所有链表都空了，则结束循环
    while (complete_count != links_size) {
        for (int i = 0; i < links_size; i++) {
            LinkedList *link = links[i];

            // 如果当前链表不为空，但是本轮结束后可以空，则本轮结束后已空的链表个数+1
            if (link->size != 0 && link->size <= subLen) {
                complete_count++;
            }

            // 本轮链表需要头删的元素个数
            int size = MIN(subLen, link->size);
            for (int j = 0; j < size; j++) {
                addLast_LinkedList(ans, removeFirst_LinkedList(link));
            }
        }
    }

    return parseToStr(ans, ",");
}

// 指定分隔符的数列字符串 转为 链表
LinkedList *parseToLink(char *s, char *delimiter) {
    LinkedList *link = new_LinkedList();

    char *token = strtok(s, delimiter);
    while (token != NULL) {
        addLast_LinkedList(link, atoi(token));
        token = strtok(NULL, delimiter);
    }

    return link;
}

// 链表 转为 指定分隔符的数列字符串
char *parseToStr(LinkedList *link, char *delimiter) {
    char *res = (char *) calloc(sizeof(char), link->size * 10);

    Node *cur = link->head;
    while (cur != NULL) {
        char *tmp = (char *) calloc(sizeof(char), 10);
        sprintf(tmp, "%d", cur->ele);

        strcat(res, tmp);

        cur = cur->next;

        if (cur != NULL) {
            strcat(res, delimiter);
        }
    }

    return res;
}

// 创建和初始化链表
LinkedList *new_LinkedList() {
    LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));

    link->head = NULL;
    link->tail = NULL;
    link->size = 0;

    return link;
}

// 链表尾插
void addLast_LinkedList(LinkedList *link, E ele) {
    Node *node = (Node *) malloc(sizeof(Node));
    node->ele = ele;
    node->next = NULL;

    if (link->size == 0) {
        link->head = node;
        link->tail = node;
    } else {
        link->tail->next = node;
        link->tail = node;
    }

    link->size++;
}

// 链表头删
E removeFirst_LinkedList(LinkedList *link) {
    if (link->size > 0) {
        Node *removed = link->head;

        link->head = link->head->next;
        link->size--;

        E res = removed->ele;
        free(removed);

        return res;
    } else {
        exit(-1);
    }
}