华为OD机试真题 Java 实现【支持优先级的队列】【2023 B卷 100分】

article/2023/9/24 21:39:14

一、题目描述

实现一个支持优先级的队列，高优先级先出队列，同优先级时先进先出。

如果两个输入数据和优先级都相同，则后一个数据不入队列被丢弃。

队列存储的数据内容是一个整数。

二、输入描述

一组待存入队列的数据（包含内容和优先级）。

三、输出描述

队列的数据内容（优先级信息输出时不再体现）。

四、补充说明

不用考虑数据不合法的情况，测试数据不超过100个。

五、解题思路

定义一个优先级队列；
先根据优先级比较；
再判断两个输入数据和优先级都相同，则后一个数据不入队列被丢弃；
输出优先级队列；

六、Java算法源码

public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 优先级队列PriorityQueue<ComparePriority> queue = new PriorityQueue<>();String[] arr1 = sc.nextLine().split(",");for (int i = 0; i < arr1.length; i++) {String arr2 = arr1[i].replace("(", "").replace(")", "");String[] arr3 = arr2.split(":");// 数据int data = Integer.valueOf(arr3[0]);// 优先级int priority = Integer.valueOf(arr3[1]);/*** 实现一个支持优先级的队列，高优先级先出队列，同优先级时先进先出。* 如果两个输入数据和优先级都相同，则后一个数据不入队列被丢弃。*/ComparePriority comparePriority = new ComparePriority(data, priority);queue.add(comparePriority);}List<Integer> list = new ArrayList<>();ComparePriority comparePriority = queue.poll();while (comparePriority != null) {if (!comparePriority.equals(queue.peek())) {list.add(comparePriority.data);}comparePriority = queue.poll();}System.out.println(list);
}/*** 实现一个支持优先级的队列，高优先级先出队列，同优先级时先进先出。** 如果两个输入数据和优先级都相同，则后一个数据不入队列被丢弃。*/
static class ComparePriority implements Comparable<ComparePriority> {int data;int priority;public ComparePriority(int data, int priority) {this.data = data;this.priority = priority;}/*** 比较优先级*/@Overridepublic int compareTo(ComparePriority o) {return o.priority - this.priority;}/*** 如果两个输入数据和优先级都相同，则后一个数据不入队列被丢弃。*/@Overridepublic boolean equals(Object o) {if (this == o) {return true;}if (o == null || getClass() != o.getClass()) {return false;}ComparePriority comparePriority = (ComparePriority) o;return data == comparePriority.data && priority == comparePriority.priority;}
}