[华为OD]实现一个支持优先级的队列,高优先级先出队列 100

题目:

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

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

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

输入描述:

一组待存入队列的数据(包含内容和优先级)

输出描述:

队列的数据内容(优先级信息输出时不再体现)

补充说明:

不用考虑输入数据不合法的情况,测试数据不超过 100 个

示例 1

输入:

(10,1),(20,1),(30,2),(40,3)

输出:

40,30,10,20

说明:

输入样例中,向队列写入了 4 个数据,每个数据由数据内容和优先级组成。

输入和输出内容都不含空格。

数据 40 的优先级最高,所以最先输出,其次是 30;10 和 20 优先级相同,所以按输入

顺序输出。

示例 2

输入:

(10,1),(10,1),(30,2),(40,3)

输出:

40,30,10说明:

输入样例中,向队列写入了 4 个数据,每个数据由数据内容和优先级组成。

输入和输出内容都不含空格。

数据 40 的优先级最高,所以最先输出,其次是 30;两个 10 和 10 构成重复数据,被丢

弃一个

题解:

需要构造对象,对象里面三个元素,输入数据,优先级,和输入位置。

然后重写equals方法,采用set集合去重和compareTo 排序方法,再排序输入在list中,输出需要的值就可以了

import java.util.Objects;

public class Data implements Comparable<Data> {
    private int index;
    private int value;
    private int height;

    public Data(int value, int height, int index) {
        this.index = index;
        this.value = value;
        this.height = height;
    }

    public int getIndex() {
        return index;
    }

    public void setIndex(int index) {
        this.index = index;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public int getHeight() {
        return height;
    }

    public void setHeight(int height) {
        this.height = height;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Data data = (Data) o;
        return value == data.value &&
                height == data.height;
    }

    @Override
    public int hashCode() {
        return Objects.hash(value, height);
    }

    @Override
    public int compareTo(Data o) {
        if (this.height != o.height) return o.height - this.height;
        return this.index - o.index;
    }
}
import java.util.*;
import java.util.stream.Collectors;

public class PriQueue {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String str = sc.nextLine();
        String[] stArr = str.substring(1, str.length() - 1).split("\\),\\(");


        Set<Data> dataSet = new HashSet<>();
        for (int i = 0; i < stArr.length; i++) {
            String[] art = stArr[i].split(",");
            Data data = new Data(Integer.valueOf(art[0]), Integer.valueOf(art[1]), i);
            if(!dataSet.contains(data)){
                dataSet.add(data);
            }
        }

        List<Data> dataList = dataSet.stream().sorted().collect(Collectors.toList());

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < dataList.size(); i++) {
            if (i != 0) sb.append(",");
            sb.append(dataList.get(i).getValue());
        }

        System.out.println(sb.toString());
    }
}

验证结果:

上一篇:基于深度学习的实时人脸检测与情绪分类


下一篇:HTTPS原理