当前位置: 首页 > 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…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...