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

刷题记录

  • *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.rhkb.cn/news/471695.html

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

相关文章

【数据结构】AVL树

引言&#xff1a;在实际情况中&#xff0c;数据不仅仅要存储起来&#xff0c;还要进行对数据进行搜索&#xff0c;为了方便进行高效搜索(在此之前的数据结构的搜索基本都是暴力搜索)二叉搜索树应运而生。但是在极端情况下(我们按照有序的方式进行插入)&#xff0c;二叉搜索树就…

CSS的综合应用例子(网页制作)

这是html的一些最基本内容的代码&#xff1a; <!DOCTYPE html> <html lang"zh"> <head> <meta charset"UTF-8"> <meta name"viewport" content"widthdevice-width, initial-scale1.0"> <t…

MySQL查询某个数据库中特定表的空间占用大小

如果您也想要查询某个数据库中特定表的空间占用大小&#xff0c;包括数据和索引的大小&#xff0c;那么您可以使用以下SQL查询。这个查询将显示特定表在数据库中的数据大小、索引大小以及总大小。 SELECT table_name AS Table,ROUND(((data_length index_length) / 1024 / 10…

Towards Reasoning in Large Language Models: A Survey

文章目录 题目摘要引言什么是推理?走向大型语言模型中的推理测量大型语言模型中的推理发现与启示反思、讨论和未来方向 为什么要推理?结论题目 大型语言模型中的推理:一项调查 论文地址:https://arxiv.org/abs/2212.10403 项目地址: https://github.com/jeffhj/LM-reason…

进入未来城:第五周游戏指南

欢迎来到 Alpha 第 4 季第五周&#xff01; 走进霓虹闪烁的未来城街道&#xff0c;这是一座科技至上的赛博朋克大都市。鳞次栉比的摩天大楼熠熠生辉&#xff0c;拥挤的街道下则是阴森恐怖的地下世界。在这里&#xff0c;像激光鹰队长这样的超级战士正在巡逻&#xff0c;而 Ago…

斯坦福泡茶机器人DexCap源码解析:涵盖收集数据、处理数据、模型训练三大阶段

前言 因为我司「七月在线」关于dexcap的复现/优化接近尾声了(每月逐步提高复现的效果)&#xff0c;故准备把dexcap的源码也分析下&#xff0c;11月​下旬则分析下iDP3的源码——为队伍「iDP3人形的复现/优化」助力 最开始&#xff0c;dexcap的源码分析属于此文《DexCap——斯…

Python中的HTML

文章目录 一. HTML1. html的定义2. html的作用3. 基本结构4. 常用的html标签5. 列表标签① 无序列表② 有序列表 6. 表格标签7. 表单标签8. 表单提交① 表单属性设置② 表单元素属性设置 一. HTML 1. html的定义 HTML 的全称为&#xff1a;HyperText Mark-up Language, 指的是…

PdServer:调用MidjourneyAPI完成静夜思图文生成

欢迎沟通讨论&#xff0c;WX: cdszsz。公号&#xff1a;AIGC中文站。 今天我们将使用PdServer&#xff0c;通过Qwen大模型完成古诗的解析与prompt的生成&#xff0c;然后调用MidjourneyAPI完成图片的生成。有了文案和图片&#xff0c;我们就可以将其生成为一个古诗讲读视频。从…

论文 | The Capacity for Moral Self-Correction in LargeLanguage Models

概述 论文探讨了大规模语言模型是否具备“道德自我校正”的能力&#xff0c;即在收到相应指令时避免产生有害或偏见输出的能力。研究发现&#xff0c;当模型参数达到一定规模&#xff08;至少22B参数&#xff09;并经过人类反馈强化学习&#xff08;RLHF&#xff09;训练后&…

认证鉴权框架SpringSecurity-1--概念和原理篇

1、基本概念 Spring Security 是一个强大且高度可定制的框架&#xff0c;用于构建安全的 Java 应用程序。它是 Spring 生态系统的一部分&#xff0c;提供了全面的安全解决方案&#xff0c;包括认证、授权、CSRF防护、会话管理等功能。 2、认证、授权和鉴权 &#xff08;1&am…

