算法训练(leetcode)二刷第二十六天 | *452. 用最少数量的箭引爆气球、435. 无重叠区间、*763. 划分字母区间

news/2024/11/16 0:46:51/

刷题记录

  • *452. 用最少数量的箭引爆气球
  • 435. 无重叠区间
  • *763. 划分字母区间
    • 笨拙版
    • 进阶版

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

leetcode题目地址

先对气球的坐标按照Xstart进行升序排序,只要两个气球之间挨着就可以一箭射穿,因此排序后查看后一个气球的起始坐标是否与前一个气球的结束坐标挨着(挨着:后一个起始坐标<=前一个结束坐标)。

时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度: O ( 1 ) O(1) O(1)

// java
class Solution {public int findMinArrowShots(int[][] points) {// 按照起始坐标从小到大排序 // 使用Integer内置比较方法,不会溢出Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));int cnt = 1;for(int i=1; i<points.length; i++){if(points[i][0] > points[i-1][1]){cnt++;}else{points[i][1] = Math.min(points[i][1], points[i-1][1]); }// System.out.println(points[i][0] + " " + points[i][1]);}return cnt;}
}

435. 无重叠区间

leetcode题目地址

和上题思路类似。本题是找到有重叠的区间,然后删除覆盖范围较大的那一个。先对区间进行排序,按照区间起始位置升序排序,若起始位置相同,则按照结束位置升序排序。

然后遍历数组,若后一个区间的起始位置小于前一个区间的结束位置(等于不算重叠),则两区间有重叠,删除后面的区间。这里的删除不是物理删除,是逻辑删除,更新后一个区间的结束区间即可,后一个区间的结束位置等于前一个区间的结束位置和后一个区间结束位置较小的那个。

时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度: O ( 1 ) O(1) O(1)

// java
class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a, b) -> {if(a[0] == b[0]){return Integer.compare(a[1], b[1]);}return Integer.compare(a[0], b[0]);});int cnt = 0;for(int i=1; i<intervals.length; i++){// 重叠if(intervals[i][0] < intervals[i-1][1]){cnt++;intervals[i][1] = Math.min(intervals[i][1], intervals[i-1][1]);}}return cnt;}
}

*763. 划分字母区间

leetcode题目地址

笨拙版

先统计字符串中每个字母的出现次数。
记录目前子串中出现的字母,若子串中的字母均已访问过则切分为一个子串记录长度。

使用map记录子串中的字母以及对应字母的剩余个数,当字母剩余0个时即当前字母访问结束从map中移除。

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( n ) O(n) O(n)

// java
class Solution {public List<Integer> partitionLabels(String s) {int[] chars = new int[26];for(int i=0; i<s.length(); i++){chars[s.charAt(i) - 'a']++;}List<Integer> result = new ArrayList<>();Map<Character, Integer> hash = new HashMap<>();int start = 0;for(int i=0; i<s.length(); i++){chars[s.charAt(i) - 'a']--;if(hash.containsKey(s.charAt(i))) hash.put(s.charAt(i), hash.get(s.charAt(i))-1);else hash.put(s.charAt(i), chars[s.charAt(i) - 'a']);if(hash.get(s.charAt(i)) == 0) hash.remove(s.charAt(i));if(hash.isEmpty()){result.add(i-start+1);start = i+1;}}return result;}
}

进阶版

先统计每个字符的最后出现的位置,当访问字符串时,若已到达子串中所有字符的最后位置,则记录当前子串长度。

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)

// java
class Solution {public List<Integer> partitionLabels(String s) {int[] hash = new int[26];for(int i=0; i<s.length(); i++){// 记录最后出现的位置hash[s.charAt(i) - 'a'] = i;}List<Integer> result = new ArrayList<>();int start = 0;int end = 0;for(int i=0; i<s.length(); i++){end = Math.max(end, hash[s.charAt(i) - 'a']);if(i == end){// 到达当前子串最右端result.add(end-start+1);start = i+1;}}return result;}
}

http://www.ppmy.cn/news/1547311.html

相关文章

MYSQL 修改表的结构

在项目的实际开发中&#xff0c;随着版本的迭代和需求的变更&#xff0c;经常会对表结构进行调整&#xff0c;比如向现有表中添加列&#xff0c;删除列&#xff0c;或者修改某列的列名、数据类型或长度&#xff0c;这时就需要对表进行修改操作。 修改表结构语法 ALTER TABLE t…

SDL读取PCM音频

文章目录 音频相关的函数主线程循环更新回调函数fill_audio_pcm的调用频率是// PCM_BUFFER_SIZE 1024 (采样点) * 2 (通道) * 2 (字节/采样点) * 2 (帧) 8192 字节设置的音频流大小 音频相关的函数 int SDLCALL SDL_OpenAudio(SDL_AudioSpec * desired, SDL_AudioSpec * obta…

Go中数组和切片

数组和切片 【1】、数组 1、什么是数组 一组数 数组需要是相同类型的数据的集合 数组是需要定义大小的 数组一旦定义了大小是不可以改变的。 package mainimport "fmt"// 数组 // 数组和其他变量定义没什么区别&#xff0c;唯一的就是这个是一组数&#xff0c;需要…

layui的table组件中,对某一列的文字设置颜色为浅蓝怎么设置

问&#xff1a; layui的table组件中&#xff0c;对某一列的文字设置颜色为浅蓝怎么设置 回答&#xff1a; <!DOCTYPE html> <html lang"zh"> <head><meta charset"UTF-8"><title>layui 表格示例</title><link r…

C++使用开源ConcurrentQueue库处理自定义业务数据类

ConcurrentQueue开源库介绍 ConcurrentQueue是一个高性能的、线程安全的并发队列库。它旨在提供高效、无锁的数据结构&#xff0c;适用于多线程环境中的数据交换。concurrentqueue 支持多个生产者和多个消费者&#xff0c;并且提供了多种配置选项来优化性能和内存使用。 Conc…

Flink使用SQL Gateway提交SQL Job到远程集群

从Flink 1.16.0开始集成了SQL Gateway功能&#xff0c;提供了多种客户端远程并发执行SQL的能力。不用再使用提交jar包的方式来创建任务了。 我是使用filnk 1.17.1版本。 官网关于SQL Gateway的讲解&#xff1a;https://nightlies.apache.org/flink/flink-docs-release-1.17/z…

单片机 外部中断实验 实验三

实验三 外部中断实验 实验目的 1、掌握MCS-51单片机外部中断的原理。 2、掌握MCS-51单片机外部中断程序的设计方法及其过程。 3、掌握MCS-51单片机外部中断的电路应用。 实验任务 利用外部中断方式&#xff0c;实现通过按键切换流水灯的流向。流水灯形式自定&#xff…

Rust实战项目与未来发展——跨平台应用开发项目实践

第十章&#xff1a;实战项目与未来发展 第一节&#xff1a;跨平台应用开发项目实践 随着移动设备、桌面设备和Web平台之间界限的模糊&#xff0c;跨平台应用开发已成为开发者日常工作中不可或缺的一部分。随着技术栈的不断演进&#xff0c;开发者有更多选择来构建高效、易维护…