【力扣一刷】代码随想录day35(贪心算法part4:860.柠檬水找零、406.根据身高重建队列、452. 用最少数量的箭引爆气球 )

本文主要是介绍【力扣一刷】代码随想录day35(贪心算法part4:860.柠檬水找零、406.根据身高重建队列、452. 用最少数量的箭引爆气球 ),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

【860.柠檬水找零】简单题(很简单)

【406.根据身高重建队列】中等题(掌握思路后简单)

【452. 用最少数量的箭引爆气球】中等题


【860.柠檬水找零】简单题(很简单)

思路:

  • 5元的直接收,不需要找钱
  • 10元的只需要找5元
  • 20元的优先找10元,没有10元再全部找5元
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){if (five >= 1){five--;ten++;}else return false;}else{// 如果是付了20,则需要找15元,优先找10元if (ten >= 1 && five >= 1){ten--; // 10元1张five--; // 5元1张}else if (five >= 3){five -= 3; // 5元3张}else return false;}}return true;}
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)


【406.根据身高重建队列】中等题(掌握思路后简单)

思路:先按身高 h 从大到小排序,再依照 k 调整顺序

关键:按照身高降序排序后,即使将后面的数组调整到前面,也不会影响前面的 k ,因为前面的肯定比后面的高。

示例:

class Solution {public int[][] reconstructQueue(int[][] people) {// 先按身高h降序排序,身高相同的情况下,按k升序排序Arrays.sort(people, (o1, o2) -> {int res = Integer.compare(o2[0], o1[0]); // h降序if (res != 0) return res;else return Integer.compare(o1[1], o2[1]); // k升序});// 频繁按索引插入,LinkedList(基于链表)的效率高于ArrayList(基于数组)List<int[]> list = new LinkedList<>(); for (int i = 0; i < people.length; i++){list.add(people[i][1], people[i]);  // 按照k调整,相当于从左到右按k为索引在链表中插入对应数组}return list.toArray(new int[people.length][]); // 链表 -> 数组,返回数组,注意要指定数组的类型和长度}
}
  • 时间复杂度: O(nlogn),快速排序
  • 空间复杂度: O(n),额外的链表空间消耗

总结:

1、排序需要重写compare方法,先按身高h降序排序,身高相同的情况下,再按k升序排序

2、调整顺序如果用ArrayList实现,时间复杂度会偏高,最好用LinkedList,而且要想到按k调整顺序相当于按k为索引,依次将people排序后的各个数组插入链表。

3、链表转换为数组的时候,注意toArray()方法默认返回的是Object[]型数组,需要在参数列表中用构造器指定数组的类型和长度。


【452. 用最少数量的箭引爆气球】中等题(偏简单)

思路:

1、按气球的起始位置(左边界)排序

2、使用变量shoot记录上一支箭的范围,判断当前遍历的气球范围是否与上一支箭的范围存在重叠区域:

  • 不存在重叠区域:需要增加一支箭,shoot更新为当前遍历的气球范围。
  • 存在重叠区域:不需要增加箭,只更新shoot的范围,起始位置不变,结束位置取上一个shoot的结束位置和当前遍历气球的结束位置的最小值。
class Solution {public int findMinArrowShots(int[][] points) {Arrays.sort(points, (o1, o2) -> Integer.compare(o1[0], o2[0]));int[] shoot = points[0]; // 用于记录上一次射箭的范围int res = 1; // 至少有一个气球,至少射1支箭,初始化为1for (int i = 1; i < points.length; i++){// 必然成立shoot[0] < point[0]int[] point = points[i];// 当前遍历的气球不在上一支箭的范围内,需要多加一支箭,并更新射箭的范围if (shoot[1] < point[0]){res++;shoot = point;}// 当前遍历的气球在上一支箭的范围内,需继续用上一支箭即可,缩窄上一支箭的范围else {shoot[0] = point[0];shoot[1] = Math.min(shoot[1], point[1]);}}return res;}
}

