【力扣一刷】代码随想录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

相关文章

Python实例题之pygame开发打飞机游戏实例代码

《Python实例题之pygame开发打飞机游戏实例代码》对于python的学习者,能够写出一个飞机大战的程序代码,是不是感觉到非常的开心,:本文主要介绍Python实例题之pygame开发打飞机... 目录题目pygame-aircraft-game使用 Pygame 开发的打飞机游戏脚本代码解释初始化部

Java中Map.Entry()含义及方法使用代码

《Java中Map.Entry()含义及方法使用代码》:本文主要介绍Java中Map.Entry()含义及方法使用的相关资料,Map.Entry是Java中Map的静态内部接口,用于表示键值对,其... 目录前言 Map.Entry作用核心方法常见使用场景1. 遍历 Map 的所有键值对2. 直接修改 Ma

Java中常见队列举例详解(非线程安全)

《Java中常见队列举例详解(非线程安全)》队列用于模拟队列这种数据结构,队列通常是指先进先出的容器,:本文主要介绍Java中常见队列(非线程安全)的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录一.队列定义 二.常见接口 三.常见实现类3.1 ArrayDeque3.1.1 实现原理3.1.2

深入解析 Java Future 类及代码示例

《深入解析JavaFuture类及代码示例》JavaFuture是java.util.concurrent包中用于表示异步计算结果的核心接口,下面给大家介绍JavaFuture类及实例代码,感兴... 目录一、Future 类概述二、核心工作机制代码示例执行流程2. 状态机模型3. 核心方法解析行为总结:三

python获取cmd环境变量值的实现代码

《python获取cmd环境变量值的实现代码》:本文主要介绍在Python中获取命令行(cmd)环境变量的值,可以使用标准库中的os模块,需要的朋友可以参考下... 前言全局说明在执行py过程中,总要使用到系统环境变量一、说明1.1 环境:Windows 11 家庭版 24H2 26100.4061

pandas实现数据concat拼接的示例代码

《pandas实现数据concat拼接的示例代码》pandas.concat用于合并DataFrame或Series,本文主要介绍了pandas实现数据concat拼接的示例代码,具有一定的参考价值,... 目录语法示例:使用pandas.concat合并数据默认的concat:参数axis=0,join=

C#代码实现解析WTGPS和BD数据

《C#代码实现解析WTGPS和BD数据》在现代的导航与定位应用中,准确解析GPS和北斗(BD)等卫星定位数据至关重要,本文将使用C#语言实现解析WTGPS和BD数据,需要的可以了解下... 目录一、代码结构概览1. 核心解析方法2. 位置信息解析3. 经纬度转换方法4. 日期和时间戳解析5. 辅助方法二、L

Python使用Code2flow将代码转化为流程图的操作教程

《Python使用Code2flow将代码转化为流程图的操作教程》Code2flow是一款开源工具,能够将代码自动转换为流程图,该工具对于代码审查、调试和理解大型代码库非常有用,在这篇博客中,我们将深... 目录引言1nVflRA、为什么选择 Code2flow?2、安装 Code2flow3、基本功能演示

IIS 7.0 及更高版本中的 FTP 状态代码

《IIS7.0及更高版本中的FTP状态代码》本文介绍IIS7.0中的FTP状态代码,方便大家在使用iis中发现ftp的问题... 简介尝试使用 FTP 访问运行 Internet Information Services (IIS) 7.0 或更高版本的服务器上的内容时,IIS 将返回指示响应状态的数字代

MySQL 添加索引5种方式示例详解(实用sql代码)

《MySQL添加索引5种方式示例详解(实用sql代码)》在MySQL数据库中添加索引可以帮助提高查询性能,尤其是在数据量大的表中,下面给大家分享MySQL添加索引5种方式示例详解(实用sql代码),... 在mysql数据库中添加索引可以帮助提高查询性能,尤其是在数据量大的表中。索引可以在创建表时定义,也可