Java数据结构优先队列实练

2024-08-01 08:49:12

最后一块石头的重量

题目描述

思路详解

这里采用最大堆进行解题。

我们首先考虑，每次拿出两个最大的进行比较，然后大的减去小的重新放入不就完成了嘛。

首先我们创建一个优先队列，遍历重量，放入队列。依次取出重量最大的和第二大的，如果a>b就把a-b重新放入。直到队列里面的元素只剩1个的时候，输出结果。

代码与结果

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();
    }
}

装满杯子需要的最短总时长

题目描述

思路详解

这个题也是思考了很久。

分两种情况：

第一种：很好想，有一种水特别多，那么答案就是这种水的杯数。

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

我们只需要先排序，在分情况就好。

代码与结果

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;
    }
}

移除石子的最大得分

题目描述

思路详解

本题的思路看起来简单，也不是很好想。

我们先排一下序，两种情况：

第一种：前两个的和小于第三个，这时候我们一直拿最后一堆和任意一堆，结果就是a+b。

第二种：前两个数的和大于第三个数，那么前两堆一定可以内部抵消一部分。只需总和除以2就好。

代码与结果

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;
		}
	}
}

到此这篇关于Java数据结构优先队列实练的文章就介绍到这了,更多相关Java优先队列内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

Java基于堆结构实现优先队列功能示例

