海智算法训练营第三十四天 | 第八章 贪心算法 part04 | ● 860.柠檬水找零 ● 406.根据身高重建队列 ● 452. 用最少数量的箭引爆气球

本文主要是介绍海智算法训练营第三十四天 | 第八章 贪心算法 part04 | ● 860.柠檬水找零 ● 406.根据身高重建队列 ● 452. 用最少数量的箭引爆气球,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 今日任务:

1.贪心算法找零

2.双维度问题解法

3.判断重叠区间问题

1.贪心算法找零

力扣题目链接

这道题较简单,就是分清情况区别对待就ok了

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

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


class Solution {public boolean lemonadeChange(int[] bills) {int five = 0 , ten = 0;for(int temp : bills){if(temp == 5)   five++;else if(temp == 10){if (five < 1)   return false;five--;ten++;}else {if(five > 0 && ten > 0){five--;ten--;} else if (five >= 3){five-=3;}else return false;}}return true;}
}

2.双维度问题解法

力扣题目链接

遇到两个维度的问题的时候一定要先确定一个维度再确定另外一个维度

按照身高h来排序呢,身高一定是从大到小排(身高相同的话则k小的站前面),让高个子在前面。

此时我们可以确定一个维度了,就是身高,前面的节点一定都比本节点高!

那么只需要按照k为下标重新插入队列就可以了,为什么呢?

看图:

先以身高维度排序,再按照题目位置条件调整位置,因为排序后的前面比你高的数是固定的,所以移动不会影响到其他的位置上的数。

class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people , (o1,o2)->o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);LinkedList<int[]> que = new LinkedList<>();for(int[] p : people){que.add(p[1] , p);}return que.toArray(new int[people.length][people.length]);}
}

3.判断重叠区间问题

力扣题目链接c 

class Solution {public int findMinArrowShots(int[][] points) {Arrays.sort(points , (o1,o2) -> Integer.compare(o1[0],o2[0]));int count = 1 ;//初始至少有一支箭for (int i = 1; i < points.length; i++) {if(points[i][0] > points[i-1][1])   count++;else{points[i][1] = Math.min(points[i-1][1] , points[i][1]);}}return count;}
}

此题的关键就在于如何简单理解,先把区间按照左边界排序,这时候就分以下几种情况:

1.区间的左边界比上个区间的右边界要大,这时候两区间不重叠至少加一箭

2.区间的左边界小于等于上个区间的右边界,这时候需要更新当前区间的右边界,选择重叠区间中更小的右边界,因为这样区间更大的以及包含住了区间更小的,所以下个区间要是小于这个右边界,那么理所当然和上上个边界也是重合的。

 

学习时长:2h

总结:此次的学习到了关于双维度、区间重叠的贪心做法,从局部到全局,对此类的题型更加熟悉

这篇关于海智算法训练营第三十四天 | 第八章 贪心算法 part04 | ● 860.柠檬水找零 ● 406.根据身高重建队列 ● 452. 用最少数量的箭引爆气球的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

SpringKafka错误处理(重试机制与死信队列)

《SpringKafka错误处理(重试机制与死信队列)》SpringKafka提供了全面的错误处理机制,通过灵活的重试策略和死信队列处理,下面就来介绍一下,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、Spring Kafka错误处理基础二、配置重试机制三、死信队列实现四、特定异常的处理策略五

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

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实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为