  • 时间复杂度: O(nlogn),快速排序
  • 空间复杂度: O(1)

这篇关于【力扣一刷】代码随想录day35(贪心算法part4:860.柠檬水找零、406.根据身高重建队列、452. 用最少数量的箭引爆气球 )的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java调用DeepSeek API的最佳实践及详细代码示例

《Java调用DeepSeekAPI的最佳实践及详细代码示例》:本文主要介绍如何使用Java调用DeepSeekAPI,包括获取API密钥、添加HTTP客户端依赖、创建HTTP请求、处理响应、... 目录1. 获取API密钥2. 添加HTTP客户端依赖3. 创建HTTP请求4. 处理响应5. 错误处理6.

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

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

使用 sql-research-assistant进行 SQL 数据库研究的实战指南(代码实现演示)

《使用sql-research-assistant进行SQL数据库研究的实战指南(代码实现演示)》本文介绍了sql-research-assistant工具,该工具基于LangChain框架,集... 目录技术背景介绍核心原理解析代码实现演示安装和配置项目集成LangSmith 配置(可选)启动服务应用场景

Python中顺序结构和循环结构示例代码

《Python中顺序结构和循环结构示例代码》:本文主要介绍Python中的条件语句和循环语句,条件语句用于根据条件执行不同的代码块,循环语句用于重复执行一段代码,文章还详细说明了range函数的使... 目录一、条件语句(1)条件语句的定义(2)条件语句的语法(a)单分支 if(b)双分支 if-else(

MySQL数据库函数之JSON_EXTRACT示例代码

《MySQL数据库函数之JSON_EXTRACT示例代码》:本文主要介绍MySQL数据库函数之JSON_EXTRACT的相关资料,JSON_EXTRACT()函数用于从JSON文档中提取值,支持对... 目录前言基本语法路径表达式示例示例 1: 提取简单值示例 2: 提取嵌套值示例 3: 提取数组中的值注意

CSS3中使用flex和grid实现等高元素布局的示例代码

《CSS3中使用flex和grid实现等高元素布局的示例代码》:本文主要介绍了使用CSS3中的Flexbox和Grid布局实现等高元素布局的方法,通过简单的两列实现、每行放置3列以及全部代码的展示,展示了这两种布局方式的实现细节和效果,详细内容请阅读本文,希望能对你有所帮助... 过往的实现方法是使用浮动加

JAVA调用Deepseek的api完成基本对话简单代码示例

《JAVA调用Deepseek的api完成基本对话简单代码示例》:本文主要介绍JAVA调用Deepseek的api完成基本对话的相关资料,文中详细讲解了如何获取DeepSeekAPI密钥、添加H... 获取API密钥首先,从DeepSeek平台获取API密钥,用于身份验证。添加HTTP客户端依赖使用Jav

Java实现状态模式的示例代码

《Java实现状态模式的示例代码》状态模式是一种行为型设计模式,允许对象根据其内部状态改变行为,本文主要介绍了Java实现状态模式的示例代码,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来... 目录一、简介1、定义2、状态模式的结构二、Java实现案例1、电灯开关状态案例2、番茄工作法状态案例

nginx-rtmp-module模块实现视频点播的示例代码

《nginx-rtmp-module模块实现视频点播的示例代码》本文主要介绍了nginx-rtmp-module模块实现视频点播,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录预置条件Nginx点播基本配置点播远程文件指定多个播放位置参考预置条件配置点播服务器 192.

CSS自定义浏览器滚动条样式完整代码

《CSS自定义浏览器滚动条样式完整代码》:本文主要介绍了如何使用CSS自定义浏览器滚动条的样式,包括隐藏滚动条的角落、设置滚动条的基本样式、轨道样式和滑块样式,并提供了完整的CSS代码示例,通过这些技巧,你可以为你的网站添加个性化的滚动条样式,从而提升用户体验,详细内容请阅读本文,希望能对你有所帮助...