【代码随想录算法训练营Day34】860.柠檬水找零;406.根据身高重建队列;452.用最少数量的箭引爆气球

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

❇️Day 34 第八章 贪心算法 part04

✴️今日任务

  • 860.柠檬水找零
  • 406.根据身高重建队列
  • 452.用最少数量的箭引爆气球

❇️860.柠檬水找零

  • 本题看上好像挺难,其实挺简单的,大家先尝试自己做一做。
  • 题目链接:https://leetcode.cn/problems/lemonade-change/
  • 视频讲解:https://www.bilibili.com/video/BV12x4y1j7DD
  • 文章链接:https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html

自己的思路

利用switch case语句判断

自己的代码(✅通过100%)

踩坑:

  • switch的case需要用break不然会一直执行剩下的case
public boolean lemonadeChange(int[] bills) {int count5 = 0;int count10 = 0;for (int i = 0; i < bills.length; i++) {switch (bills[i]){case 5:count5 ++;break;case 10:count10 ++;if(count5 > 0) count5--;else return false;break;case 20:if(count10 > 0 && count5 > 0){count10 --;count5 --;}else if(count5 >= 3){count5 -= 3;}else{return false;}break;}}return true;
}

随想录思路

和我的基本一样只是换成if-else

随想录代码

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;}return true;
}

❇️406.根据身高重建队列

  • 本题有点难度,和分发糖果类似,不要两头兼顾,处理好一边再处理另一边。
  • 题目链接:https://leetcode.cn/problems/queue-reconstruction-by-height/
  • 视频讲解:https://www.bilibili.com/video/BV1EA411675Y
  • 文章链接:https://programmercarl.com/0406.%E6%A0%B9%E6%8D%AE%E8%BA%AB%E9%AB%98%E9%87%8D%E5%BB%BA%E9%98%9F%E5%88%97.html

自己的思路

先以ki排序然后再通过hi插入
难点:不会对二维数组进行排序

随想录思路

思路一样

  1. 按照k为下标重新插入队列就可以了,以图中{5,2} 为例:
    [图片]

  2. 在按照身高从大到小排序后:

  • 局部最优:优先按身高高的people的k来插入。插入操作过后的people满足队列属性
  • 全局最优:最后都做完插入操作,整个队列满足题目队列属性
  1. 整个插入过程如下:
    排序完的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) -> {if (a[0] == b[0]) return a[1] - b[1];   // a - b 是升序排列,故在a[0] == b[0]的狀況下,會根據k值升序排列return b[0] - a[0];   //b - a 是降序排列,在a[0] != b[0],的狀況会根据h值降序排列});LinkedList<int[]> que = new LinkedList<>();for (int[] p : people) {que.add(p[1],p);   //Linkedlist.add(index, value),会將value插入到指定index里。}return que.toArray(new int[people.length][]);}
}

二维数组排序

  • 四个方法
    1. sort(T[] a):对指定数组进行升序排列。
    2. sort(T[] a, int fromIndex, int toIndex):对指定数组的指定范围升序排列。
    3. sort(T[] a, Comparator<? supre T> c): 根据指定比较器产生的顺序对指定对象数组进行排序。
    4. sort(T[] a, int fromIndex, int toIndex, Comparator<? supre T> c): 根据指定比较器产生的顺序对指定对象数组的指定范围进行排序。
  • 二维数组按照第一维数组排序
