【Java】HOT100 贪心算法
目录
理论基础
一、简单贪心
LeetCode455:分发饼干
二、中等贪心
2.1 序列问题
LeetCode376:摆动序列
2.2 贪心股票问题
LeetCode121:买卖股票的最佳时机
LeetCode121:买卖股票的最佳时机ii
2.3 两个维度权衡问题
LeetCode135:分发糖果
三、较难问题
区间问题
LeetCode55:跳跃游戏i
LeetCode55:跳跃游戏ii
LeetCode452:用最少数量的箭引爆气球
LeetCode435:无重叠区间
LeetCode763:划分字母区间
LeetCode56:合并区间
其他
LeetCode53:最大子序和
贪心算法其实就是没有什么规律可言,所以大家了解贪心算法 就了解它没有规律的本质就够了。 不用花心思去研究其规律, 没有思路就立刻看题解。基本贪心的题目 有两个极端,要不就是特简单,要不就是死活想不出来。
学完贪心之后再去看动态规划,就会了解贪心和动规的区别。
理论基础
贪心的本质是选择每一阶段的局部最优,从而达到全局最优。
举例:有一堆钞票,你可以拿走十张,如果想达到最大的金额,你要怎么拿?指定每次拿最大的,最终结果就是拿走最大数额的钱。
每次拿最大的就是局部最优,最后拿走最大数额的钱就是推出全局最优。
再举一个例子如果是 有一堆盒子,你有一个背包体积为n,如何把背包尽可能装满,如果还每次选最大的盒子,就不行了。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。
什么时候用贪心呢?没有固定的套路。刷题或者面试的时候,手动模拟一下感觉可以局部最优推出整体最优,而且想不到反例,那么就试一试贪心。
贪心算法一般分为如下四步:
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
一、简单贪心
LeetCode455:分发饼干
思路:这里的局部最优就是大饼干喂给胃口大的,充分利用饼干尺寸喂饱一个,
全局最优就是喂饱尽可能多的小孩。
所以可以尝试使用贪心策略,先将饼干数组和小孩数组排序。然后从后向前遍历小孩数组,用大饼干优先满足胃口大的,并统计满足小孩数量。
class Solution {// 思路:优先考虑胃口,先喂饱大胃口public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int count = 0;int start = s.length - 1;// 遍历胃口for (int index = g.length - 1; index >= 0; index--) {if(start >= 0 && g[index] <= s[start]) {start--;count++;}}return count;}
}
二、中等贪心
2.1 序列问题
LeetCode376:摆动序列
思路:局部最优是删除连续坡度上的节点,保证这个坡度有两个局部峰值
整体最优是整个序列拥有最多的局部峰值
在实际操作上,实际连删除都不用做,只需添加数组的局部峰值即可
本题的难度在于要考虑多种情况:(curdiff代表后一个坡度,prediff代表前一个坡度)
即单调有平坡、上下中间有平坡和只有两个数的情况,具体分析见代码随想录
class Solution {public int wiggleMaxLength(int[] nums) {if (nums.length <= 1) {return nums.length;}//当前差值int curDiff = 0;//上一个差值int preDiff = 0;int count = 1;for (int i = 1; i < nums.length; i++) {//得到当前差值curDiff = nums[i] - nums[i - 1];//如果当前差值和上一个差值为一正一负//等于0的情况表示初始时的preDiffif ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {count++;preDiff = curDiff;}}return count;}
}
这道题还可以用动态规划来做,这里就不讲了。之后可以试着做一做。
2.2 贪心股票问题
LeetCode121:买卖股票的最佳时机
思路:局部最优即左界最小,在局部最优的基础上要求的全局最优即右界最大,也就是差值最大。
class Solution {public int maxProfit(int[] prices) {int max = 0;int low = Integer.MAX_VALUE; //保留左侧最小值for (int i = 0; i < prices.length; i++) {low = Math.min(low, prices[i]); // 取最左最小价格,确定左界max = Math.max(max, prices[i] - low); // 寻找右侧最大值}return max;}
}
LeetCode121:买卖股票的最佳时机ii
思路:局部最优即在区间中寻找所有的最大递增子区间,且子区间之间不能重叠
整体最优:取所有最大的递增子区间,最后利润和也最大。
由于最后只要求利润,该题可以变成只要收集每天的正利润,而无需考虑区间的左右界。
// 贪心思路
class Solution {public int maxProfit(int[] prices) {int result = 0;for (int i = 1; i < prices.length; i++) {result += Math.max(prices[i] - prices[i - 1], 0);}return result;}
}
2.3 两个维度权衡问题
LeetCode135:分发糖果
思路:本题需要先确定一遍后,在确定另一边,从左到右的局部最优即:只要右边评分比左边大,右边的孩子就多一个糖果。全局最优:评分高的右边孩子比左边孩子糖果更多。
本题需要先从左到右更新,再从右到左,这样才能满足相邻条件。从右到左局部最优:取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量,保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优:相邻的孩子中,评分高的孩子获得更多的糖果。
class Solution {/**分两个阶段1、起点下标1 从左往右,只要 右边 比 左边 大,右边的糖果=左边 + 1,不大于就取最小糖果数1;2、起点下标 ratings.length - 2 从右往左, 只要左边 比 右边 大,此时 左边的糖果应该 取本身的糖果数(符合比它左边大) 和 右边糖果数 + 1 二者的最大值,这样才符合 它比它左边的大,也比它右边大*/public int candy(int[] ratings) {int len = ratings.length;int[] candyVec = new int[len];candyVec[0] = 1;for (int i = 1; i < len; i++) {candyVec[i] = (ratings[i] > ratings[i - 1]) ? candyVec[i - 1] + 1 : 1;}for (int i = len - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1]) {candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);}}int ans = 0;for (int num : candyVec) {ans += num;}return ans;}
}
三、较难问题
区间问题
LeetCode55:跳跃游戏i
思路:总共要跳nums.length-1步才能到达终点,局部解即取最大跳跃步数max,每次循环以第一轮的max为起点再次计算max的覆盖范围
整体解即所有的最大跳跃步数范围是否能覆盖到终点。
class Solution {public boolean canJump(int[] nums) {int max = 0;for(int i=0;i<=max;i++){ //这里注意是小于等于max,max更新等于以新一轮覆盖点为起点再次覆盖max = Math.max(i+nums[i],max);if(max>=nums.length-1) return true;}return false;}
}
LeetCode55:跳跃游戏ii
思路:局部解即每次的跳转步数尽可能最大,这样跳跃次数就最小
整体解即范围覆盖到终点且跳跃次数最小
本题的关键在于什么时候对步数进行+1?用到两个变量curIndex和preIndex来确定位置
class Solution {public int jump(int[] nums) {int nextIndex = 0;int curIndex = 0;int count = 0;for(int i=0; i<=nums.length;i++){nextIndex = Math.max(nextIndex,i+nums[i]);if(i == curIndex){ //当走到当前的最大覆盖范围时,判断是否到终点count++; //如果没到,就要跳一步curIndex = nextIndex; //跳到更新过的下一坐标if(nextIndex >= nums.length - 1) break; //如果到了则走完了}}return count;}
}
LeetCode452:用最少数量的箭引爆气球
思路:写了435,这道题就很容易了
class Solution {public int findMinArrowShots(int[][] points) {int count = 1;Arrays.sort(points, (x,y)->Integer.compare(x[1],y[1]));int end = points[0][1];for(int i=1;i<points.length;i++){//只要右界排序,记录不重叠的情况就可以了,每次不重叠就需要多一支箭if(end < points[i][0]){ count++;end = points[i][1];}}return count;}
}
LeetCode435:无重叠区间
思路:重叠区间问题通常有两种思路:要么是按左边界排序,要么是按右边界
1. 按右边界升序排列,从左向右可以记录非重叠区间的个数,总数-非重叠个数=重叠个数
非重叠只要判断end和上一区间的左区间的关系
class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a,b)-> {return Integer.compare(a[1],b[1]);});int count = 1; //记录非重叠区间的个数int end = intervals[0][1];for(int i = 1;i < intervals.length;i++){if(end <= intervals[i][0]){ //无重叠区间,count++,更新endcount++;end = intervals[i][1];}}return intervals.length-count;}
}
2. 按左边界升序排序,向左到右可以记录重叠的区间个数,直接得到重叠个数就是移除个数
非重叠和重叠都要更新end,之所以count取end和右界的较小值是因为,可能会出现>=3个区间重叠的情况。
class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a,b)-> {return Integer.compare(a[0],b[0]);});int count = 0; //记录重叠区间的个数int end = intervals[0][1];for(int i = 1;i < intervals.length;i++){if(end <= intervals[i][0]){ //无重叠区间,更新endend = intervals[i][1];}else{count++;end = Math.min(end, intervals[i][1]); //重叠区间的end}}return count;}
}
LeetCode763:划分字母区间
思路:首先遍历计算每个字母的最后出现下标,然后从头开始遍历,并更新最远出现下标,当到达最后序号时进行一次分割
class Solution {public List<Integer> partitionLabels(String s) {List<Integer> list = new ArrayList<>();int[] record = new int[26];//首先记录字母最后一次出现的下标for(int i=0;i<s.length();i++){record[s.charAt(i)-'a'] = i;}int idx = 0;int last = -1;//然后当遍历下标等于最后一次的下标时,添加字符串长度for(int i=0;i<s.length();i++){idx = Math.max(idx, record[s.charAt(i)-'a']);if(i == idx){list.add(idx-last); //先添加结果到list,再更新last = idx;}}return list;}
}
LeetCode56:合并区间
思路:同样首先按照左边界先排序,然后判断左边界和最右边界
(记得判断=到底属于那种情况)
class Solution {public int[][] merge(int[][] intervals) {List<int[]> res = new LinkedList<>();Arrays.sort(intervals, (x,y)->Integer.compare(x[0],y[0]));int left = intervals[0][0];int right = intervals[0][1];for(int i = 1; i<intervals.length; i++){if(right >= intervals[i][0]){ //重叠,合并right = Math.max(right, intervals[i][1]);}else{ //不重叠,添加旧区间,更新left、rightres.add(new int[]{left, right});left = intervals[i][0];right = intervals[i][1];}}res.add(new int[]{left, right});return res.toArray(new int[res.size()][2]);}
}
其他
LeetCode53:最大子序和
思路:连续子数组局部最优,即遇到连续和count为负数,则立刻放弃当前count,置0,相当于从当前位置重新开始计算连续子数组和。整体最优即用sum来计算循环中count的最大值。
class Solution {public int maxSubArray(int[] nums) {if (nums.length == 1){return nums[0];}int sum = Integer.MIN_VALUE;int count = 0;for (int i = 0; i < nums.length; i++){count += nums[i];sum = Math.max(sum, count); // 取区间累计的最大值(相当于不断确定最大子序终止位置)if (count <= 0){count = 0; // 相当于重置最大子序起始位置,因为遇到负数一定是拉低总和}}return sum;}
}
相关文章:
【Java】HOT100 贪心算法
目录 理论基础 一、简单贪心 LeetCode455:分发饼干 二、中等贪心 2.1 序列问题 LeetCode376:摆动序列 2.2 贪心股票问题 LeetCode121:买卖股票的最佳时机 LeetCode121:买卖股票的最佳时机ii 2.3 两个维度权衡问题 LeetCode135&…...
绝地求生:PUBG杜卡迪联名进入倒计时3天!
大家好,我是闲游盒。 杜卡迪联名已经进入倒计时3天!喜欢的朋友要注意结束时间可千万别错过! 杜卡迪6色车辆 随着五一小长假的结束,本次混沌漫彩通行证也即将结束,本次通行证31级之后没升1级可额外领取1500BP和挑战者纪…...
【论文阅读】Learning Texture Transformer Network for Image Super-Resolution
Learning Texture Transformer Network for Image Super-Resolution 论文地址Abstract1. 简介2.相关工作2.1单图像超分辨率2.2 Reference-based Image Super-Resolution 3. 方法3.1. Texture TransformerLearnable Texture Extractor 可学习的纹理提取器。Relevance Embedding.…...
读字库写FM24C04
/*PCB机板增加读写24C64函数PAST 2017 12 26 08:10 CODE 7382*/ /*按11键进入手动选择,按12键进入参数设定界面 按1存1 2存2 3存3 15存0 16存1236 17读EEPROM显示正确 L1008 13775061792 ******/ #include <reg52.h>…...
boost::asio::ip::tcp::socket set_option
Boost asio 官方教程简介_asio::write-CSDN博客 boost::asio::ip::tcp::socket 是一个用于异步I/O操作的类,它是Boost.Asio库的一部分,专门用于处理TCP套接字。 以下是一个简单的使用 boost::asio::ip::tcp::socket 的例子,这个例子展示了如…...
华为鸿蒙HarmonyOS应用开发者高级认证答案
判断 1只要使用端云一体化的云端资源就需要支付费用(错) 2所有使用Component修饰的自定义组件都支持onPageShow,onBackPress和onPageHide生命周期函数。(错) 3 HarmonyOS应用可以兼容OpenHarmony生态(对…...
ElasticSearch 与 OpenSearch:拉开性能差距
Elasticsearch 与 OpenSearch:扩大性能差距 对于任何依赖快速、准确搜索数据的组织来说,强大、快速且高效的搜索引擎是至关重要的元素。对于开发人员和架构师来说,选择正确的搜索平台可以极大地影响您的组织提供快速且相关结果的能力。在我们…...
Java构造器
构造器 无参构造器有参构造器构造方法VS成员方法总结 概念:也称构造方法、构造函数。作用是构造出来一个类的实例,确保对象得到初始化。 格式: 权限修饰符 类名(无参/有参){ }。 分类: 带参数:有参构造器不带参数&am…...
TiDB系列之:使用TiUP部署TiDB集群最新版本,同时部署TiCDC的详细步骤
TiDB系列之:使用TiUP部署TiDB集群最新版本,同时部署TiCDC的详细步骤 一、部署TiDB集群二、准备环境三、安装 TiUP四、安装TiUP cluster组件五、初始化包含TiCDC的TiDB集群拓扑文件六、检查和修复集群存在的潜在风险七、查看可以安装的tidb版本八、部署 TiDB 集群:九、查看集…...
【经典算法】LeetCode 72. 编辑距离(Java/C/Python3/Go实现含注释说明,中等)
题目描述 给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数。 你可以对一个单词进行如下三种操作: 插入一个字符删除一个字符替换一个字符 原题:LeetCode 72 思路及实现 方式一:动态规划 思路…...
webstorm 常用插件
安装插件步骤: 打开软件,文件 -- 设置-- 插件 -- 输入插件名称 -- 安装 代码截图: code screenShots 先选中代码,按 ctrl shift alt a,就可截取选中的代码颜色注释: comments highlighter 对注释的文字改变颜色高亮成对符号: h…...
clang:在 Win10 上编译 MIDI 音乐程序(二)
先从 Microsoft C Build Tools - Visual Studio 下载 1.73GB 安装 "Microsoft C Build Tools“ 访问 Swift.org - Download Swift 找到 Windows 10:x86_64 下载 swift-5.10-RELEASE-windows10.exe 大约490MB 建议安装在 D:\Swift\ ,安装后大约占…...
【redis】Redis数据类型(三)List类型
目录 List类型介绍特点 List数据结构附:3.2以前的版本(介绍一下压缩列表和双向链表)压缩列表ZipList双向链表LinkedList 常用命令lpush示例 lpushx示例 rpush示例 rpushx示例 LPOP示例 RPOP示例 BLPOP非阻塞行为阻塞行为相同的 key 被多个客户端同时阻塞在 MULTI/EX…...
Java面试题:多线程2
如何停止正在运行的线程 1,使用退出标志,使线程正常退出(run方法中循环对退出标志进行判断) 2,使用stop()方法强行终止(不推荐) 3,调用interrupt()方法中断线程 打断阻塞线程(sleep,wait,join),线程会抛出InterruptedException异常 打断正常的线程,可以根据打断状态来标记…...
T型槽地轨承载力是如何连接整个制造过程的强力桥梁(北重公司设计)
T型槽地轨承载力的定义和计算 T型槽地轨是一种用于工业设备运输和装配的关键组件。它由世界上各行各业的生产商广泛采用,其有效的承载力使其成为连接整个制造过程的强力桥梁。本文将介绍T型槽地轨的承载力以及相关的设计要点和应用。 承载力的定义和计算 承载力是…...
【Numpy】一文向您详细介绍 np.linspace()
【Numpy】一文向您详细介绍 np.linspace() 🌈 欢迎莅临我的个人主页👈 这里是我静心耕耘深度学习领域、真诚分享知识与智慧的小天地!🎇 🎓 博主简介:985高校的计算机专业人士,热衷于分享技术见…...
VMware虚拟网卡网络适配器出现黄色感叹号
问题发生:VMware在使用Ubuntu的过程中突然卡死,强制关闭开启后就发生了网络无法连接 找到电脑的设备管理发现VMware的适配器出现黄色感叹号 解决方法: 下载软件ccleaner 扫描问题,懒得去找就修复了所有的问题 最后发现适配器…...
论生命价值
我们该如何定义一个人的生命价值,这是一个十分值得我们深思的问题,而谈论到生命的价值,我们先从非人的东西去谈论它的价值,从我们作为人的角度去思考价值,一个东西对我们有用,这个东西能够让我们的主观上的…...
基于Springboot的民航网上订票系统(有报告)。Javaee项目,springboot项目。
演示视频: 基于Springboot的民航网上订票系统(有报告)。Javaee项目,springboot项目。 项目介绍: 采用M(model)V(view)C(controller)三层体系结构…...
ubuntu开启message文件
环境:ubuntu 20.04 1、首先需要修改 /etc/rsyslog.d/50-default.conf 文件;源文件中message被注释,如下图: 2、打开注释: 3、重启服务 systemctl restart rsyslog.service 如此即可!...
ISIS的基本概念
1.ISIS概述 IS-IS是一种链路状态路由协议,IS-IS与OSPF在许多方面非常相似, 例如运行IS-IS协议的直连设备之间通过发送Hello报文发现彼此,然后建立邻接关系,并交互链路状态信息。 CLNS由以下三个部分组成: CLNP…...
Vue 工程化开发入门
Vue开发的两种方式: 核心包传统开发模式:基于html/css/js文件,直接引入核心包,开发Vue工程化开发模式:基于构建工具的环境中开发Vue 这里选择Vue cli脚手架 进行开发,搜索教程自行下载。 组件化开发 一个页…...
车牌号识别系统:PyQT5+QT Designe+crnn/PaddleOCR+YOLO+OpenCV矫正算法。
PyQT5&QT Designecrnn/PaddleOCRYOLO传统OpenCV矫正算法。可视化的车牌识别系统项目。 车牌号识别系统 项目绪论1.项目展示2.视频展示3.整体思路 一、PyQT5 和 QT Designer1.简介2.安装3.使用 二、YOLO检测算法三、OpenCV矫正算法四、crnn/PaddleOCR字符识别算法五、QT界面…...
【基于MAX98357的Minimax(百度)长文本语音合成TTS 接入教程】
【基于MAX98357的Minimax(百度)长文本语音合成TTS 接入教程】 1. 前言2. 先决条件2.1 硬件准备2.2 软件准备2.3 接线 3. 核心代码3.1 驱动实现3.2 代码解析 4. 播放文本5. 结论 视频地址: SeeedXIAO ESP32S3 Sense【基于MAX98357的Minimax&am…...
秋招后端开发面试题 - JVM底层原理
目录 JVM底层原理前言面试题Java 对象的创建过程?什么是指针碰撞?什么是空闲列表?/ 内存分配的两种方式?JVM 里 new 对象时,堆会发生抢占吗?JVM 是怎么设计来保证线程安全的?/ 内存分配并发问题…...
VUE2从入门到精通(一)
**************************************************************************************************************************************************************************** 1、课程概述 【1】前置储备:HTMLCSSJS、WebAPI、Ajax、Node.js 【2】1天&…...
cmake进阶:文件操作之写文件
一. 简介 cmake 提供了 file() 命令可对文件进行一系列操作,譬如读写文件、删除文件、文件重命名、拷贝文件、创建目录等等。 接下来 学习这个功能强大的 file() 命令。 本文学习 CMakeLists.txt语法中写文件操作。 二. cmake进阶:文件操作之写文件…...
ubuntu 安装单节点HBase
下载HBase mkdir -p /home/ellis/HBase/ cd /home/ellis/HBase/ wget https://downloads.apache.org/hbase/2.5.8/hbase-2.5.8-bin.tar.gz tar -xvf hbase-2.5.8-bin.tar.gz安装java jdk sudo apt install openjdk-11-jdksudo vim /etc/profileexport JAVA_HOME/usr/lib/jvm/…...
HTTP 多个版本
了解一下各个版本的HTTP。 上个世纪90年代初期,蒂姆伯纳斯-李(Tim Berners-Lee)及其 CERN的团队共同努力,制定了互联网的基础,定义了互联网的四个构建模块: 超文本文档格式(HTML) …...
【DevOps】探索Linux命令行世界:深入了解Shell的力量
目录 一、Linux Shell 详细介绍 1. Shell基础概念 2. Shell的功能特性 3. 常用Shell命令与技巧 4. 高级Shell特性与实践 二、常见的Shell及其比较 1. Bash (Bourne Again SHell) 2. Zsh (Z Shell) 3. Fish (Friendly Interactive SHell) 4. Ksh (Korn SHell) 5. Csh …...
武汉哪里做网站/电商网站设计论文
//Arduino Mega328p. #ifdef CPU_MAP_ATMEGA328P // (Arduino Uno) //串口中断向量 #define SERIAL_RX USART_RX_vect #define SERIAL_UDRE USART_UDRE_vect // 步进电机脉冲端口,所有步进端口必须在一个通道里. #define STEP_DDR DDRD #define STEP_…...
如何进入网站后台地址/网址收录网站
计算机应用基础 说课 CPU与内存 甘肃钢铁职业技术学院王鑫 目录 一 教学分析二 教学改革与创新三 教学任务目标四 教学重点和难点五 教学方法六 教学资源配备七 教学过程 一 教学分析 1 教材内容分析微型计算机硬件系统的组成 是教材第一章基础知识部分的重点章节 该章节教材的…...
长沙营销型网页制作公司/网站自然优化
题意:有n张卡片,每张上的值可以相同,每张上的值不超过m,第n1张为m。设k[i]为任意整数,a[i]为第i张卡片的值,那么问∑k[i]*a[i]1的a[i]有多少种(0<i<n)。 有式子可得n1个数线性无关,即最大…...
做婚纱影楼网站的价格/十大软件免费下载网站排行榜
一、数值运算与运算符:思考引入:[rootlocalhost sh]# aa11[rootlocalhost sh]# bb22[rootlocalhost sh]# cc$aa$bb[rootlocalhost sh]# echo $cc1122如上:Linux中,shell中的变量类型,都是字符串类型,在此表…...
vb net 做网站/万能搜索
因为FireFox Chrome默认都是有一个值传进来的,所以这里是对IE和FireFox Chrome做了兼容。 例如:页面点击事件事件要使用document,获取鼠标位置 document.onclinkfunction(ev) { var oEventev||event; //兼容IE和FireFox Chrome 只要一个为…...
做网站都得会什么技术/万网注册域名查询
Abstract 单图像雾霾去除是一个具有挑战性的不适定问题。现有的方法使用各种约束/先验来获得似是而非的去雾解。实现雾霾去除的关键是对输入的雾霾图像进行介质透射图的估计。在本文中,我们提出了一个可训练的端到端系统称为DehazeNet,用于介质传输估计…...