删库跑路,启动!

起因&#xff1a;这是一个悲伤的故事&#xff0c;在抓logcat时 device待机自动回根目录了&#xff0c;而题主对当前路径的印象还停留在文件夹下&#xff0c;不小心在根目录执行了rm -rf * … 所以&#xff0c;这是个悲伤的故事&#xff0c;东西全没了…device也黑屏了&#xff…

unity单例模式的不同声明(待完善

总结&#xff1a; 这段代码实现了一个泛型单例模式&#xff08;Singleton Pattern&#xff09;&#xff0c;用于确保某个类&#xff08;由泛型参数 T 指定&#xff09;在整个应用程序中只有一个实例&#xff0c;并且在第一次访问时才创建该实例。该模式保证了该实例的全局唯一…

低代码牵手 AI 接口:开启智能化开发新征程

一、低代码与 AI 接口的结合趋势 低代码开发平台近年来在软件开发领域迅速崛起。随着企业数字化转型的需求不断增长&#xff0c;低代码开发平台以其快速构建应用程序的优势&#xff0c;满足了企业对高效开发的需求。例如&#xff0c;启效云低代码平台通过范式化和高颗粒度的可配…

3. Sharding-Jdbc核⼼流 程+多种分⽚策略

1. Sharding-Jdbc 分库分表执⾏核⼼流程 Sharding-JDBC执行流程 1. SQL解析 -> SQL优化 -> SQL路由 -> SQL改写 -> SQL执⾏-> 结果归并 ->返回结果简写为&#xff1a;解析->路由->改写->执⾏->结果归并1.1 SQL解析 1. SQL解析过程分为词法解析…

解读Nature:Larger and more instructable language models become less reliable

目录 Larger and more instructable language models become less reliable 核心描述 核心原理 创新点 举例说明 大模型训练,微调建议 Larger and more instructable language models become less reliable 这篇论文的核心在于对大型语言模型(LLMs)的可靠性进行了深入…

A3超级计算机虚拟机,为大型语言模型LLM和AIGC提供强大算力支持

热门大语言模型项目地址&#xff1a;www.suanjiayun.com/mirrorDetails?id66ac7d478099315577961758 近几个月来&#xff0c;我们目睹了大型语言模型&#xff08;LLMs&#xff09;和生成式人工智能强势闯入我们的视野&#xff0c;显然&#xff0c;这些模型在训练和运行时需要…

跟着尚硅谷学vue2—基础篇4.0

11. 收集表单数据 收集表单数据&#xff1a; 若&#xff1a;<input type"text"/>&#xff0c;则v-model收集的是value值&#xff0c;用户输入的就是value值。 若&#xff1a;<input type"radio"/>&#xff0c;则v-model收集的是value值&…

「人眼视觉不再是视频消费的唯一形式」丨智能编解码和 AI 视频生成专场回顾@RTE2024

你是否想过&#xff0c;未来你看到的电影预告片、广告&#xff0c;甚至新闻报道&#xff0c;都可能完全由 AI 生成&#xff1f; 在人工智能迅猛发展的今天&#xff0c;视频技术正经历着一场前所未有的变革。从智能编解码到虚拟数字人&#xff0c;再到 AI 驱动的视频生成&#…

【LeetCode】每日一题 2024_11_14 统计好节点的数目(图/树的 DFS)

前言 每天和你一起刷 LeetCode 每日一题~ LeetCode 启动&#xff01; 题目&#xff1a;统计好节点的数目 代码与解题思路 先读题&#xff1a;题目要求我们找出好节点的数量&#xff0c;什么是好节点&#xff1f;“好节点的所有子节点的数量都是相同的”&#xff0c;拿示例一…

js中typeOf无法区分数组对象

[TOC]&#xff08;js中typeOf无法区分数组对象) 前提&#xff1a;很多时候我们在JS中用typeOf来判断值类型&#xff0c;如&#xff1a;typeOf ‘abc’//string ,typeOf 123 //number; 但当判断对象为数组时返回的仍是’object’ 这时候我们可以使用Object.prototype.toString.c…