int[][] nums=new int[][]{{1,3},{1,2},{5,1},{4,5},{3,3}};
//方法一,使用比较器
Arrays.sort(nums,new Comparator<int[]>(){@Overridepublic int compare(int[] a,int[] b){// 当第一维相等时比较第二维的if(a[0] == b[0]){return a[1]-b[1];}else{return a[0]-b[0];}}
});// 方法二,使用 lambda 表达式
Arrays.sort(nums,(a,b) -> a[0] == b[0] ? a[1]-b[1] : a[0]-b[0]);
for (int[] num : nums) {System.out.print(Arrays.toString(num));
}
// 结果 : [1, 2][1, 3][3, 3][4, 5][5, 1] 
  • 二维数组按照第二维数组排序
int[][] nums=new int[][]{{1,3},{1,2},{5,1},{4,5},{3,3}};
//方法一
Arrays.sort(nums,new Comparator<int[]>(){@Overridepublic int compare(int[] a,int[] b){// 当第二维相等时比较第一维的if(a[1] == b[1]){return a[0]-b[0];}else{return a[1]-b[1];}}
});// 方法二,使用 lambda 表达式
Arrays.sort(nums,(a,b) -> a[1] == b[1]  ? a[0]-b[0] : a[1]-b[1]);
for (int[] num : nums) {System.out.print(Arrays.toString(num));
}
// 结果 : [5, 1][1, 2][1, 3][3, 3][4, 5]

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

  • 本题是一道 重叠区间的题目,好好做一做,因为明天三道题目,都是 重叠区间。
  • 题目链接:https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/
  • 视频讲解:https://www.bilibili.com/video/BV1SA41167xe
  • 文章链接:https://programmercarl.com/0452.%E7%94%A8%E6%9C%80%E5%B0%91%E6%95%B0%E9%87%8F%E7%9A%84%E7%AE%AD%E5%BC%95%E7%88%86%E6%B0%94%E7%90%83.html

自己的思路

就是一个取交集的问题

  1. 先对二维数组进行排序(根据第一个数字)
  2. 然后选定第一个范围的右区间A,看后面有几个(n)范围的左区间小于等于A,即可以一下扎破n+1个气球
  3. 然后再从第n+2个范围开始判断

自己的代码(✅通过84.56%)

踩坑:
用lambda表达式会溢出,排不了序,必须使用比较器

public static int findMinArrowShots(int[][] points) {if(points.length == 1) return 1;int count = 1;Arrays.sort(points, new Comparator<int[]>() {@Overridepublic int compare(int[] points1, int[] points2) {//要升序排序,本来习惯写类似于 return o1.val - o2.val 来实现,这里由于样例中有出现//[[-2147483646,-2147483645],[2147483646,2147483647]] 这样的例子,加减法会溢出,所以只能通过比较来实现if (points1[1] > points2[1]) {return 1;} else if (points1[1] < points2[1]) {return -1;}return 0;}});for(int[] i : points) System.out.println(Arrays.toString(i));int end = 0; //被取右区间的范围下标int start = 1; //被取左区间的下标while(start < points.length){System.out.println("次数:"+count);//重叠if(points[start][0] <= points[end][1]){System.out.println("气球{"+points[start][0]+", "+points[start][1]+"}可同时和气球{"+points[end][0]+", "+points[end][1]+"}一起被扎破");}else{end = start;count ++;}start ++;}return count;
}

随想录思路

为了让气球尽可能的重叠,需要对数组进行排序。
如果气球重叠了,重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。
[图片]

随想录代码

/*** 时间复杂度 : O(NlogN)  排序需要 O(NlogN) 的复杂度* 空间复杂度 : O(logN) java所使用的内置函数用的是快速排序需要 logN 的空间*/
class Solution {public int findMinArrowShots(int[][] points) {// 根据气球直径的开始坐标从小到大排序// 使用Integer内置比较方法,不会溢出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 {  // 气球i和气球i-1挨着points[i][1] = Math.min(points[i][1], points[i - 1][1]); // 更新重叠气球最小右边界}}return count;}
}

这篇关于【代码随想录算法训练营Day34】860.柠檬水找零;406.根据身高重建队列;452.用最少数量的箭引爆气球的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

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

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

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

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

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

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

Java强制转化示例代码详解

《Java强制转化示例代码详解》:本文主要介绍Java编程语言中的类型转换,包括基本类型之间的强制类型转换和引用类型的强制类型转换,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录引入基本类型强制转换1.数字之间2.数字字符之间引入引用类型的强制转换总结引入在Java编程语言中,类型转换(无论

Vue 调用摄像头扫描条码功能实现代码

《Vue调用摄像头扫描条码功能实现代码》本文介绍了如何使用Vue.js和jsQR库来实现调用摄像头并扫描条码的功能,通过安装依赖、获取摄像头视频流、解析条码等步骤,实现了从开始扫描到停止扫描的完整流... 目录实现步骤:代码实现1. 安装依赖2. vue 页面代码功能说明注意事项以下是一个基于 Vue.js

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu