当前位置: 首页 > news >正文

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^4
  • s 由数字、方括号 "[]"、负号 '-' 、逗号 ','组成
  • 用例保证 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 表示一个整数嵌套列表&#xff0c;实现一个解析它的语法分析器并返回解析的结果 NestedInteger 。 列表中的每个元素只可能是整数或整数嵌套列表 示例 1&#xff1a; 输入&#xff1a;s "324", 输出&#xff1a;324 解释&#xff…...

Unity WebGL交互通信

Unity 调用 H5 本文使用的 unity 版本为&#xff1a;2021.3.3 1.在unity中通过c#的特性DllImport导出外部实现函数 [DllImport("__Internal")]private static extern void callJsString(string param);[DllImport("__Internal")]private static extern vo…...

王道考研之数据结构

数据结构系列 提示&#xff1a;这里可以添加系列文章的所有文章的目录&#xff0c;目录需要自己手动添加 数据结构 数据结构系列1.线性表1.1 线性表的定义和相关概念1.2 线性表的创销 增删查改 判空表长打印 2.顺序表2.1 顺序表定义和相关概念2.2 顺序表的静态实现2.3 顺序表的…...

实习冲刺Day17

算法题 x的平方根 69. x 的平方根 - 力扣&#xff08;LeetCode&#xff09; 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 //注册账号时&#xff0c;给密码加密 password是前端传过来的密码&#xff0c;hashPassword是存到数据库中的密码 const bcrypt require(bcrypt) const hashPassword bcrypt.hash(password,10) //登…...

岛屿数量问题

给一个0 1矩阵&#xff0c;1代表是陆地&#xff0c;0代表海洋&#xff0c; 如果两个1相邻&#xff0c;那么这两个1属于同一个岛。我们只考虑上下左右为相邻。 岛屿问题: 相邻陆地可以组成一个岛屿&#xff08;相邻:上下左右&#xff09; 判断岛屿个数。 C 解决方案 #include &…...

智能制造基础- TPM(全面生产维护)

TPM 前言一、TPM二、TPM实施步骤三、 消除主要问题3.1 实施指南3.2 如何进行“主要问题”的消除&#xff1f; 四、自主维护4.1 实施指南4.2 主要工作内容4.3 如何进行“自主维护“ 五、计划维护5.1 实施指南5.2 如何实施计划维护 六、TPM 适当的 设备 设计5.1 实施指南5.2 如何…...

C++学习笔记----11、模块、头文件及各种主题(一)---- 模板概览与类模板(4)

2.2.2、显式实例化 有危险存在于有些类模板成员函数的编译错误&#xff0c;在隐式实例化时没有注意到。未被使用的类模板成员函数也可能包含语法错误&#xff0c;因为它们不会被编译到。这会使得检测代码的语法错误很困难。可以强制编译器生成所有成员函数的代码&#xff0c;vi…...

【力扣热题100】[Java版] 刷题笔记-160. 相交链表

题目&#xff1a;160. 相交链表 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点&#xff0c;返回 null 。 图示两个链表在节点 c1 开始相交&#xff1a; 题目数据 保证 整个链式结构中不存在环。 注意…...

多线程和线程同步复习

多线程和线程同步复习 进程线程区别创建线程线程退出线程回收全局写法传参写法 线程分离线程同步同步方式 互斥锁互斥锁进行线程同步 死锁读写锁api细说读写锁进行线程同步 条件变量生产者消费者案例问题解答加强版生产者消费者 总结信号量信号量实现生产者消费者同步-->一个…...

贝式计算的 AI4S 观察:使用机器学习对世界进行感知与推演,最大魅力在于横向扩展的有效性

「传统研究方法高度依赖于科研人员自身的特征和问题定义能力&#xff0c;通常采用小数据&#xff0c;在泛化能力和拓展能力上存疑。而 AI 研究方法则需要引入大规模、高质量数据&#xff0c;并采用机器学习进行特征抽取&#xff0c;这使得产生的科研结果在真实世界的问题中非常…...

容器化技术入门:Docker详解

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 容器化技术入门&#xff1a;Docker详解 容器化技术入门&#xff1a;Docker详解 容器化技术入门&#xff1a;Docker详解 引言 Doc…...

基于SSM(Spring + Spring MVC + MyBatis)框架的药房管理系统

基于SSM&#xff08;Spring Spring MVC MyBatis&#xff09;框架的药房管理系统 项目概述 功能需求 用户管理&#xff1a;管理员可以添加、删除、修改和查询用户信息。药品管理&#xff1a;支持对药品信息的增删改查操作&#xff0c;包括药品名称、价格、库存量等。供应商…...

在服务器里安装2个conda

1、安装新的conda 下载地址&#xff1a;Index of /anaconda/archive/ | 清华大学开源软件镜像站 | Tsinghua Open Source Mirror 本文选择&#xff1a;Anaconda3-2023.03-1-Linux-x86_64.sh 安装&#xff1a;Ubuntu安装Anaconda详细步骤&#xff08;Ubuntu22.04.1&#xff…...

web安全漏洞之ssrf入门

web安全漏洞之ssrf入门 1.什么是ssrf SSRF(Server Side Request Forgery,服务端请求伪造)是一种通过构造数据进而伪造成服务端发起请求的漏洞。因为请求是由服务器内部发起&#xff0c;所以一般情况下SSRF漏洞的目标往往是无法从外网访问的内系统。 SSRF漏洞形成的原理多是服务…...

《NoSQL 基础知识总结》

在当今的数据存储和管理领域&#xff0c;NoSQL 数据库正逐渐崭露头角&#xff0c;成为许多应用场景下的有力选择。今天&#xff0c;我们就来一起深入了解一下 NoSQL 的基础知识吧。 一、什么是 NoSQL&#xff1f; NoSQL&#xff0c;即 “Not Only SQL”&#xff0c;它是一种不…...

高校宿舍信息管理系统小程序

作者主页&#xff1a;编程千纸鹤 作者简介&#xff1a;Java领域优质创作者、CSDN博客专家 、CSDN内容合伙人、掘金特邀作者、阿里云博客专家、51CTO特邀作者、多年架构师设计经验、多年校企合作经验&#xff0c;被多个学校常年聘为校外企业导师&#xff0c;指导学生毕业设计并参…...

2.索引:MySQL 索引分类

MySQL中的索引是提高数据查询速度的重要工具&#xff0c;就像一本书的目录&#xff0c;可以帮助我们快速定位到所需的内容。选择适合的索引类型对数据库设计和性能优化至关重要。本文将详细介绍MySQL中常见的索引类型&#xff0c;并重点讲解聚集索引和二级索引的概念及应用。 1…...

sklearn红酒数据集分类器的构建和评估

实验目的&#xff1a; 1. 掌握sklearn科学数据包中决策树和神经网络分类器的构建 2. 掌握对不同分类器进行综合评估 实验数据&#xff1a; 红酒数据集 红酒数据集利用红酒的化学特征来描述三种不同类型的葡萄酒。 实验内容与要求&#xff1a; 解压文件得到wine数据。利用pa…...

【IC验证面试常问-4】

IC验证面试常问-4 1.11 struct和union的异同1.13 rose 和posedge 的区别&#xff1f;1.14 semaphore的用处是什么&#xff1f;1.15 类中的静态方法使用注意事项有哪些&#xff1f;1.16 initial和final的区别&#xff1f; s t o p , stop, stop,finish的区别1.17 logic,wire和re…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...