华为OD机试 - 小火车最多人时所在园区站点（Java 2024 E卷 100分）
华为OD机试 2024E卷题库疯狂收录中，刷题点这里
专栏导读
本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）》。
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
公园园区提供小火车单向通行，从园区站点编号最小到最大通行（如1→2→3→4→1），然后供员工在各个办公园区穿梭。通过对公司N个员工调研统计到每个员工的坐车区间，包含前后站点，请设计一个程序计算出小火车在哪个园区站点时人数最多。
二、输入描述
第1行：为调研员工人数。
第2行开始：为每个员工的上车站点和下车站点。
使用数字代表每个园区且为整数分割，如3表示从第3个园区上车，在第5个园区下车。
三、输出描述
人数最多时的园区站点编号，最多人数同时出现在的园区站点最小的园区站点。
四、测试用例
测试用例1：
1、输入
3
1 3
2 4
3 1
2、输出
3
3、说明
测试用例2：
1、输入
5
2 5
3 6
1 4
5 2
4 1
2、输出
4
3、说明
五、解题思路
我们需要找出在小火车经过的所有园区站点中，乘客数量最多的站点编号。为了高效计算每个站点的乘客数量，可以采用差分数组和前缀和的方法。
- 输入处理：首先读取员工人数N，然后读取每位员工的上车站点和下车站点。
- 确定最大站点编号：遍历所有上车和下车站点，找出最大的站点编号M，以便初始化差分数组。
- 差分数组初始化：创建一个长度为M+2的差分数组，用于记录每个站点乘客数量的变化。
- 处理每位员工的乘车区间：
- 如果上车站点 ≤ 下车站点，表示乘客在区间内直行，不涉及环形绕行。
- 在上车站点位置增加1，在下车站点的下一个位置减少1。
- 如果上车站点 > 下车站点，表示乘客需要绕行一圈。
- 在上车站点位置增加1，在最大站点的下一个位置减少1。
- 在第1站点位置增加1，在下车站点的下一个位置减少1。
- 计算前缀和：通过遍历差分数组，累加得到每个站点的实际乘客数量。
- 找出最大乘客数量的站点：遍历前缀和数组，记录乘客数量最多的站点编号，若有多个站点数量相同，则选择编号最小的站点。
六、Java算法源码
public class OdTest {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取员工人数
int N = scanner.nextInt();
// 初始化数组存储上车和下车站点
int[][] intervals = new int[N][2];
int maxStation = 0;
// 读取每位员工的上车和下车站点，并找到最大站点编号
for (int i = 0; i < N; i++) {
intervals[i][0] = scanner.nextInt(); // 上车站点
intervals[i][1] = scanner.nextInt(); // 下车站点
if (intervals[i][0] > maxStation) {
maxStation = intervals[i][0];
}
if (intervals[i][1] > maxStation) {
maxStation = intervals[i][1];
}
}
// 初始化差分数组
int[] diff = new int[maxStation + 2];
// 处理每位员工的乘车区间
for (int i = 0; i < N; i++) {
int start = intervals[i][0];
int end = intervals[i][1];
if (start <= end) {
// 区间不绕行
diff[start] += 1;
diff[end + 1] -= 1;
} else {
// 区间绕行一圈
diff[start] += 1;
diff[maxStation + 1] -= 1;
diff[1] += 1;
diff[end + 1] -= 1;
}
}
// 计算前缀和，得到每个站点的乘客数量
int maxCount = 0;
int resultStation = 1;
int current = 0;
for (int i = 1; i <= maxStation; i++) {
current += diff[i];
if (current > maxCount) {
maxCount = current;
resultStation = i;
}
}
// 输出结果
System.out.println(resultStation);
scanner.close();
}
}
七、效果展示
1、输入
4
1 2
2 3
3 4
4 1
2、输出
1
3、说明
🏆下一篇：华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 E卷 200分）
🏆本文收录于，华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
原文地址：https://blog.csdn.net/guorui_java/article/details/142714513
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！