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…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...
理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...
ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
