【代码随想录算法训练营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;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/269227.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

即时设计-高效易用的界面工具

界面工具是设计师的得力助手&#xff0c;为设计师快速创建精美易用的用户界面提供了丰富的功能和直观的界面。在众多的界面工具中&#xff0c;有的支持预设模板、图标库和样式库&#xff0c;有的更注重原型和互动。如何选择优秀的界面工具&#xff1f;这里有一个高效易用的界面…

python并发 map函数的妙用

1.map是什么&#xff1f; map函数是Python中的一个内置函数&#xff0c;用于将一个函数应用到一个或多个可迭代对象的每个元素上&#xff0c;生成一个新的可迭代对象。它的一般形式是&#xff1a; map(function, iterable1, iterable2, ...)其中&#xff0c;function是一个函…

JS逆向进阶篇【去哪儿旅行登录】【下篇-逆向Bella参数JS加密逻辑Python生成】

目录&#xff1a; 每篇前言&#xff1a;引子——本篇目的1、 代码混淆和还原&#xff08;1&#xff09;单独替换&#xff1a;&#xff08;2&#xff09;整个js文件替换&#xff1a; 2、算法入口分析3、 深入分析&#xff08;0&#xff09;整体分析&#xff1a;&#xff08;1&am…

STM32启动过程及反汇编

STM32从Flash启动的过程&#xff0c;主要是从上电复位到main函数的过程&#xff0c;主要有以下步骤&#xff1a; 1.初始化堆栈指针 SP_initial_sp&#xff0c;初始化 PC 指针Reset_Handler 2.初始化中断向量表 3.配置系统时钟 4.调用 C 库函数_main 初始化用户堆栈&#xf…

华为配置WLAN高密业务示例

配置WLAN高密业务示例 组网图形 图1 配置高密WLAN环境网络部署组网图 业务需求组网需求数据规划配置思路配置注意事项操作步骤配置文件 业务需求 体育场由于需要接入用户数量很大&#xff0c;AP间部署距离较小&#xff0c;因此AP间的干扰较大&#xff0c;可能导致用户上网网…

Qt 中Qwidget相关属性

文章目录 1. QWidget 核心属性1.1 enabled1.2 geometry1.2.1 window frame 的影响 1.3 windowTitle1.4 windowIcon1.4.1 qrc的使用 1.5 windowOpacity1.6 cursor1.7 focusPolicy1.8 styleSheet 1. QWidget 核心属性 在 Qt 中, 使⽤ QWidget 类表⽰ “控件”. 像按钮, 视图, 输…

Shell管道和过滤器

一、Shell管道 Shell 还有一种功能&#xff0c;就是可以将两个或者多个命令&#xff08;程序或者进程&#xff09;连接到一起&#xff0c;把一个命令的输出作为下一个命令的输入&#xff0c;以这种方式连接的两个或者多个命令就形成了管道&#xff08;pipe&#xff09;。 重定…

应用方案 | D722 9MHz,轨对轨I/O CMOS运放,低噪声、低电压、低功耗运放,应用广泛

D722是低噪声、低电压、低功耗运放&#xff0c;应用广泛。D722具有9MHz的高增益带宽积&#xff0c;转换速率为8.5V/μs&#xff0c;静态电流为1.7mA&#xff08;5V电源电压&#xff09;。 D722具有低电压、低噪声的特点&#xff0c;并提供轨到轨输出能力&#xff0c;D722的最大…

Shell编程——条件测试(五)

在shell编程中&#xff0c;if语句本身不执行任何判断&#xff0c;它实际上接受一个程序作为参数&#xff0c;然后执行这个程序&#xff0c;并依据这个程序的返回值来判断是否执行相应的语句。 程序的返回值是0&#xff0c;则为真&#xff0c;反之则为假。 目录 test命令&…

SpringCloud搭建微服务之Consul服务注册与发现

1. Consul介绍 Consul是由HashiCorp公司使用Go语言开发的一款开源工具&#xff0c;主要用于实现分布式系统的服务发现和服务配置&#xff0c;其内置了服务注册与发现框架、分布式一致性协议实现、健康检查、Key-Value存储、多数据中心方案。Consul具有高可移植性&#xff0c;支…

