LeetCode题练习与总结:迷你语法分析器--385
一、题目描述
给定一个字符串 s 表示一个整数嵌套列表,实现一个解析它的语法分析器并返回解析的结果 NestedInteger 。
列表中的每个元素只可能是整数或整数嵌套列表
示例 1:
输入:s = "324", 输出:324 解释:你应该返回一个 NestedInteger 对象,其中只包含整数值 324。
示例 2:
输入:s = "[123,[456,[789]]]", 输出:[123,[456,[789]]] 解释:返回一个 NestedInteger 对象包含一个有两个元素的嵌套列表: 1. 一个 integer 包含值 123 2. 一个包含两个元素的嵌套列表:i. 一个 integer 包含值 456ii. 一个包含一个元素的嵌套列表a. 一个 integer 包含值 789
提示:
1 <= s.length <= 5 * 10^4s由数字、方括号"[]"、负号'-'、逗号','组成- 用例保证
s是可解析的NestedInteger - 输入中的所有值的范围是
[-10^6, 10^6]
二、解题思路
解题思路:
- 如果字符串
s的第一个字符不是[,那么它是一个整数,可以直接解析并返回。 - 如果
s的第一个字符是[,那么它是一个嵌套列表。我们需要遍历字符串,解析出每个元素(整数或嵌套列表),并将其添加到结果NestedInteger对象中。
在解析嵌套列表时,我们需要注意以下几点:
- 使用一个栈来追踪嵌套的深度。每当遇到
[,将一个新NestedInteger对象压入栈中;每当遇到],将栈顶的NestedInteger对象弹出。 - 当遇到
,或]时,表示一个元素的结束。如果元素不是空的,将其添加到栈顶的NestedInteger对象中。
三、具体代码
import java.util.*;public class Solution {public NestedInteger deserialize(String s) {if (s == null || s.isEmpty()) {return new NestedInteger();}if (s.charAt(0) != '[') { // 如果不是以'['开头,则表示是一个整数return new NestedInteger(Integer.parseInt(s));}// 如果以'['开头,则表示是一个嵌套列表Stack<NestedInteger> stack = new Stack<>();NestedInteger curr = null;int numStart = 0; // 数字开始的索引for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (c == '[') {// 遇到 '[' 时,将一个新的 NestedInteger 压入栈中if (curr != null) {stack.push(curr);}curr = new NestedInteger();numStart = i + 1; // 数字开始的索引更新} else if (c == ',' || c == ']') {// 遇到 ',' 或 ']' 时,表示一个元素的结束if (i > numStart) { // 确保字符串不是空的String num = s.substring(numStart, i);if (!num.isEmpty()) {curr.add(new NestedInteger(Integer.parseInt(num)));}}numStart = i + 1; // 数字开始的索引更新if (c == ']') {// 遇到 ']' 时,将当前 NestedInteger 弹出并添加到上一个 NestedInteger 中if (!stack.isEmpty()) {NestedInteger pop = stack.pop();pop.add(curr);curr = pop;}}}}return curr;}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
代码中的主要操作是遍历字符串 s,这个操作的时间复杂度是 O(n),其中 n 是字符串 s 的长度。在遍历过程中,对于每个字符,我们执行了常数时间的操作,例如字符比较、字符串子串的创建和整数的解析。这些操作不会改变整体的时间复杂度,仍然是 O(n)。
因此,整体的时间复杂度是 O(n)。
2. 空间复杂度
空间复杂度主要取决于以下两个因素:
-
栈
stack:在最坏的情况下,如果嵌套列表非常深,那么栈的大小将接近字符串的长度 n。因此,栈的空间复杂度是 O(n)。 -
字符串子串:在每次遇到逗号或右括号时,我们可能创建了一个新的字符串子串。在最坏的情况下,每次都会创建一个新的子串,这些子串的总长度将接近字符串的长度 n。因此,字符串子串的空间复杂度也是 O(n)。
综上所述,整体的空间复杂度是 O(n),因为这两个空间需求是并列的,不是累加的。
五、总结知识点
-
接口与实现:
NestedInteger接口的使用,该接口定义了嵌套整数的抽象操作。
-
字符串处理:
- 使用
charAt方法来访问字符串中的单个字符。 - 使用
substring方法来提取字符串的子串。
- 使用
-
异常处理:
- 在将字符串转换为整数时,如果字符串不是一个有效的整数表示,
parseInt方法会抛出NumberFormatException。
- 在将字符串转换为整数时,如果字符串不是一个有效的整数表示,
-
数据结构:
- 使用
Stack来处理嵌套结构,这是解决此类问题的一种常见方法。
- 使用
-
逻辑控制:
- 使用循环 (
for循环) 来遍历字符串。 - 使用条件语句 (
if-else) 来根据不同的字符进行不同的处理。
- 使用循环 (
-
递归结构:
- 虽然代码本身不是递归的,但处理嵌套列表的逻辑是递归的,因为每次遇到
[时,都会创建一个新的NestedInteger对象,并在遇到]时将其添加到上一层的NestedInteger对象中。
- 虽然代码本身不是递归的,但处理嵌套列表的逻辑是递归的,因为每次遇到
-
对象操作:
- 创建
NestedInteger对象,并使用add方法来添加整数或嵌套列表。
- 创建
-
边界条件处理:
- 检查字符串是否为空或
null,并返回一个空的NestedInteger对象。 - 确保在添加整数前字符串子串不为空。
- 检查字符串是否为空或
-
索引管理:
- 使用变量
numStart来跟踪当前数字子串的开始位置。
- 使用变量
-
栈的操作:
- 使用
push方法将对象压入栈中。 - 使用
pop方法从栈中弹出对象。
- 使用
以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。
相关文章:
LeetCode题练习与总结:迷你语法分析器--385
一、题目描述 给定一个字符串 s 表示一个整数嵌套列表,实现一个解析它的语法分析器并返回解析的结果 NestedInteger 。 列表中的每个元素只可能是整数或整数嵌套列表 示例 1: 输入:s "324", 输出:324 解释ÿ…...
Unity WebGL交互通信
Unity 调用 H5 本文使用的 unity 版本为:2021.3.3 1.在unity中通过c#的特性DllImport导出外部实现函数 [DllImport("__Internal")]private static extern void callJsString(string param);[DllImport("__Internal")]private static extern vo…...
王道考研之数据结构
数据结构系列 提示:这里可以添加系列文章的所有文章的目录,目录需要自己手动添加 数据结构 数据结构系列1.线性表1.1 线性表的定义和相关概念1.2 线性表的创销 增删查改 判空表长打印 2.顺序表2.1 顺序表定义和相关概念2.2 顺序表的静态实现2.3 顺序表的…...
实习冲刺Day17
算法题 x的平方根 69. x 的平方根 - 力扣(LeetCode) class Solution { public:int mySqrt(int x) {long left 0,right x;//定义左右边界//数值取的大longlong类型while (left < right) {long mid (right-left1)/2left;//定义中间节点if ((mid *…...
我自己nodejs练手时常用的一些库基础用法
我自己在使用nodejs以及前端实战练习时常用的一些库的基本使用 1.bcrypt //注册账号时,给密码加密 password是前端传过来的密码,hashPassword是存到数据库中的密码 const bcrypt require(bcrypt) const hashPassword bcrypt.hash(password,10) //登…...
岛屿数量问题
给一个0 1矩阵,1代表是陆地,0代表海洋, 如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。 岛屿问题: 相邻陆地可以组成一个岛屿(相邻:上下左右) 判断岛屿个数。 C 解决方案 #include &…...
智能制造基础- TPM(全面生产维护)
TPM 前言一、TPM二、TPM实施步骤三、 消除主要问题3.1 实施指南3.2 如何进行“主要问题”的消除? 四、自主维护4.1 实施指南4.2 主要工作内容4.3 如何进行“自主维护“ 五、计划维护5.1 实施指南5.2 如何实施计划维护 六、TPM 适当的 设备 设计5.1 实施指南5.2 如何…...
C++学习笔记----11、模块、头文件及各种主题(一)---- 模板概览与类模板(4)
2.2.2、显式实例化 有危险存在于有些类模板成员函数的编译错误,在隐式实例化时没有注意到。未被使用的类模板成员函数也可能包含语法错误,因为它们不会被编译到。这会使得检测代码的语法错误很困难。可以强制编译器生成所有成员函数的代码,vi…...
【力扣热题100】[Java版] 刷题笔记-160. 相交链表
题目:160. 相交链表 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。 图示两个链表在节点 c1 开始相交: 题目数据 保证 整个链式结构中不存在环。 注意…...
多线程和线程同步复习
多线程和线程同步复习 进程线程区别创建线程线程退出线程回收全局写法传参写法 线程分离线程同步同步方式 互斥锁互斥锁进行线程同步 死锁读写锁api细说读写锁进行线程同步 条件变量生产者消费者案例问题解答加强版生产者消费者 总结信号量信号量实现生产者消费者同步-->一个…...
贝式计算的 AI4S 观察:使用机器学习对世界进行感知与推演,最大魅力在于横向扩展的有效性
「传统研究方法高度依赖于科研人员自身的特征和问题定义能力,通常采用小数据,在泛化能力和拓展能力上存疑。而 AI 研究方法则需要引入大规模、高质量数据,并采用机器学习进行特征抽取,这使得产生的科研结果在真实世界的问题中非常…...
容器化技术入门:Docker详解
💓 博客主页:瑕疵的CSDN主页 📝 Gitee主页:瑕疵的gitee主页 ⏩ 文章专栏:《热点资讯》 容器化技术入门:Docker详解 容器化技术入门:Docker详解 容器化技术入门:Docker详解 引言 Doc…...
基于SSM(Spring + Spring MVC + MyBatis)框架的药房管理系统
基于SSM(Spring Spring MVC MyBatis)框架的药房管理系统 项目概述 功能需求 用户管理:管理员可以添加、删除、修改和查询用户信息。药品管理:支持对药品信息的增删改查操作,包括药品名称、价格、库存量等。供应商…...
在服务器里安装2个conda
1、安装新的conda 下载地址:Index of /anaconda/archive/ | 清华大学开源软件镜像站 | Tsinghua Open Source Mirror 本文选择:Anaconda3-2023.03-1-Linux-x86_64.sh 安装:Ubuntu安装Anaconda详细步骤(Ubuntu22.04.1ÿ…...
web安全漏洞之ssrf入门
web安全漏洞之ssrf入门 1.什么是ssrf SSRF(Server Side Request Forgery,服务端请求伪造)是一种通过构造数据进而伪造成服务端发起请求的漏洞。因为请求是由服务器内部发起,所以一般情况下SSRF漏洞的目标往往是无法从外网访问的内系统。 SSRF漏洞形成的原理多是服务…...
《NoSQL 基础知识总结》
在当今的数据存储和管理领域,NoSQL 数据库正逐渐崭露头角,成为许多应用场景下的有力选择。今天,我们就来一起深入了解一下 NoSQL 的基础知识吧。 一、什么是 NoSQL? NoSQL,即 “Not Only SQL”,它是一种不…...
高校宿舍信息管理系统小程序
作者主页:编程千纸鹤 作者简介:Java领域优质创作者、CSDN博客专家 、CSDN内容合伙人、掘金特邀作者、阿里云博客专家、51CTO特邀作者、多年架构师设计经验、多年校企合作经验,被多个学校常年聘为校外企业导师,指导学生毕业设计并参…...
2.索引:MySQL 索引分类
MySQL中的索引是提高数据查询速度的重要工具,就像一本书的目录,可以帮助我们快速定位到所需的内容。选择适合的索引类型对数据库设计和性能优化至关重要。本文将详细介绍MySQL中常见的索引类型,并重点讲解聚集索引和二级索引的概念及应用。 1…...
sklearn红酒数据集分类器的构建和评估
实验目的: 1. 掌握sklearn科学数据包中决策树和神经网络分类器的构建 2. 掌握对不同分类器进行综合评估 实验数据: 红酒数据集 红酒数据集利用红酒的化学特征来描述三种不同类型的葡萄酒。 实验内容与要求: 解压文件得到wine数据。利用pa…...
【IC验证面试常问-4】
IC验证面试常问-4 1.11 struct和union的异同1.13 rose 和posedge 的区别?1.14 semaphore的用处是什么?1.15 类中的静态方法使用注意事项有哪些?1.16 initial和final的区别? s t o p , stop, stop,finish的区别1.17 logic,wire和re…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
阿里云Ubuntu 22.04 64位搭建Flask流程(亲测)
cd /home 进入home盘 安装虚拟环境: 1、安装virtualenv pip install virtualenv 2.创建新的虚拟环境: virtualenv myenv 3、激活虚拟环境(激活环境可以在当前环境下安装包) source myenv/bin/activate 此时,终端…...
Java 与 MySQL 性能优化:MySQL 慢 SQL 诊断与分析方法详解
文章目录 一、开启慢查询日志,定位耗时SQL1.1 查看慢查询日志是否开启1.2 临时开启慢查询日志1.3 永久开启慢查询日志1.4 分析慢查询日志 二、使用EXPLAIN分析SQL执行计划2.1 EXPLAIN的基本使用2.2 EXPLAIN分析案例2.3 根据EXPLAIN结果优化SQL 三、使用SHOW PROFILE…...
文件上传漏洞防御全攻略
要全面防范文件上传漏洞,需构建多层防御体系,结合技术验证、存储隔离与权限控制: 🔒 一、基础防护层 前端校验(仅辅助) 通过JavaScript限制文件后缀名(白名单)和大小,提…...
6.9本日总结
一、英语 复习默写list11list18,订正07年第3篇阅读 二、数学 学习线代第一讲,写15讲课后题 三、408 学习计组第二章,写计组习题 四、总结 明天结束线代第一章和计组第二章 五、明日计划 英语:复习l默写sit12list17&#…...
