【代码随想录算法训练营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[]>(){
    @Override
    public 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[]>(){
    @Override
    public 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[]>() {
            @Override
            public 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;
    }
}

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

python lambda表达式(匿名函数)

python lambda表达式(匿名函数)

lambda 表达式 在Python中&#xff0c;匿名函数&#xff08;也称为lambda函数&#xff09;是一种简洁的方式来定义小函数&#xff0c;这些函数可以在需要的地方直接定义和使用&#xff0c;而不需要使用def关键字来定义一个具有名称的函数。 lambda 函数是一种小型、匿名的、内…
阅读更多...
软件测试/测试开发｜一文讲清楚你什么是测试用例

软件测试/测试开发｜一文讲清楚你什么是测试用例

前言 对于一个测试工程师来说&#xff0c;测试用例的编写是一项必须掌握的能力&#xff0c;但有效的设计和熟练的编写确实一项十分复杂的技术。不仅需要掌握软件测试技术和流程&#xff0c;而且还要对整个软件不管从业务&#xff0c;还是对软件的设计&#xff0c;程序模块的结…
阅读更多...
【Bugs】class path resource [xxx.xml] cannot be opened because it does not exist

【Bugs】class path resource [xxx.xml] cannot be opened because it does not exist

报错&#xff1a; 关键报错信息&#xff1a; class path resource [scope.xml] cannot be opened because it does not exist完整报错信息&#xff1a; 2024-03-01 14:26:58 866 [main] DEBUG org.springframework.context.support.ClassPathXmlApplicationContext - Refres…
阅读更多...
外部存储器接口（EMIF）

外部存储器接口（EMIF）

外部存储器接口&#xff08;EMIF&#xff09; 该设备支持双核架构&#xff1b;为了为每个CPU子系统提供一个专用的EMIF&#xff0c;该设备支持两个EMIF模块——EMIF1和EMIF2。两个模块完全相同&#xff0c;具有相同的功能集&#xff0c;但具有不同的地址/数据大小。EMIF1在CPU…
阅读更多...
赋能中国制造，大道云行发布智能制造分布式存储解决方案

赋能中国制造，大道云行发布智能制造分布式存储解决方案

《中国制造2025》指出&#xff0c;“制造业是国民经济的主体&#xff0c;是立国之本、兴国之器、强国之基。” 智能制造引领产业提质增效 智能制造是一种利用先进的信息技术、自动化技术和智能技术来优化和升级制造业生产过程的方法。它将人工智能、大数据、物联网、机器学习等…
阅读更多...
代码工具APEX的入门使用（未包含安装）

代码工具APEX的入门使用（未包含安装）

第一次使用APEX是2019年&#xff0c;这个技术成名已久只是我了解的比较晚。请看Oracle ACE的网站&#xff0c;这就是用APEX做的。实际上有一次我看O记的人操作他们的办公流程&#xff0c;都是用APEX做的。 那一年&#xff0c;我用APEX做了一个CMDB的管理系统。那时候还没有流行…
阅读更多...
Docker实战——容器

Docker实战——容器

目录 Docker 容器的基本概念与操作1.使用“docker create”创建容器。这里基于Nginx的镜像创建了一个容器&#xff0c;名字为mycontainer。2.使用“docker ps -a”命令查看所有的容器&#xff0c;这时的容器不一定是运行状态。3.使用 “docker start” 命令可以启动容器。4.使用…
阅读更多...
如何创建测试计划？这些要考虑到

如何创建测试计划？这些要考虑到

以下为作者观点&#xff1a; 创建一个彻底和有效的测试计划对软件测试的成功至关重要。它可以帮助识别过程中可能出现的潜在问题或问题。 什么是测试计划&#xff1f; 测试计划是一份文件&#xff0c;概述了软件测试过程的策略、目标、资源和时间表。测试计划通常包括一些细…
阅读更多...
抖店0元入驻不交钱会怎么样？个人店和个体店的利弊分析，开店必看

抖店0元入驻不交钱会怎么样？个人店和个体店的利弊分析，开店必看

我是王路飞。 现在的抖店是可以开通个人店的。 也就是不需要营业执照、直接使用个人身份证就可以在抖音开店&#xff0c;而且也不需要缴纳店铺保证金就能开店运营了。 但真实情况是怎么样的呢&#xff1f;新手0元入驻抖店不交这个保证金会怎么样呢&#xff1f; 今天给想在抖…
阅读更多...
倒计时35天

倒计时35天

小红的子序列权值和 (nowcoder.com) #include<bits/stdc.h> using namespace std; #define int long long const int N2e56; const int inf0x3f3f3f3f; const double piacos(-1.0); const int mod1e97; int c[1100][1100]; int a[1100],b[5]; void solve() {int n;cin>…
阅读更多...
布隆过滤器到底是什么东西？它有什么用

布隆过滤器到底是什么东西？它有什么用

一、问题解析 昨天&#xff0c;一个工作了 6 年的粉丝私聊我&#xff0c;说最近面试被问到布隆过滤器没回答出来。然后在网上找了一堆资料也没有说清楚&#xff0c;想让我帮他讲解一下&#xff0c;今天正好有空&#xff0c;给大家分享一下布隆过滤器。 在解释布隆过滤器之前&a…
阅读更多...
openGauss学习笔记-235 openGauss性能调优-系统调优-资源负载管理-资源管理准备-创建资源池

openGauss学习笔记-235 openGauss性能调优-系统调优-资源负载管理-资源管理准备-创建资源池

文章目录 openGauss学习笔记-235 openGauss性能调优-系统调优-资源负载管理-资源管理准备-创建资源池235.1 背景信息235.2 前提条件235.3 操作过程235.3.1 创建资源池235.3.2 管理资源池235.3.3 删除资源池 235.4 查看资源池的信息 openGauss学习笔记-235 openGauss性能调优-系…
阅读更多...
加密与安全_ 凯撒密码

加密与安全_ 凯撒密码

文章目录 Pre概述Code 实现 凯撒密码字母频率分析攻击Code解密凯撒密码 小结 Pre PKI - 02 对称与非对称密钥算法 概述 凯撒密码是一种简单的替换加密技术&#xff0c;也称为移位密码。它是古典密码学中最早的密码之一&#xff0c;得名于古罗马军队领袖凯撒尤利乌斯&#xff…
阅读更多...
express+mysql+vue,从零搭建一个商城管理系统7--token

express+mysql+vue,从零搭建一个商城管理系统7--token

提示&#xff1a;学习express&#xff0c;搭建管理系统 文章目录 前言一、安装jsonwebtoken二、新建config/jwt.js三、修改models/user.js四、修改routes下的user.js五、修改index.js六、Api新建user/queryUserList接口七、token验证失败示例总结 前言 需求&#xff1a;主要学习…
阅读更多...
Python爬虫副业真的可行吗？

Python爬虫副业真的可行吗？

首先回答你&#xff0c;是可行的&#xff0c;python爬虫能当副业&#xff0c;副业的方式比较多&#xff0c;等下我会讲几种。 那学到哪个层次可以接单呢&#xff1f;主要看你是接什么样的单&#xff0c;爬一些资料&#xff0c;视频这种简单的学一两个月就没什么问题&#xff0…
阅读更多...
（unity学习）一些效果的学习

（unity学习）一些效果的学习

一、学习视频 【Unity教程】零基础带你从小白到超神 二、效果实现 三、问题解决 Unity 点击UI与点击屏幕冲突的解决方案 关于unity UI界面操作与场景内操作不冲突问题
阅读更多...
TCPDump 使用教程

TCPDump 使用教程

每次服务器网络不通的时候&#xff0c;总会听到一个声音&#xff0c;你去抓包啊&#xff0c;那这里就来介绍下TCPDump&#xff0c;一款强大的网络分析工具&#xff0c;可以捕获网络上的数据包&#xff0c;并进行分析。这款工具在网络管理员和安全专家中非常受欢迎。 一、安装 …
阅读更多...
进程间通信之消息队列及共享内存

进程间通信之消息队列及共享内存

1.IPC对象: 内存文件 1.ipcs 查看系统重的消息队列、共享内存、信号灯的信息 2.ipcrm 删除消息队列、共享内存、信号灯 ipcrm -Q/-M/-S key ipcrm -q/-m/-s 消息队列ID/共享内存ID/信号灯ID 消息队列&#xff1a; 3.操作流程: …
阅读更多...
【论文阅读】High-Resolution Image Synthesis with Latent Diffusion Model

【论文阅读】High-Resolution Image Synthesis with Latent Diffusion Model

High-Resolution Image Synthesis with Latent Diffusion Model 引用&#xff1a; Rombach R, Blattmann A, Lorenz D, et al. High-resolution image synthesis with latent diffusion models[C]//Proceedings of the IEEE/CVF conference on computer vision and pattern re…
阅读更多...
智慧城市的创新实践：全球案例分享

智慧城市的创新实践：全球案例分享

一、引言 在全球化和数字化的时代&#xff0c;智慧城市已经成为城市发展的前沿趋势。智慧城市运用先进的信息技术&#xff0c;如大数据、物联网、云计算和人工智能等&#xff0c;提升城市管理的智能化水平&#xff0c;增强公共服务效率&#xff0c;优化居民生活质量。本文将通…
阅读更多...
最新文章

Copyright @ 2022~2023