算法打卡day30|贪心算法篇04|Leetcode 860.柠檬水找零、406.根据身高重建队列、452. 用最少数量的箭引爆气球

本文主要是介绍算法打卡day30|贪心算法篇04|Leetcode 860.柠檬水找零、406.根据身高重建队列、452. 用最少数量的箭引爆气球,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

算法题

Leetcode 860.柠檬水找零

题目链接:860.柠檬水找零

 大佬视频讲解:柠檬水找零视频讲解

 个人思路

5元最通用,然后是10元,所以如果是对于20元找零直接先找10元,也涉及到贪心的思想,可以用贪心算法。

解法
贪心法

对于找零分为三种情况

  • 情况一:账单是5,直接收下。
  • 情况二:账单是10,消耗一个5,增加一个10
  • 情况三:账单是20,优先消耗一个10和一个5,如果不够,再消耗三个5

局部最优:遇到账单20,优先消耗美元10,完成本次找零。全局最优:完成全部账单的找零。

class Solution {public boolean lemonadeChange(int[] bills) {int five = 0;//五元数量int ten = 0;//十元数量for (int i = 0; i < bills.length; i++) {if (bills[i] == 5) {five++;} else if (bills[i] == 10) {five--;ten++;} else if (bills[i] == 20) {if (ten > 0) {//先消耗十元ten--;five--;} else {five -= 3;}}if (five < 0 || ten < 0) return false;//遍历完如果不够找零就返回false}return true;}
}

时间复杂度:O(n);(遍历数组)

空间复杂度:O(1);(两个变量-常量级)


 Leetcode  406.根据身高重建队列

题目链接:406.根据身高重建队列

大佬视频讲解:根据身高重建队列视频讲解

个人思路

这道题与昨天的分发糖果有些像,都是需要分开考虑两个维度,要先确定一个维度,再确定另一个维度

解法
贪心法

可以先手动模拟一遍,发现只能先按照身高排序,因为前面的节点一定都比本节点高!排序之后,优先按身高高的people的k来插入,后序插入节点也不会影响前面已经插入的节点,最终按照k的规则完成了队列。

按照题目所给例子做个示范:people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]],整个插入过程如下:

排序完的people: [[7,0], [7,1], [6,1], [5,0], [5,2],[4,4]]

插入的过程:

  • 插入[7,0]:[[7,0]]
  • 插入[7,1]:[[7,0],[7,1]]
  • 插入[6,1]:[[7,0],[6,1],[7,1]]
  • 插入[5,0]:[[5,0],[7,0],[6,1],[7,1]]
  • 插入[5,2]:[[5,0],[7,0],[5,2],[6,1],[7,1]]
  • 插入[4,4]:[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

class Solution {public int[][] reconstructQueue(int[][] people) {// 身高从大到小排(身高相同时 k小的站前面)Arrays.sort(people, (a, b) -> {// a - b 是升序排列,故在a[0] == b[0]的状况下,会根据k值升序排列if (a[0] == b[0]) return a[1] - b[1];   //b - a 是降序排列,在a[0] != b[0],的状况会根据h值降序排列return b[0] - a[0];   });LinkedList<int[]> que = new LinkedList<>();for (int[] p : people) {que.add(p[1],p);   //将value插入到指定index里。}return que.toArray(new int[people.length][]);}
}

时间复杂度:O(n log n);(排序操作)

空间复杂度:O(n);(用LinkedList 来存储元素)


 Leetcode  452. 用最少数量的箭引爆气球

题目链接:452. 用最少数量的箭引爆气球

大佬视频讲解:用最少数量的箭引爆气球视频讲解

 个人思路

如何计算重叠区间呢,重叠区间是删除还是跳过,根据左边界还是右边界呢 思路不清晰...

解法
贪心法

局部最优:当气球出现重叠,一起射,所用弓箭最少。全局最优:把所有气球射爆所用弓箭最少。

求边界问题,为了让气球尽可能的重叠,需要对数组进行排序,排序之后,从前到后遍历气球,被射过的气球仅仅跳过就行了,再记录一下箭的数量。

按照气球起始位置排序,还是按照气球终止位置排序 都可以,这里按照起始位置排序

如果遇到气球重叠了,重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。.

以题目示例: [[10,16],[2,8],[1,6],[7,12]]为例,如图:(方便起见,已经排序)

如上图,首先第一组重叠气球,一定是需要一个箭,气球3,的左边界大于了 第一组重叠气球的最小右边界,所以再需要一支箭来射气球3。

class Solution {public int findMinArrowShots(int[][] points) {// 根据气球直径的开始坐标从小到大排序Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0])); int count = 1;  // points 不为空时,至少需要一支箭for (int i = 1; i < points.length; i++) {if (points[i][0] > points[i - 1][1]) {  // 气球i和气球i-1不挨着,不能加=count++; // 需要一支箭} else {  // 更新重叠气球最小右边界points[i][1] = Math.min(points[i][1], points[i - 1][1]);}}return count;}
}

时间复杂度:O(n logN);(排序数组)

空间复杂度:O( logN);(java所使用的内置函数用的是快速排序需要 logN 的空间)


 以上是个人的思考反思与总结,若只想根据系列题刷,参考卡哥的网址代码随想录算法官网

这篇关于算法打卡day30|贪心算法篇04|Leetcode 860.柠檬水找零、406.根据身高重建队列、452. 用最少数量的箭引爆气球的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/856364

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Spring Boot整合消息队列RabbitMQ的实现示例

《SpringBoot整合消息队列RabbitMQ的实现示例》本文主要介绍了SpringBoot整合消息队列RabbitMQ的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录RabbitMQ 简介与安装1. RabbitMQ 简介2. RabbitMQ 安装Spring

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque

解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)

《解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)》该文章介绍了使用Redis的阻塞队列和Stream流的消息队列来优化秒杀系统的方案,通过将秒杀流程拆分为两条流水线,使用Redi... 目录Redis秒杀优化方案(阻塞队列+Stream流的消息队列)什么是消息队列?消费者组的工作方式每

Redis延迟队列的实现示例

《Redis延迟队列的实现示例》Redis延迟队列是一种使用Redis实现的消息队列,本文主要介绍了Redis延迟队列的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录一、什么是 Redis 延迟队列二、实现原理三、Java 代码示例四、注意事项五、使用 Redi

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1