502. IPO(贪心算法+优先队列/堆)
整体思想:在满足可用资金的情况下,选择其中利润最大的业务,直到选到k个业务为止,注意k可能比n大。
每次选择完一个业务,可用资金都会变动,这是可选择的业务也会变化,因此每次将可选择的业务放在一个优先队列(大顶堆)中,堆顶元素就是目标业务。
优先队列(堆)的实现方式:优先队列,自定义比较器。
另外注意,将业务根据所需资金capacity进行升序排列,达到一种剪枝的目的。
class Solution {public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {int n = profits.length;List<int[]> list = new ArrayList<>();for (int i = 0; i < n; ++i) {list.add(new int[] {capital[i], profits[i]});}Collections.sort(list, (a, b) -> a[0] - b[0]);PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);int i = 0;while (k-- > 0) {while (i < n && list.get(i)[0] <= w) q.add(list.get(i++)[1]);if (q.isEmpty()) break;w += q.poll();}return w;}
}
拓展:
-
优先队列
在Java中,优先队列(PriorityQueue)是一种特殊的队列,它可以确保队列中元素的顺序是按照它们的优先级进行排列的数据结构。在优先队列中,具有较高优先级的元素会先被处理,而具有较低优先级的元素会被放置在队列的尾部。
优先队列可以用于许多应用,比如任务调度、事件模拟等。在Java中,优先队列通常是基于堆(Heap)实现的,这意味着它可以高效地支持插入和删除具有最高(或最低)优先级的元素。
import java.util.PriorityQueue; public class Main { public static void main(String[] args) { // 创建一个优先队列 PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(); // 向优先队列中添加元素 priorityQueue.add(3); priorityQueue.add(1); priorityQueue.add(2); // 输出队列中的元素(按照优先级顺序) while (!priorityQueue.isEmpty()) { System.out.println(priorityQueue.poll()); } } }需要注意的是,当元素被添加到优先队列中时,它们会根据其自然顺序或者根据提供的比较器进行排序。默认情况下,优先队列会按照元素的自然顺序进行排序,但也可以通过提供自定义的比较器来改变排序规则。
-
比较器
在Java中,
Collections.sort方法用于对集合进行排序。它可以接受一个比较器(Comparator)作为第二个参数,以便根据指定的比较规则对集合中的元素进行排序。比较器是一个接口,它定义了用于比较两个对象顺序的规则。在
Collections.sort中,当传入比较器时,它将根据比较器所定义的规则对集合中的元素进行排序。具体来说,比较器的定义如下:
public interface Comparator<T> {int compare(T o1, T o2); }这个接口中的
compare方法接受两个参数o1和o2,分别代表要比较的两个对象。在这个方法中,需要定义比较规则,返回一个负整数、零或者正整数,分别表示第一个参数小于、等于或大于第二个参数。在实际使用中,可以通过创建实现了Comparator接口的类,或者使用Lambda表达式来定义比较器。比如:
List<Integer> numbers = Arrays.asList(3, 1, 2); Collections.sort(numbers, (a, b) -> a - b);在这个例子中,
(a, b) -> a - b就是一个比较器,它定义了对整数列表进行升序排序的规则。具体来说,它告诉Collections.sort方法按照元素的大小进行排序。总之,比较器允许我们根据特定的规则对集合中的元素进行排序,从而满足不同的排序需求。
相关文章:
502. IPO(贪心算法+优先队列/堆)
整体思想:在满足可用资金的情况下,选择其中利润最大的业务,直到选到k个业务为止,注意k可能比n大。 每次选择完一个业务,可用资金都会变动,这是可选择的业务也会变化,因此每次将可选择的业务放在…...
设计模式篇---中介者模式
文章目录 概念结构实例总结 概念 中介者模式:用一个中介对象来封装一系列的对象交互。中介者使各对象不需要显示地相互引用,从而使其耦合松散,而且可以独立地改变它们之间的交互。 就好比世界各个国家之间可能会产生冲突,但是当产…...
双端Diff算法
双端Diff算法 双端Diff算法指的是,在新旧两组子节点的四个端点之间分别进行比较,并试图找到可复用的节点。相比简单Diff算法,双端Diff算法的优势在于,对于同样的更新场景,执行的DOM移动操作次数更少。 简单 Diff 算法…...
react+antd,Table表头文字颜色设置
1、创建一个自定义的TableHeaderCell组件,并设置其样式为红色 const CustomTableHeaderCell ({ children }) > (<th style{{ color: "red" }}>{children}</th> ); 2、将CustomTableHeaderCell组件传递到Table组件的columns属性中的titl…...
2024年1月18日Arxiv最热NLP大模型论文:Large Language Models Are Neurosymbolic Reasoners
大语言模型化身符号逻辑大师,AAAI 2024见证文本游戏新纪元 引言:文本游戏中的符号推理挑战 在人工智能的众多应用场景中,符号推理能力的重要性不言而喻。符号推理涉及对符号和逻辑规则的理解与应用,这对于处理现实世界中的符号性…...
服务限流实现方案
服务限流怎么做 限流算法 计数器 每个单位时间能通过的请求数固定,超过阈值直接拒绝。 通过维护一个单位时间内的计数器,每次请求计数器加1,当单位时间内计数器累加到大于设定的阈值,则之后的请求都被绝,直到单位时…...
【RTOS】快速体验FreeRTOS所有常用API(1)工程创建
目录 一、工程创建1.1 新建工程1.2 配置RCC1.3 配置SYS1.4 配置外设1)配置 LED PC132)配置 串口 UART13)配置 OLED I2C1 1.5 配置FreeRTOS1.6 工程设置1.7 生成代码1.8 keil设置下载&复位1.9 添加用户代码 快速体验FreeRTOS所有常用API&a…...
Red Hat Enterprise Linux 8.9 安装图解
风险告知 本人及本篇博文不为任何人及任何行为的任何风险承担责任,图解仅供参考,请悉知!本次安装图解是在一个全新的演示环境下进行的,演示环境中没有任何有价值的数据,但这并不代表摆在你面前的环境也是如此。生产环境…...
vcruntime140.dll文件修复的几种常见解决办法,vcruntime140.dll丢失的原因
vcruntime140.dll文件是Windows操作系统中的一个重要动态链接库(DLL)文件,它是Microsoft Visual C Redistributable的一部分。当出现vcruntime140.dll文件丢失的情况时,可能会导致一些程序无法正常运行或出现错误提示。为了电脑能…...
SpringCloud Alibaba 深入源码 - Nacos 分级存储模型、支撑百万服务注册压力、解决并发读写问题(CopyOnWrite)
目录 一、SpringCloudAlibaba 源码分析 1.1、SpringCloud & SpringCloudAlibaba 常用组件 1.2、Nacos的服务注册表结构是怎样的? 1.2.1、Nacos的分级存储模型(理论层) 1.2.2、Nacos 源码启动(准备工作) 1.2.…...
算法训练营Day45
#Java #动态规划 Feeling and experiences: 最长公共子序列:力扣题目链接 给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。 一个字符串的 子序列 是指这样一个新…...
【Redis漏洞利用总结】
前言 redis是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。Redis默认使用 6379 端口。 一、redis未授权访问漏洞 0x01 漏洞描述 描述: Redis是一套开源的使用ANSI C编写、支持网络、可基于内存…...
SPI 动态服务发现机制
SPI(Service Provier Interface)是一种服务发现机制,通过ClassPath下的META—INF/services文件查找文件,自动加载文件中定义的类,再调用forName加载; spi可以很灵活的让接口和实现分离, 让API提…...
【C++进阶07】哈希表and哈希桶
一、哈希概念 顺序结构以及平衡树中 元素关键码与存储位置没有对应关系 因此查找一个元素 必须经过关键码的多次比较 顺序查找时间复杂度为O(N) 平衡树中为树的高度,即O( l o g 2 N log_2 N log2N) 搜索效率 搜索过程中元素的比较次数 理想的搜索方法:…...
Go 语言实现冒泡排序算法的简单示例
以下是使用 Go 语言实现冒泡排序算法的简单示例: package mainimport "fmt"func bubbleSort(arr []int) {n : len(arr)for i : 0; i < n-1; i {for j : 0; j < n-i-1; j {if arr[j] > arr[j1] {// 交换元素arr[j], arr[j1] arr[j1], arr[j]}}}…...
JAVA 学习 面试(五)IO篇
BIO是阻塞I/O,NIO是非阻塞I/O,AIO是异步I/O。BIO每个连接对应一个线程,NIO多个连接共享少量线程,AIO允许应用程序异步地处理多个操作。NIO,通过Selector,只需要一个线程便可以管理多个客户端连接࿰…...
vue3相比vue2的效率提升
1、静态提升 2、预字符串化 3、缓存事件处理函数 4、Block Tree 5、PatchFlag 一、静态提升 在vue3中的app.vue文件如下: 在服务器中,template中的内容会变异成render渲染函数。 最终编译后的文件: 1.静态节点优化 那么这里为什么是两部分…...
web terminal - 如何在mac os上运行gotty
gotty可以让你使用web terminal的方式与环境进行交互,实现终端效果 假设你已经配置好了go环境,首先使用go get github.com/yudai/gotty命令获取可执行文件,默认会安装在$GOPATH/bin这个目录下,注意如果你的go版本比较高ÿ…...
机械设计-哈工大课程学习-螺纹连接
圆柱螺纹主要几何参数螺纹参数 ①外径(大径),与外螺纹牙顶或内螺纹牙底相重合的假想圆柱体直径。螺纹的公称直径即大径。 ②内径(小径),与外螺纹牙底或内螺纹牙顶相重合的假想圆柱体直径。 ③中径ÿ…...
ai绘画|stable diffusion的发展史!简短易懂!!!
手把手教你入门绘图超强的AI绘画,用户只需要输入一段图片的文字描述,即可生成精美的绘画。给大家带来了全新保姆级教程资料包 (文末可获取) 一、stable diffusion的发展史 本文目标:学习交流 对于熟悉SD的同学&#x…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...
10-Oracle 23 ai Vector Search 概述和参数
一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...
AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...
NPOI操作EXCEL文件 ——CAD C# 二次开发
缺点:dll.版本容易加载错误。CAD加载插件时,没有加载所有类库。插件运行过程中用到某个类库,会从CAD的安装目录找,找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库,就用插件程序加载进…...
