维护网站,网络运营商在哪里找,内网网站建设方案,海南四定网站开发目录 专栏导读一、题目描述二、输入描述三、输出描述四、二分查找五、解题思路六、Java算法源码七、效果展示1、输入2、输出3、说明 华为OD机试 2023B卷题库疯狂收录中#xff0c;刷题点这里 专栏导读
本专栏收录于《华为OD机试#xff08;JAVA#xff09;真题#xff08;… 目录 专栏导读一、题目描述二、输入描述三、输出描述四、二分查找五、解题思路六、Java算法源码七、效果展示1、输入2、输出3、说明 华为OD机试 2023B卷题库疯狂收录中刷题点这里 专栏导读
本专栏收录于《华为OD机试JAVA真题A卷B卷》。
刷的越多抽中的概率越大每一题都有详细的答题思路、详细的代码注释、样例测试发现新题目随时更新全天CSDN在线答疑。
一、题目描述
某实验室计算机待处理任务以 [start,end,period] 格式记于二维数组 tasks表示完成该任务的时间范围为起始时间 start 至结束时间 end 之间需要计算机投入 period 的时长注意
period 可为不连续时间首尾时间均包含在内
处于开机状态的计算机可同时处理任意多个任务请返回电脑最少开机多久可处理完所有任务。
二、输入描述
[[1,3,2],[2,5,3],[5,6,2]]
三、输出描述
4
tasks[0] 选择时间点 2、3tasks[1] 选择时间点 2、3、5tasks[2] 选择时间点 5、6因此计算机仅需在时间点 2、3、5、6 四个时刻保持开机即可完成任务。
四、二分查找
二分查找Binary Search也称为折半查找是一种在有序数组中查找特定元素的搜索算法。
二分查找的基本思想是将数组分成两部分确定待查找元素可能存在的那一部分然后继续对该部分进行二分直到找到目标元素或者确定该元素不存在于数组中。
比如下面这段Java代码
public class BinarySearch { public static int binarySearch(int[] array, int target) { int left 0; int right array.length - 1; while (left right) { int mid (left right) / 2; if (array[mid] target) { return mid; } else if (array[mid] target) { left mid 1; } else { right mid - 1; } } return -1; } public static void main(String[] args) { int[] array {1, 3, 5, 7, 9}; int target 5; int result binarySearch(array, target); if (result -1) { System.out.println(Element not found); } else { System.out.println(Element found at index result); } }
}在这个示例中binarySearch方法接收一个有序数组array和要查找的目标元素target。然后使用循环进行二分查找将搜索范围不断缩小直到找到目标元素或确定该元素不存在于数组中。如果找到目标元素返回其索引否则返回-1。
在main方法中我们定义一个数组和一个目标元素然后调用binarySearch方法并打印结果。
五、解题思路
由于每次都是从右到左新增时间点相当于把若干右侧的区间合并成一个大区间因此可以用栈来优化。
栈中保存闭区间的左右端点以及从栈底到栈顶的区间长度之和类似前缀和。
合并前先在栈中二分查找左端点所在区间由于我们保存了长度之和所以可以算出 [start,end]范围内的运行中的时间点。
如果还需要新增时间点那么就从右到左合并。
六、Java算法源码
package com.guor.od;import com.alibaba.fastjson.JSON;import java.util.*;
import java.util.function.Predicate;/*** 批量处理任务*/
public class OdTest {public static void main(String[] args) {Scanner sc new Scanner(System.in);/*** demo[[2,3,1],[5,5,1],[5,6,2]]* 起始时间结束时间需要计算机投入 period 的时长*/int[][] tasks JSON.parseObject(sc.nextLine(), int[][].class);System.out.println(getPeriod(tasks));}public static int getPeriod(int[][] tasks) {Arrays.sort(tasks, (a, b) - a[1] - b[1]);// 集合中保存闭区间的左右端点以及从栈底到栈顶的区间长度之和Listint[] list new ArrayList();for (int[] task : tasks) {// 起始时间int start task[0];// 结束时间int end task[1] 1;// 需要计算机投入 period 的时长int period task[2];// 在集合中二分查找左端点所在区间// [[2,3,1],[5,5,1],[5,6,2]]int i binarySearch(list, (x - x[1] start));int max 0;if (i ! list.size()) {int[] arr list.get(list.size() - 1);max Math.max(0, arr[2] - list.get(i)[2] list.get(i)[1] - Math.max(start, list.get(i)[0]));}int temp Math.max(0, period - max);int cur end;while (!list.isEmpty() cur - list.get(list.size() - 1)[1] temp) {int[] arr list.remove(list.size() - 1);temp - cur - arr[1];cur arr[0];}list.add(new int[]{cur - temp, end, end - cur temp (list.isEmpty() ? 0 : list.get(list.size() - 1)[2])});}return list.get(list.size() - 1)[2];}// 在集合中二分查找左端点所在区间private static int binarySearch(Listint[] list, Predicateint[] predicate) {int left 0;int right list.size() - 1;while (left right) {int mid left (right - left) / 2;if (predicate.test(list.get(mid))) {right mid - 1;} else {left mid 1;}}return left;}
}七、效果展示
1、输入
[[2,3,1],[5,5,1],[5,6,2]]
2、输出
3
3、说明
tasks[0] 选择时间点 2 或 3tasks[1] 选择时间点 5tasks[2] 选择时间点 5、6因此计算机仅需在时间点 2、5、6 或 3、5、6 三个时刻保持开机即可完成任务。 下一篇华为OD机试真题 Java 实现【路灯照明问题】【2022Q4 100分】感谢fly晨发现这个问题并提供更优质的算法
本文收录于华为OD机试JAVA真题A卷B卷
刷的越多抽中的概率越大每一题都有详细的答题思路、详细的代码注释、样例测试发现新题目随时更新全天CSDN在线答疑。