本文实例讲述了Java基于堆结构实现优先队列功能.分享给大家供大家参考,具体如下: package Demo; import java.util.NoSuchElementException; /* * 小顶堆 java使用堆结构实现优先队列 */ public class JPriorityQueue<E> { @SuppressWarnings("hiding") class QueueNode<E> { int capacity; int size; E[
Java优先队列 priority queue

目录 1.优先队列概念 2.二叉堆(Heap) 完全二叉树和满二叉树堆的重要操作 1.优先队列概念优先队列(priority queue)是一种特殊的数据结构. 队列中每一个元素都被分配到一个优先权值,出队顺序按照优先权值来划分. 一般有两种出队顺序:高优先权出队或低优先权出队. priority queue至少要有两个最基本的ADT:进队,出队(按照高优先权或低优先权) 产生原因:同样是为了提高数据处理的效率.试想,要实现优先队列对应的功能,若使用链表或者数组,那么要么先排序再插入,要么先
Java优先队列(PriorityQueue)重写compare操作

we can custom min heap or max heap by override the method compare. package myapp.kit.quickstart.utils; import java.util.Comparator; import java.util.Queue; /** * priority queue (heap) demo. * * @author huangdingsheng * @version 1.0, 2020/5/8 */ publi
java优先队列PriorityQueue中Comparator的用法详解

在使用java的优先队列PriorityQueue的时候,会看到这样的用法. PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>(){ @Override public int compare(Integer o1, Integer o2){ return o1.compareTo(o2); } }); 那这样到底构造的是最大优先还是最小优先队列呢? 看看源码
Java数据结构之堆(优先队列)的实现

堆(优先队列)是一种典型的数据结构,其形状是一棵完全二叉树,一般用于求解topk问题.根据双亲节点大于等于孩子节点或双亲节点小于等于孩子节点,可分为大顶堆和小顶堆,本文实现大顶堆. 根据大顶堆的定义,大顶堆的双亲节点大于等于其孩子节点,堆顶元素最大,对于每一个子树都是一个大顶堆,则从最后一个双亲节点进行调整为大顶堆,一直到根节点,则可构建一个大顶堆. 我们这里采用数组去存储,以heap={3,2,1,5,6,4}为例,需要一个init(int[] heap)初始化方法,从最后一个双亲节点开始将h
Java的优先队列PriorityQueue原理及实例分析

这篇文章主要介绍了Java的优先队列PriorityQueue原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下一.优先队列概述优先队列PriorityQueue是Queue接口的实现,可以对其中元素进行排序, 可以放基本数据类型的包装类(如:Integer,Long等)或自定义的类对于基本数据类型的包装器类,优先队列中元素默认排列顺序是升序排列但对于自己定义的类来说,需要自己定义比较器二.常用方法 peek()//返回队首元素
java数据结构-堆实现优先队列

目录一.二叉树的顺序存储 1.堆的存储方式 2.下标关系二.堆(heap) 1.概念 2.大/小根堆 2.1小根堆 2.2大根堆 3.建堆操作 3.1向下调整 4.入队操作 4.1向上调整 4.2push 入队的完整代码展示 5.出队操作 5.1pop 出队代码完全展示 6.查看堆顶元素 7.TOK 问题 7.1TOPK 8.堆排序文章内容介绍大纲一.二叉树的顺序存储 1.堆的存储方式使用数组保存二叉树结构,方式即将二叉树用层序遍历方式放入数组中. 一般只适合表示完全二叉树,因为非完
java编程实现优先队列的二叉堆代码分享

这里主要介绍的是优先队列的二叉堆Java实现,代码如下: package practice; import edu.princeton.cs.algs4.StdRandom; public class TestMain { public static void main(String[] args) { int[] a = new int[20]; for (int i = 0; i < a.length; i++) { int temp = (int)(StdRandom.random()*1
Java数据结构优先队列实练

目录最后一块石头的重量题目描述思路详解代码与结果装满杯子需要的最短总时长题目描述思路详解代码与结果移除石子的最大得分题目描述思路详解代码与结果最后一块石头的重量题目描述思路详解这里采用最大堆进行解题. 我们首先考虑,每次拿出两个最大的进行比较,然后大的减去小的重新放入不就完成了嘛. 首先我们创建一个优先队列,遍历重量,放入队列.依次取出重量最大的和第二大的,如果a>b就把a-b重新放入.直到队列里面的元素只剩1个的时候,输出结果. 代码与结果 class Solu
Java真题实练掌握哈希表的使用

目录 1.多数元素题目描述思路详解代码与结果 2.数组中的k-diff数对题目描述思路详解代码与结果 3.缺失的第一个正数题目描述思路详解代码与结果 1.多数元素题目描述思路详解这个思路比较简单,先排序,排序过后遍历如果后一个等于前一个输出就好代码与结果 class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length / 2]; }
Java数据结构之堆(优先队列)详解

目录堆的性质堆的分类堆的向下调整堆的建立堆得向上调整堆的常用操作入队列出队列获取队首元素 TopK 问题例子数组排序堆的性质堆逻辑上是一棵完全二叉树,堆物理上是保存在数组中 . 总结:一颗完全二叉树以层序遍历方式放入数组中存储,这种方式的主要用法就是堆的表示. 并且如果已知父亲(parent) 的下标, 则: 左孩子(left) 下标 = 2 * parent + 1; 右孩子(right) 下标 = 2 * parent + 2; 已知孩子(不区分左右)(child
Java数据结构之最小堆和最大堆的原理及实现详解

目录一.前言二.堆的数据结构三.堆的代码实现 1. 实现介绍 2. 入堆实现 3. 出堆实现 4. 小堆实现 5. 大堆实现一.前言堆的历史堆的数据结构有很多种体现形式,包括:2-3堆.B堆.斐波那契堆,而在 Java API 中最常用的是用于实现优先队列的二叉堆,它是由 JWJ Williams 在 1964 年引入的,作为堆排序算法的数据结构.另外在 Dijkstra 算法等几种高效的图算法中,堆也是非常重要的. 二.堆的数据结构在计算机科学中,堆(heap) 的实现是一种基于
Java使用dom4j实现对xml简单的增删改查操作示例

本文实例讲述了Java使用dom4j实现对xml简单的增删改查操作.分享给大家供大家参考,具体如下: xml留了个结课作业: 后台用xml文件作为存储做个迷你系统实现增删改查的功能, 在此记录一下先得引入dom4j的jar包放在项目的WEB-INF-->lib目录下先新建一个读取器, 读取你想操作的xml文件(我这里写的绝对路径) //读取XML文件,获得document对象 SAXReader reader = new SAXReader(); Document document = n
Java数据结构之栈与队列实例详解

目录一,栈 1,概念 2,栈的操作 3,栈的实现 4,实现mystack 二,队列 1,概念 2,队列的实现 3,实现myqueue 栈.队列与数组的区别? 总结一,栈 1,概念在我们软件应用 ,栈这种后进先出数据结构的应用是非常普遍的.比如你用浏览器上网时不管什么浏览器都有个"后退"键,你点击后可以接访问顺序的逆序加载浏览过的网页. 很多类似的软件,比如 Word Photoshop 等文档或图像编软件中都有撤销 )的操作,也是用栈这种方式来实现的,当然不同的
Java 数据结构与算法系列精讲之二叉堆

目录概述优先队列二叉堆二叉堆实现获取索引添加元素 siftUp 完整代码概述从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 优先队列优先队列 (Priority Queue) 和队列一样, 是一种先进先出的数据结构. 优先队列中的每个元素有各自的优先级, 优先级最高的元素最先得到服务. 如图: 二叉堆二叉堆 (Binary Heap) 是一种特殊的堆, 二叉堆具有堆的性质和二叉树的性质. 二叉堆中的任意一节点的值总是大于等于其孩子节点值. 如图: 二
Java数据结构之优先级队列(堆)图文详解

目录一.堆的概念二.向下调整 1.建初堆 2.建堆三.优先级队列 1.什么是优先队列? 2.入队列 3.出队列 4.返回队首元素 5.堆的其他TopK问题总结: 总结一.堆的概念堆的定义:n个元素的序列{k1 , k2 , … , kn}称之为堆,当且仅当满足以下条件时: (1)ki >= k2i 且 ki >= k(2i+1) ——大根堆 (2) ki <= k2i 且 ki <= k(2i+1) ——小根堆简单来说: 堆是具有以下性质的完全二叉树:(1)每个结点的