做网站需要什么 图片视频,泉州市住房和城乡建设局,好的网站建设价格,宁波网站建设设计公司信息华为OD机试 2024E卷题库疯狂收录中#xff0c;刷题点这里 专栏导读
本专栏收录于《华为OD机试真题#xff08;Python/JS/C/C#xff09;》。
刷的越多#xff0c;抽中的概率越大#xff0c;私信哪吒#xff0c;备注华为OD#xff0c;加入华为OD刷题交流群#xff0c;… 华为OD机试 2024E卷题库疯狂收录中刷题点这里 专栏导读
本专栏收录于《华为OD机试真题Python/JS/C/C》。
刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。
一、题目描述
推荐多样性需要从多个列表中选择元素一次性要返回 N 屏数据窗口数量每屏展示 K 个元素窗口大小选择策略:
各个列表元素需要做穿插处理即先从第一个列表中为每屏选择一个元素再从第二个列表中为每屏选择一个元素依次类推。
每个列表的元素尽量均分为 N 份如果不够 N 份也要全部分配完参考样例图
(1) 从第一个列表中选择 4 条 0123分别放到 4 个窗口中
(2) 从第二个列表中选择 4 条 10111213分别放到 4 个窗口中
(3) 从第三个列表中选择 4 条 20212223分别放到 4 个窗口中
(4) 再从第一个列表中选择 4 条 4567分别放到 4 个窗口中
…
(5) 再从第一个列表中选择由于数量不足 4 条取剩下的 2 条放到窗口1 和窗口2
(6) 再从第二个列表中选择由于数量不足 4 条且总的元素数达到窗口要求取 1819 放到窗口3 和窗口4
二、输入描述
第一行输入为 N表示需要输出的窗口数量取值范围 [1, 10]
第二行输入为 K表示每个窗口需要的 元素数量取值范围 [1, 100]
之后的行数不定行数取值范围 [1, 10]表示每个列表输出的元素列表。元素之间以空格隔开已经过排序处理每个列表输出的元素数量取值范围 [1, 100]
三、输出描述
输出元素列表元素数量 窗口数量 * 窗口大小元素之间以空格分隔多个窗口合并为一个列表输出参考样例
先输出窗口1的元素列表再输出窗口2的元素列表再输出窗口3的元素列表最后输出窗口4的元素列表。
备注
每个列表会保证元素数量满足窗口要求不需要考虑元素不足情况每个列表的元素已去重不需要考虑元素重复情况每个列表的元素列表均不为空不需要考虑列表为空的情况每个列表的元素列表已经过排序处理输出结果要保证不改变同一个列表的元素顺序每个列表的元素数量可能是不同的
四、测试用例
测试用例1
1、输入
4 7 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
2、输出
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
3、说明
测试用例2
1、输入
2 3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
2、输出
0 10 20 1 11 21
3、说明
五、解题思路
1、问题分析
问题要求我们从多个排序好的列表中选择元素以 “轮询” 的方式将元素分配到多个窗口中。每个窗口的展示数量固定窗口数量也固定。主要目标是通过轮询方式选择元素确保列表中的元素尽量平均分布到各个窗口中同时保持列表中元素的顺序不变。
2、ArrayList LinkedList
使用 ArrayList 存储每个输入列表每个输入列表使用 LinkedList 来存储元素。
选择 LinkedList 的原因是它可以高效地在列表头部移除元素removeFirst 操作的时间复杂度为 O(1)这在轮询分配元素时非常重要。
3、具体步骤
读取窗口数量 N 和每个窗口需要的元素数量 K。接着读取多个列表每个列表包含已排序的整数。使用一个二维列表来存储输入的每个列表。每个列表使用 LinkedList 以便于从列表头部快速删除元素。创建一个一维数组 windows大小为 N * K用于存储所有窗口的元素。使用一个指针 idx 表示当前正在分配元素的位置以及一个指针 level 表示当前从哪个列表中取元素。使用一个循环直到所有窗口都填满 对于每一轮分配轮询当前列表将其前 N 个元素依次分配给 N 个窗口。如果当前列表的元素不够 N 个或者被取空则切换到下一个列表进行分配。 每轮次需要检查列表是否为空如果为空则移除以防止越界。按照窗口的列顺序进行输出将每个窗口的元素按列拼接成最终的结果。
主要使用了轮询遍历法。每次从当前列表中为每个窗口分配一个元素然后切换到下一个列表。这样可以确保元素被均匀分布在各个窗口中。
4、时间复杂度
总时间复杂度为 O(N * K)其中 N 是窗口数量K 是每个窗口的元素数量。主要耗时在于分配元素和输出结果的过程中。
六、Python算法源码
def main():import sysinput sys.stdin.readdata input().splitlines()# 读取窗口数量和每个窗口的元素数量n int(data[0])k int(data[1])# 读取输入的所有列表lists []for line in data[2:]:if line.strip() : # 本地测试时以空行作为输入截止条件breaknums list(map(int, line.split()))lists.append(nums)# 初始化窗口矩阵为一维数组windows [0] * (k * n)# 当前正在为窗口矩阵赋值的索引位置idx 0# 当前从第level个列表中取值level 0# 当窗口矩阵填满后结束循环while idx len(windows):# 当前轮次是否发生了借动作flag False# 从当前列表中取前 n 个元素for i in range(n):windows[idx] lists[level].pop(0)idx 1# 如果当前列表没有元素了则继续切到下一个列表中借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) # 防止越界# 构建输出result []# 遍历窗口矩阵的每一列for j in range(n): # 遍历列号for i in range(k): # 遍历行号result.append(str(windows[i * n j])) # 将每一列的元素进行拼接print( .join(result))if __name__ __main__:main()
七、JavaScript算法源码
function main() {const fs require(fs);// 读取输入const input fs.readFileSync(/dev/stdin, utf8).split(\n);// 读取窗口数量和每个窗口的元素数量const n parseInt(input[0]);const k parseInt(input[1]);// 读取输入的所有列表let lists [];for (let i 2; i input.length; i) {const line input[i].trim();if (line ) break; // 本地测试时以空行作为输入截止条件let nums line.split( ).map(Number);lists.push(nums);}// 初始化窗口矩阵为一维数组let windows new Array(k * n);// 当前正在为窗口矩阵赋值的索引位置let idx 0;// 当前从第 level 个列表中取值let level 0;// 当窗口矩阵填满后结束循环while (idx windows.length) {// 当前轮次是否发生了借动作let flag false;// 从当前列表中取前 n 个元素for (let i 0; i n; i) {windows[idx] lists[level].shift();// 如果当前列表没有元素了则继续切到下一个列表中借if (lists[level].length 0 lists.length 1) {lists.splice(level, 1); // 删除空列表level % lists.length; // 防止越界flag true; // 发生了借动作}}// 如果没有发生借动作则切换到下一个列表if (!flag) {level (level 1) % lists.length; // 防止越界}}// 构建输出let result [];// 遍历窗口矩阵的每一列for (let j 0; j n; j) { // 遍历列号for (let i 0; i k; i) { // 遍历行号result.push(windows[i * n j]); // 将每一列的元素进行拼接}}console.log(result.join( ));
}main();
八、C算法源码
#include stdio.h
#include stdlib.h// 辅助函数读取一行输入
char* read_line() {char* line NULL;size_t len 0;getline(line, len, stdin);return line;
}// 辅助函数将字符串按空格分割并转换为整数数组
int* parse_integers(char* line, int* size) {int* nums malloc(100 * sizeof(int)); // 假设每行最多有100个数字*size 0;char* token strtok(line, );while (token ! NULL) {nums[(*size)] atoi(token);token strtok(NULL, );}return nums;
}int main() {// 读取窗口数量和每个窗口的元素数量int n, k;scanf(%d, n);scanf(%d, k);getchar(); // 读取换行符// 存储所有的列表int** lists malloc(10 * sizeof(int*)); // 最多有10个列表int list_sizes[10] {0};int list_count 0;while (1) {char* line read_line();if (line[0] \n || line[0] \0) {free(line);break;}lists[list_count] parse_integers(line, list_sizes[list_count]);list_count;free(line);}// 初始化窗口矩阵为一维数组int* windows malloc(k * n * sizeof(int));int idx 0;int level 0;// 当窗口矩阵填满后结束循环while (idx k * n) {int flag 0;for (int i 0; i n; i) {windows[idx] lists[level][0];// 移除第一个元素for (int j 0; j list_sizes[level] - 1; j) {lists[level][j] lists[level][j 1];}list_sizes[level]--;// 如果当前列表没有元素了则继续切到下一个列表中借if (list_sizes[level] 0 list_count 1) {free(lists[level]); // 删除空列表for (int j level; j list_count - 1; j) {lists[j] lists[j 1];list_sizes[j] list_sizes[j 1];}list_count--;level % list_count; // 防止越界flag 1;}}// 如果没有发生借动作则切换到下一个列表if (!flag) {level (level 1) % list_count; // 防止越界}}// 构建输出for (int j 0; j n; j) {for (int i 0; i k; i) {printf(%d , windows[i * n j]);}}printf(\n);// 释放内存free(windows);for (int i 0; i list_count; i) {free(lists[i]);}free(lists);return 0;
}
九、C算法源码
#include iostream
#include vector
#include queue
#include sstream
using namespace std;int main() {int n, k;cin n k;cin.ignore(); // 读取换行符vectorqueueint lists;string line;// 读取输入的所有列表while (getline(cin, line)) {if (line.empty()) break; // 本地测试时以空行作为输入截止条件istringstream iss(line);queueint q;int num;while (iss num) {q.push(num);}lists.push_back(q);}// 初始化窗口矩阵为一维数组vectorint windows(k * n);// 当前正在为窗口矩阵赋值的索引位置int idx 0;// 当前从第 level 个列表中取值int level 0;// 当窗口矩阵填满后结束循环while (idx windows.size()) {// 当前轮次是否发生了 下一篇华为OD机试真题 - 简易内存池Python/JS/C/C 2024 E卷 200分
本文收录于华为OD机试真题Python/JS/C/C
刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。
