快捷導(dǎo)航

Java數(shù)據(jù)結(jié)構(gòu)優(yōu)先隊(duì)列實(shí)練

更新時(shí)間：2022年07月21日 11:16:18 作者：風(fēng)鈴聽(tīng)雨~

通常都把隊(duì)列比喻成排隊(duì)買東西，大家都很守秩序，先排隊(duì)的人就先買東西。但是優(yōu)先隊(duì)列有所不同，它不遵循先進(jìn)先出的規(guī)則，而是根據(jù)隊(duì)列中元素的優(yōu)先權(quán)，優(yōu)先權(quán)最大的先被取出，這篇文章主要介紹了java優(yōu)先隊(duì)列的真題，感興趣的朋友一起看看吧

最后一塊石頭的重量

題目描述

思路詳解

這里采用最大堆進(jìn)行解題。

我們首先考慮，每次拿出兩個(gè)最大的進(jìn)行比較，然后大的減去小的重新放入不就完成了嘛。

首先我們創(chuàng)建一個(gè)優(yōu)先隊(duì)列，遍歷重量，放入隊(duì)列。依次取出重量最大的和第二大的，如果a>b就把a(bǔ)-b重新放入。直到隊(duì)列里面的元素只剩1個(gè)的時(shí)候，輸出結(jié)果。

代碼與結(jié)果

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
        for (int stone : stones) {
            pq.offer(stone);
        }
        while (pq.size() > 1) {
            int a = pq.poll();
            int b = pq.poll();
            if (a > b) {
                pq.offer(a - b);
            }
        }
        return pq.isEmpty() ? 0 : pq.poll();
    }
}

裝滿杯子需要的最短總時(shí)長(zhǎng)

題目描述

思路詳解

這個(gè)題也是思考了很久。

分兩種情況：

第一種：很好想，有一種水特別多，那么答案就是這種水的杯數(shù)。

第二種：就是一定可以匹配完成或者匹配到只剩一杯。

我們只需要先排序，在分情況就好。

代碼與結(jié)果

class Solution {
    public int fillCups(int[] amount) {
        Arrays.sort(amount);
        int sum=amount[0]+amount[1]+amount[2];
        if(amount[1]+amount[0]>=amount[2]) sum=(sum+1)/2;
        else sum=amount[2];
        return sum;
    }
}

移除石子的最大得分

題目描述

思路詳解

本題的思路看起來(lái)簡(jiǎn)單，也不是很好想。

我們先排一下序，兩種情況：

第一種：前兩個(gè)的和小于第三個(gè)，這時(shí)候我們一直拿最后一堆和任意一堆，結(jié)果就是a+b。

第二種：前兩個(gè)數(shù)的和大于第三個(gè)數(shù)，那么前兩堆一定可以內(nèi)部抵消一部分。只需總和除以2就好。

代碼與結(jié)果

class Solution {
	public int maximumScore(int a, int b, int c) {
		int[] arr = new int[] { a, b, c };
		Arrays.sort(arr);
		a = arr[0];
		b = arr[1];
		c = arr[2];
		if (a + b <= c) {
			return a + b;
		} else {
			return (a + b + c) / 2;
		}
	}
}

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)優(yōu)先隊(duì)列實(shí)練的文章就介紹到這了,更多相關(guān)Java優(yōu)先隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: