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

一、题目描述

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

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

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

二、输入描述

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

三、输出描述

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

四、补充说明

不用考虑数据不合法的情况，测试数据不超过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;
    }

    /**
     * 比较优先级
     */
    @Override
    public int compareTo(ComparePriority o) {
        return o.priority - this.priority;
    }

    /**
     * 如果两个输入数据和优先级都相同，则后一个数据不入队列被丢弃。
     */
    @Override
    public 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;
    }
}

七、效果展示

1、输入

(100:1),(200:2),(300:3),(400:3)

2、输出

[300, 400, 200, 100]

3、说明

输入四组数据，每一组第一个数字为内容，第二个数字为优先级。

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

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

数据300和400的优先级最高，都为3，按输入顺序输出，故300,400，然后是优先级为2的200、优先级为1的100。

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

4、下面测试一下“如果两个输入数据和优先级都相同，则后一个数据不入队列被丢弃。”

(100:1),(100:1),(300:3),(400:3)

按道理，应该输出300, 400, 100。

下面，您来试一下？

🏆下一篇：华为OD机试真题 Java 实现【云短信平台优惠活动】【2023Q1 200分】

🏆本文收录于，华为OD机试（JAVA）（2022&2023）

本专栏包含了最新最全的2023年华为OD机试真题，有详细的分析和Java解答。已帮助1000+同学顺利通过OD机考。专栏会持续更新，每天在线答疑。

哪 吒