《Redis 设计与实现》读书概要

注&#xff1a; 《Redis 设计与实现》一书基于 Redis 2.9 版本编写&#xff0c;部分内容已过时&#xff0c;过时之处本文会有所说明。本文为读书笔记&#xff0c;部分简单和日常使用较少的知识点未记录。原书网页版地址 https://redisbook.com/ 一、底层数据结构 SDS(Simple Dy…

654.最大二叉树

这段Java代码实现了一个名为Solution的类&#xff0c;其中包含两个方法&#xff1a;constructMaximumBinaryTree()和constructMaximumBinaryTree1()&#xff0c;目的是从给定的整数数组nums中构建出一个最大二叉树。以下是详细的注释说明&#xff1a; class Solution {// 主方…

某品零食交易平台设计与实现|基于springboot+ Mysql+Java的某品交易平台设计与实现(源码+数据库+文档+PPT)

目录 基于springboot MysqlJava的某品交易平台设计与实现 摘 要 系统详细设计 数据库设计 论文参考 源码获取 文末获取源码联系 基于springboot MysqlJava的某品交易平台设计与实现 摘 要 随着科学技术的飞速发展&#xff0c;社会的方方面面、各行各业都在努力与现代的…

利用excel文件增量同步一个库的数据并自动校正两端数据库条数不一致

利用excel文件增量同步一个库的数据并自动校正两端数据库条数不一致 现在有sqlserver和mysql两个库上的表在进行同步&#xff0c;sqlserver上的是源表&#xff0c;mysql上是目标表。 我们就把sqlserver上的数据同步到mysql上 mysql 是没有数据的。 sqlserver的三个表只是创建了…

240多道!Go开发岗位面试题合集(含答案)

随着今年大环境的影响&#xff0c;找工作的人在今年达到顶峰&#xff0c;马上金九银十面试黄金季&#xff0c;很多人都想在这次面试中拿到心仪Offer。 数以百计的面试&#xff0c;为何迟迟无法顺利入职&#xff1f;能力无疑是至关重要的&#xff0c;可却有不少能力不比已入职的…

未来已来!AI大模型引领科技革命

未来已来&#xff01;AI大模型正以惊人的速度引领着科技革命。随着科技的发展&#xff0c;人工智能在各个领域展现出了非凡的能力和潜力&#xff0c;大模型更是成为了科技领域的明星。从自然语言处理到图像识别&#xff0c;从智能推荐到语音识别&#xff0c;大模型的应用正在改…

Linux-信号3_sigaction、volatile与SIGCHLD

文章目录 前言一、sigaction__sighandler_t sa_handler;__sigset_t sa_mask; 二、volatile关键字三、SIGCHLD方法一方法二 前言 本章内容主要对之前的内容做一些补充。 一、sigaction #include <signal.h> int sigaction(int signum, const struct sigaction *act,struc…

阿里云2核4G服务器支持多少人在线?多少钱?

阿里云2核4G服务器多少钱一年&#xff1f;2核4G5M带宽优惠价格199元一年&#xff0c;轻量应用服务器2核4G4M带宽165元一年&#xff0c;2核4G服务器30元3个月&#xff0c;可以在阿里云官方活动查看2核4G配置详细报价 https://t.aliyun.com/U/bLynLC 阿里云2核4G服务器价格 2核4G…

07. Nginx进阶-Nginx负载均衡

简介 负载均衡 什么是负载均衡&#xff1f; 负载均衡&#xff0c;英文名称为Load Balance&#xff0c;其含义就是指将负载&#xff08;工作任务&#xff09;进行平衡、分摊到多个操作单元上进行运行。 Nginx负载均衡 什么是Nginx负载均衡&#xff1f; Nginx负载均衡可以大…

深度学习算法的基本原理

深度学习是一种机器学习方法&#xff0c;其核心是通过构建深层神经网络来学习数据的表示和特征&#xff0c;以解决各种复杂的任务。以下是深度学习算法的基本原理&#xff0c;希望对大家有所帮助。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xff0c;欢迎…