代码随想录第三十一天| 56. 合并区间 738.单调递增的数字
56. 合并区间
题目描述
给定一个区间的集合 intervals,请合并所有重叠的区间。
解题思路
-
排序区间
- 按照每个区间的起点
start升序排序,便于后续合并。
- 按照每个区间的起点
-
合并区间
- 使用两个变量
start和right分别记录当前区间的起点和终点。 - 遍历排序后的区间:
- 如果当前区间的起点
intervals[i][0]小于或等于right,说明当前区间与之前的区间重叠,更新right为两者终点的最大值。 - 如果不重叠,将当前区间
[start, right]添加到结果中,并更新start和right为当前区间的起点和终点。
- 如果当前区间的起点
- 使用两个变量
-
时间复杂度
- 排序时间复杂度为 O(n log n)。
- 遍历时间复杂度为 O(n)。
- 总时间复杂度为 O(n log n),空间复杂度为 O(n)。
Java代码
class Solution {public int[][] merge(int[][] intervals) {List<int[]> res = new LinkedList<>();Arrays.sort(intervals , (a,b) ->{return Integer.compare(a[0],b[0]);});int start = intervals[0][0];int right = intervals[0][1];for(int i = 1;i<intervals.length;i++){if(intervals[i][0]<=right){right = Math.max(intervals[i][1],right);}else {res.add(new int[]{start,right});start = intervals[i][0];right = intervals[i][1];}}res.add(new int[]{start,right});return res.toArray(new int[res.size()][]);}
}
738.单调递增的数字
题目:给定一个非负整数 N,找出小于或等于 N 的最大的整数,同时这个整数需要满足其各个位数上的数字是单调递增。
(当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。)
解题思路:
代码:
class Solution {public int monotoneIncreasingDigits(int n) {String[] strings = (n + "").split("");int start = strings.length;for(int i = strings.length-1;i>0;i--){if(Integer.parseInt(strings[i]) < Integer.parseInt(strings[i-1])){strings[i-1] = (Integer.parseInt(strings[i-1])-1) + "";start = i;}}for(int i =start;i<strings.length;i++){strings[i] = "9";}return Integer.parseInt(String.join("",strings));}
}
class Solution {public int monotoneIncreasingDigits(int n) {String s = String.valueOf(n);char[] chars = s.toCharArray();int start = chars.length;for(int i = chars.length-1;i>0;i--){if(chars[i] < chars[i-1]){chars[i-1]--;start = i;}}for(int i =start;i<chars.length;i++){chars[i] = '9';}return Integer.parseInt(String.valueOf(chars));}
}
相关文章:
代码随想录第三十一天| 56. 合并区间 738.单调递增的数字
56. 合并区间 题目描述 给定一个区间的集合 intervals,请合并所有重叠的区间。 解题思路 排序区间 按照每个区间的起点 start 升序排序,便于后续合并。 合并区间 使用两个变量 start 和 right 分别记录当前区间的起点和终点。遍历排序后的区间&#x…...
C语言基本知识 2.2void 函数
在C语言中, void 是一个重要的关键字,具有多种用途,以下是详细介绍: 函数返回值类型声明 - 当函数不需要返回任何值时,可以将函数的返回值类型声明为 void 。例如: void printMessage() { printf(…...
Spring 框架中哪些接口可以创建对象
Spring 框架中哪些接口可以创建对象 在 Spring 框架中,向 IOC 容器中添加 Bean 主要有以下几种接口和方式。Spring 提供了不同的手段来实现对象的创建和管理,涵盖了不同的需求和场景。以下是几种常用的接口和方式: 1. BeanFactory 接口 Be…...
豆瓣书摘 | 爬虫 | Python
获取豆瓣书摘,存入MongoDB中。 import logging import timeimport requests from bs4 import BeautifulSoup from pymongo import MongoClientheaders {accept: text/html,application/xhtmlxml,application/xml;q0.9,image/avif,image/webp,image/apng,*/*;q0.8,…...
Oracle数据库物理存储结构管理
大家好,我是程序员小羊! 前言: 安装和配置Oracle数据库是一个涉及多个步骤的任务,通常包括环境准备、软件安装、数据库创建和基本配置等。以下是详细的安装与配置流程。 一、环境准备 1. 系统要求 操作系统:Wind…...
java——Map接口
Java的Map接口是一种键值对的数据结构,用于存储和操作键值对的集合。它是Java集合框架中的一部分,提供了一种以键值对形式组织数据的方法。 Map接口有多个实现类,常用的有HashMap、TreeMap和LinkedHashMap。每种实现类都有不同的特点和适用场…...
量子计算机全面解析:技术、应用与未来
标题:量子计算机全面解析:技术、应用与未来 一、什么是量子计算机? 量子计算机是一种利用量子力学原理(如叠加、纠缠和干涉)进行计算的新型计算设备。与传统计算机基于比特(0 和 1)的运算方式不…...
IDEA相关(包括但不限于快捷键,使用技巧)成长笔记
1.IDEA创建及命名规范 IDEA创建是:项目、模块、包、类 命名规范: 1.项目名全部小写 2.包名全部小写 3.类名首字母大写,一般都是使用驼峰式命名。 如:public class MyFirstClass{} 4.同上: 变量名、方法名首字母小…...
【再谈设计模式】适配器模式 ~接口兼容的桥梁
一、引言 在软件开发的复杂世界里,不同的组件、类或者系统往往有着各自独立的设计和接口定义。当需要将这些原本不兼容的部分整合在一起协同工作时,就像尝试将方形的榫头插入圆形的卯眼一样困难。适配器设计模式就如同一位神奇的工匠,能够巧妙…...
使用Cursor和Claude AI打造你的第一个App
大家好,使用Cursor和Claude AI打造应用程序是一个结合智能代码辅助和人工智能对话的创新过程。Cursor是一个编程辅助工具,它通过智能代码补全、聊天式AI对话和代码生成等功能,帮助开发者提高编程效率。Claude AI则是一个强大的人工智能平台&a…...
粗读Apache Paimon 的基本概念及其组成结构
文章目录 一、Paimon的基本概念(一)快照(二)分区(三)分桶(四)一致性保证 二、Paimon的组成结构(一)文件布局(二)存储结构(…...
c++调用 c# dll 通过 P/Invoke (详细避坑)
项目场景: VS2022 .NET8 , 项目应用的库需要支持AOT,不支持AOT的库看这里 我的c项目很奇怪,如果使用 clr 调用c# dll,会有很多报错,所以使用 P/Invoke方法,这个方法不会有任何奇怪的报错 解决方案 示例…...
李春葆《数据结构》——图相关代码
邻接矩阵结构体: #define MAX<最大结点个数> #define INF 32765 //定义无穷 typedef struct{int no;//顶点的编号;InfoType info;//顶点的其他信息 }vertexType;//顶点的类型 typedef struct{int edges[MAX][Max];//邻接矩阵数组 int vertexTy…...
Linux驱动开发第2步_“物理内存”和“虚拟内存”的映射
“新字符设备的GPIO驱动”和“设备树下的GPIO驱动”都要用到寄存器地址,使用“物理内存”和“虚拟内存”映射时,非常不方便,而pinctrl和gpio子系统的GPIO驱动,非常简化。因此,要重点学习pinctrl和gpio子系统下的GPIO驱…...
告别多品牌乱战,吉利开始觉醒
科技新知 原创作者丨思原 编辑丨蕨影 2007年,是国内自主品牌汽车萌芽的一年,当时行业普遍奉行“多生孩子好打架”战略,吉利也是在这样的背景下发布了《宁波宣言》,奠定了之后十多年的发展主导思想。 然而,新能源的快…...
Target-absent Human Attention
Abstract 预测人类注视行为对于构建能够预测用户注意力的人机交互系统非常重要。已经开发出计算机视觉模型来预测人们在搜索目标物体时的注视点。但当目标不存在于图像中时,又该如何处理呢?同样重要的是要了解当人们找不到目标时,他们如何进行搜索,以及何时停止搜索。在本文…...
<QNAP 453D QTS-5.x> 日志记录:在 Docker 中运行的 Flask 应用安装 自签名 SSL 证书 解决 Chrome 等浏览器证书安全
原因:Chrome 不信任 ssc 证书 使启用了 HTTPS,即使有使用 自签名证书 (self-signed certificate 非由可信的证书颁发机构 【CA,Certificate Authority】签发的)。浏览器 Chrome 默认不信任自签名证书,也会报 NET::ERR_…...
通过huggingface-cli下载Hugging Face上的公开数据集或模型至本地
1. 获取 Access Tokens 在使用huggingface-cli命令下载之前需要先去官网获取 Access Tokens: 获取tokens的官网链接:https://huggingface.co/settings/tokens点击新增 token: 然后选择 write 权限: 最后,这个 Access…...
论文阅读——Intrusion detection systems using longshort‑term memory (LSTM)
一.基本信息 论文名称:Intrusion detection systems using longshort‑term memory (LSTM) 中文翻译:基于长短期记忆(LSTM)的入侵检测系统 DOI:10.1186/s40537-021-00448-4 作者:FatimaEzzahra Laghrissi1* , Samira Douzi2*, Kha…...
SparkSQL的执行过程:从源码角度解析逻辑计划、优化计划和物理计划
SparkSQL的执行过程可以分为以下几个阶段:从用户的SQL语句到最终生成的RDD执行,涵盖逻辑计划、优化计划和物理计划。以下是详细的源码角度解析: 1. 解析阶段(Parsing) SQL语句解析:Spark 使用 Catalyst 引…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...
使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...
Qt的学习(一)
1.什么是Qt Qt特指用来进行桌面应用开发(电脑上写的程序)涉及到的一套技术Qt无法开发网页前端,也不能开发移动应用。 客户端开发的重要任务:编写和用户交互的界面。一般来说和用户交互的界面,有两种典型风格&…...
