(200分)- 推荐多样性Java JS Python C题目描述推荐多样性需要从多个列表中选择元素一次性要返回 N 屏数据窗口数量每屏展示 K 个元素窗口大小选择策略各个列表元素需要做穿插处理即先从第一个列表中为每屏选择一个元素再从第二个列表中为每屏选择一个元素依次类推每个列表的元素尽量均分为 N 份如果不够 N 个也要全部分配完参考样例图1从第一个列表中选择 4 条 0 1 2 3分别放到 4 个窗口中2从第二个列表中选择 4 条 10 11 12 13分别放到 4 个窗口中3从第三个列表中选择 4 条 20 21 22 23分别放到 4 个窗口中4再从第一个列表中选择 4 条 4 5 6 7分别放到 4 个窗口中...5再从第一个列表中选择由于数量不足 4 条取剩下的 2 条放到 窗口1 和 窗口26再从第二个列表中选择由于数量不足 4 条并且总的元素数达到窗口要求取 18 19 放到 窗口3 和 窗口4输入描述第一行输入为 N表示需要输出的窗口数量取值范围 [1, 10]第二行输入为 K表示每个窗口需要的元素数量取值范围 [1, 100]之后的行数不定行数取值范围 [1, 10]表示每个列表输出的元素列表。元素之间以空格隔开已经过排序处理每个列表输出的元素数量取值范围 [1, 100]输出描述输出元素列表元素数量 窗口数量 * 窗口大小元素之间以空格分隔多个窗口合并为一个列表输出参考样例先输出窗口1的元素列表再输出窗口2的元素列表再输出窗口3的元素列表最后输出窗口4的元素列表备注每个列表会保证元素数量满足窗口要求不需要考虑元素不足情况每个列表的元素已去重不需要考虑元素重复情况每个列表的元素列表均不为空不需要考虑列表为空的情况每个列表的元素列表已经过排序处理输出结果要保证不改变同一个列表的元素顺序每个列表的元素数量可能是不同的用例输入470 1 2 3 4 5 6 7 8 910 11 12 13 14 15 16 17 18 1920 21 22 23 24 25 26 27 28 29输出0 10 20 4 14 24 8 1 11 21 5 15 25 9 2 12 22 6 16 26 18 3 13 23 7 17 27 19说明无题目解析我们可以将最终的窗口集当成一个矩阵windows该矩阵有 k 行 n 列矩阵的每一列对应一个窗口。最终按列打印该矩阵即为题解。之后就是根据题目给定规则往这个windos矩阵中填值即可。由于填值过程遵循从左到右、从上到下的顺序我们可以将windows矩阵转化为一维数组其长度为k*n。这样只需维护一个索引指针idx就能准确指示当前填值位置。列表集的读取规则如下从第一个列表开始每次读取n个值填入windows若当前列表剩余元素≥n读取n个值后该列表仍有剩余无需向后借元素若当前列表剩余元素n读取完该列表后需向后借元素需注意借元素的情况例如540 1 2 3 45 6 7 89 10 11 12 13 1415 16 17 18 19在填充 Windows 矩阵的第二行时由于第二个列表元素不足系统自动从第三个列表借用元素。那么在填充 Windows 矩阵的第三行时应该从列表集的第三个列表开始读取。最终生成的 Windows 矩阵如下所示在代码实现时需注意以下处理逻辑定义level指针指向当前读取轮次的列表序号无借操作时当前列表读取完成后执行level有借操作时因当前列表元素不足需在读取过程中执行level切换到下一列表借元素完成元素填充后无需再次level此时已处于下一轮要读取的列表位置优化后的表达修复了一个边界问题当执行借操作时若当前层级列表元素已耗尽需要向下一层级借用时必须确保存在下一层级列表否则将无法完成借用操作。相关代码位置如下JS第40行 Java第41行 Python第33行 C第111行JS算法源码const rl require(readline).createInterface({ input: process.stdin }); var iter rl[Symbol.asyncIterator](); const readline async () (await iter.next()).value; void (async function () { const n parseInt(await readline()); const k parseInt(await readline()); const lists []; while (true) { try { const s await readline(); if (s.length 0) break; lists.push(s.split( ).map(Number)); } catch (e) { break; } } // 窗口矩阵k行n列每一列对应一个窗口这里将二维矩阵一维化方便后面赋值 const windows new Array(k * n); // 窗口矩阵中正在赋值的索引位置 let idx 0; // 正在从第level个列表中取值 let level 0; // 当窗口矩阵填满后结束循环 while (idx windows.length) { // 当前轮次是否发生了借动作 let flag false; // 从第level个列表中取前n个元素 for (let i 0; i n; i) { windows[idx] lists[level].shift(); // 如果第level个列表没有元素了则继续切到下一个列表中借 if (lists[level].length 0 lists.length 1) { lists.splice(level, 1); // 删除空列表 level % lists.length; // 防止越界 flag true; // 发生了借动作 } } // 如果没有发生借动作则需要切到下一行 if (!flag) { level (level 1) % lists.length; // 防止越界 } } const ans []; // 遍历列号 for (let j 0; j n; j) { // 遍历行号 for (let i 0; i k; i) { // 按列收集元素 ans.push(windows[i * n j]); } } console.log(ans.join( )); })();Java算法源码import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n Integer.parseInt(sc.nextLine()); int k Integer.parseInt(sc.nextLine()); ArrayListLinkedListInteger lists new ArrayList(); while (sc.hasNextLine()) { String line sc.nextLine(); // 本地测试以空行作为输入截止条件 if (line.length() 0) break; Integer[] nums Arrays.stream(line.split( )).map(Integer::parseInt).toArray(Integer[]::new); lists.add(new LinkedList(Arrays.asList(nums))); } // 窗口矩阵k行n列每一列对应一个窗口这里将二维矩阵一维化方便后面赋值 int[] windows new int[k * n]; // 窗口矩阵中正在赋值的索引位置 int idx 0; // 正在从第level个列表中取值 int level 0; // 当窗口矩阵填满后结束循环 while (idx windows.length) { // 当前轮次是否发生了借动作 boolean flag false; // 从第level个列表中取前n个元素 for (int i 0; i n; i) { windows[idx] lists.get(level).removeFirst(); // 如果第level个列表没有元素了则继续切到下一个列表中借 if (lists.get(level).size() 0 lists.size() 1) { lists.remove(level); // 删除空列表 level % lists.size(); // 防止越界 flag true; // 发生了借动作 } } // 如果没有发生借动作则需要切到下一行 if (!flag) { level (level 1) % lists.size(); // 防止越界 } } StringJoiner sj new StringJoiner( ); // 遍历窗口矩阵的每一列 for (int j 0; j n; j) { // 遍历列号 for (int i 0; i k; i) { // 遍历行号 sj.add(windows[i * n j] ); // 将每一列的元素进行拼接 } } System.out.println(sj); } }Python算法源码# 输入获取 n int(input()) k int(input()) lists [] while True: try: lists.append(list(map(int, input().split()))) except: break # 算法入口 def getResult(): # 窗口矩阵k行n列每一列对应一个窗口这里将二维矩阵一维化方便后面赋值 windows [0] * (k * n) # 窗口矩阵中正在赋值的索引位置 idx 0 # 正在从第level个列表中取值 level 0 # 当窗口矩阵填满后结束循环 while idx len(windows): # 当前轮次是否发生了借动作 flag False # 从第level个列表中取前n个元素 for _ in range(n): windows[idx] lists[level].pop(0) idx 1 # 如果第level个列表没有元素了则继续切到下一个列表中借 if len(lists[level]) 0 and len(lists) 1: lists.pop(level) # 删除空列表 level % len(lists) # 防止越界 flag True # 发生了借动作 # 如果没有发生借动作则需要切到下一行 if not flag: level (level 1) % len(lists) # 防止越界 ans [] # 遍历列号 for j in range(n): # 遍历行号 for i in range(k): # 按列收集元素 ans.append(windows[i * n j]) return .join(map(str, ans)) # 算法调用 print(getResult())C算法源码#include stdio.h #include string.h #include stdlib.h #define MAX_ROWS 100 #define MAX_ROW_LEN 10000 /* 链表节点 */ typedef struct Node { int val; struct Node *next; } Node; /* 链表 */ typedef struct Link { int size; Node *head; Node *tail; } Link; // 创建链表 Link *new_Link() { Link *link (Link *) malloc(sizeof(Link)); link-size 0; link-head NULL; link-tail NULL; return link; } // 尾插 void addLast_Link(Link *link, int val) { Node *node (Node *) malloc(sizeof(Node)); node-val val; node-next NULL; if (link-size 0) { link-head node; link-tail node; } else { link-tail-next node; link-tail node; } link-size; } // 头删 int removeFirst_Link(Link *link) { if (link-size 0) exit(-1); Node *removed link-head; if (link-size 1) { link-head NULL; link-tail NULL; } else { link-head link-head-next; } link-size--; int val removed-val; free(removed); return val; } int main() { int n, k; scanf(%d %d, n, k); getchar(); Link *lists[MAX_ROWS]; int lists_size 0; char s[MAX_ROW_LEN]; while (gets(s)) { // 本地测试以空行作为输入截止条件 if (strlen(s) 0) break; Link *link new_Link(); char *token strtok(s, ); while (token ! NULL) { addLast_Link(link, atoi(token)); token strtok(NULL, ); } lists[lists_size] link; } // 窗口矩阵k行n列每一列对应一个窗口这里将二维矩阵一维化方便后面赋值 int windows[k * n]; // 窗口矩阵中正在赋值的索引位置 int idx 0; // 正在从第level个列表中取值 int level 0; // 当窗口矩阵填满后结束循环 while (idx k * n) { // 当前轮次是否发生了借动作 int flag 0; // 从第level个列表中取前n个元素 for (int i 0; i n; i) { windows[idx] removeFirst_Link(lists[level]); // 如果第level个列表没有元素了则继续切到下一个列表中借 if (lists[level]-size 0 lists_size 1) { // 删除第level个空列表 for (int j level 1; j lists_size; j) { lists[j - 1] lists[j]; } lists_size--; level % lists_size; // 防止越界 flag 1; // 发生了借动作 } } // 如果没有发生借动作则需要切到下一行 if (!flag) { level (level 1) % lists_size; // 防止越界 } } // 遍历列号 for (int j 0; j n; j) { // 遍历行号 for (int i 0; i k; i) { // 按列打印 printf(%d, windows[i * n j]); if (j ! n - 1 || i ! k - 1) { printf( ); } } } return 0; }