算法训练Day35|860.柠檬水找零 ● 406.根据身高重建队列 ● 452. 用最少数量的箭引爆气球

简介: 算法训练Day35|860.柠檬水找零 ● 406.根据身高重建队列 ● 452. 用最少数量的箭引爆气球

LeetCode:860.柠檬水找零

860. 柠檬水找零 - 力扣(LeetCode)

1.思路

通过map做映射,记录5,10出现的次数,然后罗列5、10、20出现时对map中元素数量的影响,排除所有不符合条件的,最后符合条件的返回true.

2.代码实现

 1class Solution {
 2    public boolean lemonadeChange(int[] bills) {
 3        // 映射
 4        Map<Integer, Integer> map = new HashMap<>(); 
 5        map.put(5, 0);
 6        map.put(10, 0);
 7        for (int i = 0; i < bills.length; i++) {
 8            if (bills[i] == 5) {
 9                map.put(5, map.get(5) + 1);
10            } else if (bills[i] == 10) {
11                if (map.get(5) > 0) {
12                    map.put(5, map.get(5) - 1);
13                    map.put(10, map.get(10) + 1);
14                } else {
15                    return false;
16                }
17            } else if (bills[i] == 20){
18                if (map.get(5) > 0 && map.get(10) > 0) {
19                    map.put(5, map.get(5) - 1);
20                    map.put(10, map.get(10) - 1);
21                } else if (map.get(5) >= 3){
22                    map.put(5, map.get(5) - 3);
23                } else {
24                    return false;
25                }
26            }
27        }
28        return true;
29    }
30}

3.复杂度分析

时间复杂度:O(n).

空间复杂度:O(1).


LeetCode:406.根据身高重建队列

406. 根据身高重建队列 - 力扣(LeetCode)


1.思路

先判断身高,从高到低排列,对于相同身高按照k值从低到高排列。

方法不熟悉,调用还挺难的…


2.代码实现

 1class Solution {
 2    public int[][] reconstructQueue(int[][] people) {
 3        Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
 4
 5        List<int[]> list = new ArrayList<>();
 6
 7        for (int i = 0; i < people.length; i++) {
 8            int[] person = people[i];
 9            list.add(person[1], person);
10        }
11        return list.toArray(new int[people.length][]);
12    }
13}

3.复杂度分析

时间复杂度:O(n^2).

空间复杂度:O(n).

LeetCode:452. 用最少数量的箭引爆气球

452. 用最少数量的箭引爆气球 - 力扣(LeetCode)

1.思路

对齐左边界,更新右边界,思路清晰,方法调用较弱

2.代码实现

 1class Solution {
 2    public int findMinArrowShots(int[][] points) {
 3        Arrays.sort(points, (a, b) -> Integer.compare(a[0] , b[0]));
 4
 5        int count = 1;
 6        for (int i = 1; i < points.length; i++) {
 7            if (points[i][0] > points[i - 1][1]) {
 8                count++;
 9            } else {
10                points[i][1] = Math.min(points[i - 1][1], points[i][1]);
11            }
12        }
13        return count;
14    }
15}

3.复杂度分析

时间复杂度:O(logn).

空间复杂度:O(1).

4.视频解析

贪心算法,判断重叠区间问题 | LeetCode:452.用最少数量的箭引爆气球_哔哩哔哩_bilibili

相关文章
|
7月前
|
缓存 监控 算法
内网监控管理软件:PHP 语言队列算法揭秘
在数字化办公环境中,内网监控管理软件对企业的稳定运行和信息安全至关重要。本文深入介绍PHP中的队列算法及其在内网监控软件中的应用,包括监控数据收集、任务调度和日志记录等场景,通过代码示例展示其实现方法。队列算法可提高性能、保证数据顺序并实现异步处理,为企业提供高效的安全保障。
98 1
|
11月前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合,涵盖了从基础到提高的多个算法题目及其解答。
492 3
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
|
10月前
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
|
10月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
11月前
|
机器学习/深度学习 算法 决策智能
【机器学习】揭秘深度学习优化算法:加速训练与提升性能
【机器学习】揭秘深度学习优化算法:加速训练与提升性能
|
11月前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
127 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
|
11月前
|
算法 数据挖掘
【栈和队列】算法题 ---- 力扣(二)
【栈和队列】算法题 ---- 力扣
|
11月前
|
存储 算法
【栈和队列】算法题 ---- 力扣(一)
【栈和队列】算法题 ---- 力扣
|
11月前
|
算法 Java C++
【贪心算法】算法训练 ALGO-1003 礼物(C/C++)
【贪心算法】算法训练 ALGO-1003 礼物(C/C++)
【贪心算法】算法训练 ALGO-1003 礼物(C/C++)
|
11月前
|
算法 C++
蓝桥 算法训练 共线(C++)
蓝桥 算法训练 共线(C++)

热门文章

最新文章