沧州网站设计公司价格,做网站确定什么主题好,网页安全站点设置,平顶山网站建设电话华为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 (3 ≤ n ≤ 90000 且可以整除 3) 个学生排成一排学生编号分别是 1 到 nn 为 3 的整数倍数老师随机抽签决定将所有学生分成 m 个 3 人的小组n 3 * m。
为了便于同组学生交流老师决定将小组成员安排到一起也就是同组成员彼此相连同组任意两个成员之间无其它组的成员。
因此老师决定调整队伍老师每次可以调整任意一名学生到队伍的任意位置计为调整了一次请计算最少调整多少次可以达到目标。
注意对于小组之间没有顺序要求同组学生之间没有顺序要求。
二、输入描述
第一行输入初始排列顺序序列
第二行输入分组排列顺序序列
三、输出描述
输出一个整数k表示至少调整k次。
四、测试用例
测试用例1
1、输入
4 2 8 5 3 6 1 9 7 6 3 1 2 4 8 7 9 5
2、输出
1
3、说明
只有一个组例如 [4, 2, 8] 对应的组号需要调整位置使其成员在最终排列中相邻。这意味着只需要一次调整就能实现目标排列。因此输出结果为 1表示至少需要一次调整。
测试用例2
1、输入
8 9 7 5 6 3 2 1 4 7 8 9 4 2 1 3 5 6
2、输出
0
3、说明
每组3个学生的编号在初始排列和目标排列中的组号顺序已经是对应的并且组内成员在初始排列中已经彼此相邻。 通过检查可以发现每个组的成员在初始排列中已经满足相邻的条件因此不需要进行任何调整。
五、解题思路
这道题的目的是通过最少的调整次数将一组学生按照指定的目标顺序排列使得同组的学生在最终排列中彼此相连。题目的核心在于寻找一种策略能够有效地将学生移动到合适的位置同时最小化移动次数。
在计算调整次数时采用了一种贪心的策略优先处理需要最少调整的情况如两两交换从而减少整体调整次数。
1将学生编号映射为组号
我们的目标是将学生编号转化为组号。因为每个组有3个学生我们可以通过将目标排列中的每个学生编号映射到其组号即编号除以3来得到初始序列中每个学生的目标组号。
2记录组号的位置
我们需要记录每个组号在初始排列中的位置。为此我们创建一个数组列表每个列表存储对应组号在初始排列中出现的位置。
3计算最少调整次数
我们通过遍历每个组的位置列表来计算是否需要调整。如果一个组的所有成员在初始序列中已经连续排列那么不需要调整否则需要进行一次调整。
如果一个组只有一个成员则需要两次调整因为要将其与另两个成员排在一起。如果有两个成员且它们间隔较大也需要一次调整。
4计算组间交错
为了避免多余的调整计算组间的交错情况。如果一个组的成员之间有其他组的成员插入这表明需要额外的调整。通过遍历整个组号序列记录每个组号的出现次数我们可以发现是否存在组间交错并调整次数。
5输出最小调整次数
最后我们取前述计算出的两种调整方法的最小值作为最终的最小调整次数。
六、Python算法源码
# 导入必要的模块
import sysdef main():# 读取输入的初始排列顺序initial_order list(map(int, sys.stdin.readline().strip().split()))# 读取输入的目标排列顺序target_order list(map(int, sys.stdin.readline().strip().split()))student_count len(initial_order)group_count student_count // 3# 创建一个映射数组将学生编号映射到目标序列中的组号group_mapping [0] * (student_count 1)for i in range(student_count):group_mapping[target_order[i]] i // 3# 将初始顺序转换为组号数组group_order [group_mapping[student] for student in initial_order]# 创建一个列表数组用于存储每个组号在初始序列中出现的位置group_positions [[] for _ in range(group_count)]for i, group in enumerate(group_order):group_positions[group].append(i)minimum_moves 0# 遍历每个组的位置列表计算需要的最少移动次数for positions in group_positions:if len(positions) 3:# 如果一个组有3个成员检查他们是否连续if positions[1] - positions[0] 1 or positions[2] - positions[1] 1:minimum_moves 1elif len(positions) 2:# 如果一个组有2个成员检查他们是否间隔过大if positions[1] - positions[0] 2:minimum_moves 1elif len(positions) 1:# 如果一个组只有1个成员最坏情况需要两次调整minimum_moves 2# 通过计算组间的交错情况可能减少调整次数encountered_groups set()overlap_adjustments 0for group in group_order:if group not in encountered_groups:encountered_groups.add(group)else:overlap_adjustments 1# 取两种调整方法的最小值minimum_moves min(minimum_moves, overlap_adjustments)# 输出最小调整次数print(minimum_moves)# 调用主函数
if __name__ __main__:main()
七、JavaScript算法源码
// 使用Node.js的readline模块读取输入
const readline require(readline);const rl readline.createInterface({input: process.stdin,output: process.stdout
});let inputLines [];rl.on(line, (line) {inputLines.push(line.trim());if (inputLines.length 2) {rl.close();}
});rl.on(close, () {// 读取初始排列顺序const initialOrder inputLines[0].split( ).map(Number);// 读取目标排列顺序const targetOrder inputLines[1].split( ).map(Number);const studentCount initialOrder.length;const groupCount studentCount / 3;// 创建一个映射数组将学生编号映射到目标序列中的组号const groupMapping new Array(studentCount 1).fill(0);for (let i 0; i studentCount; i) {groupMapping[targetOrder[i]] Math.floor(i / 3);}// 将初始顺序转换为组号数组const groupOrder initialOrder.map(student groupMapping[student]);// 创建一个数组列表的数组用于存储每个组号在初始序列中出现的位置const groupPositions Array.from({length: groupCount}, () []);for (let i 0; i groupOrder.length; i) {groupPositions[groupOrder[i]].push(i);}let minimumMoves 0;// 遍历每个组的位置列表计算需要的最少移动次数for (const positions of groupPositions) {if (positions.length 3) {// 如果一个组有3个成员检查他们是否连续if (positions[1] - positions[0] 1 || positions[2] - positions[1] 1) {minimumMoves;}} else if (positions.length 2) {// 如果一个组有2个成员检查他们是否间隔过大if (positions[1] - positions[0] 2) {minimumMoves;}} else if (positions.length 1) {// 如果一个组只有1个成员最坏情况需要两次调整minimumMoves 2;}}// 通过计算组间的交错情况可能减少调整次数const encounteredGroups new Set();let overlapAdjustments 0;for (const group of groupOrder) {if (!encounteredGroups.has(group)) {encounteredGroups.add(group);} else {overlapAdjustments;}}// 取两种调整方法的最小值minimumMoves Math.min(minimumMoves, overlapAdjustments);// 输出最小调整次数console.log(minimumMoves);
});
八、C算法源码
#include stdio.h
#include stdlib.h// 主函数
int main() {// 定义变量int n 0;int initialOrder[90000];int targetOrder[90000];// 读取初始排列顺序while (scanf(%d, initialOrder[n]) ! EOF getchar() ! \n) {n;}// 读取目标排列顺序int m 0;while (scanf(%d, targetOrder[m]) ! EOF getchar() ! \n) {m;}// 计算组数int groupCount n / 3;// 创建组映射数组将学生编号映射到组号int *groupMapping (int *)malloc((n 1) * sizeof(int));for (int i 0; i m; i) {groupMapping[targetOrder[i]] i / 3;}// 将初始顺序转换为组号数组int groupOrder[90000];for (int i 0; i n; i) {groupOrder[i] groupMapping[initialOrder[i]];}// 创建组位置数组int **groupPositions (int **)malloc(groupCount * sizeof(int *));int *counts (int *)calloc(groupCount, sizeof(int));for (int i 0; i groupCount; i) {groupPositions[i] (int *)malloc(3 * sizeof(int));}// 记录每个组的位置for (int i 0; i n; i) {int group groupOrder[i];groupPositions[group][counts[group]] i;}int minimumMoves 0;// 遍历每个组计算调整次数for (int i 0; i groupCount; i) {if (counts[i] 3) {if (groupPositions[i][1] - groupPositions[i][0] 1 || groupPositions[i][2] - groupPositions[i][1] 1) {minimumMoves;}} else if (counts[i] 2) {if (groupPositions[i][1] - groupPositions[i][0] 2) {minimumMoves;}} else if (counts[i] 1) {minimumMoves 2;}}// 计算组间的交错情况int *encounteredGroups (int *)calloc(groupCount, sizeof(int));int overlapAdjustments 0;for (int i 0; i n; i) {int group groupOrder[i];if (!encounteredGroups[group]) {encounteredGroups[group] 1;} else {overlapAdjustments;}}// 取最小调整次数if (overlapAdjustments minimumMoves) {minimumMoves overlapAdjustments;}// 输出结果printf(%d\n, minimumMoves);// 释放内存free(groupMapping);for (int i 0; i groupCount; i) {free(groupPositions[i]);}free(groupPositions);free(counts);free(encounteredGroups);return 0;
}
九、C算法源码
#include bits/stdc.h
using namespace std;int main(){ios::sync_with_stdio(false);cin.tie(0);// 读取初始排列顺序vectorint initialOrder;string line;getline(cin, line);stringstream ss(line);int num;while(ss num){initialOrder.push_back(num);}// 读取目标排列顺序vectorint targetOrder;getline(cin, line);stringstream ss2(line);while(ss2 num){targetOrder.push_back(num);}int n initialOrder.size();int groupCount n / 3;// 创建组映射数组将学生编号映射到组号vectorint groupMapping(n1, 0);for(int i0;in;i){groupMapping[targetOrder[i]] i / 3;}// 将初始顺序转换为组号数组vectorint groupOrder(n, 0);for(int i0;in;i){groupOrder[i] groupMapping[initialOrder[i]];}// 创建组位置数组vectorvectorint groupPositions(groupCount, vectorint());for(int i0;in;i){groupPositions[groupOrder[i]].push_back(i);}int minimumMoves 0;// 遍历每个组计算调整次数for(auto positions : groupPositions){if(positions.size() 3){if(positions[1] - positions[0] 1 || positions[2] - positions[1] 1){minimumMoves;}}else if(positions.size() 2){if(positions[1] - positions[0] 2){minimumMoves;}}else if(positions.size() 1){minimumMoves 2;}}// 计算组间的交错情况unordered_setint encounteredGroups;int overlapAdjustments 0;for(auto group : groupOrder){if(encounteredGroups.find(group) encounteredGroups.end()){encounteredGroups.insert(group);}else{overlapAdjustments;}}// 取最小调整次数minimumMoves min(minimumMoves, overlapAdjustments);// 输出结果cout minimumMoves;return 0;
} 下一篇华为OD机试真题 - 简易内存池Python/JS/C/C 2024 E卷 200分
本文收录于华为OD机试真题Python/JS/C/C
刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。
