LeetCode题练习与总结:扁平化嵌套列表迭代器--341
一、题目描述
给你一个嵌套的整数列表 nestedList
。每个元素要么是一个整数,要么是一个列表;该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化,使之能够遍历这个列表中的所有整数。
实现扁平迭代器类 NestedIterator
:
NestedIterator(List<NestedInteger> nestedList)
用嵌套列表nestedList
初始化迭代器。int next()
返回嵌套列表的下一个整数。boolean hasNext()
如果仍然存在待迭代的整数,返回true
;否则,返回false
。
你的代码将会用下述伪代码检测:
initialize iterator with nestedList res = [] while iterator.hasNext()append iterator.next() to the end of res return res
如果 res
与预期的扁平化列表匹配,那么你的代码将会被判为正确。
示例 1:
输入:nestedList = [[1,1],2,[1,1]]
输出:[1,1,2,1,1]
解释:通过重复调用 next 直到 hasNext 返回 false,next 返回的元素的顺序应该是: [1,1,2,1,1]
。
示例 2:
输入:nestedList = [1,[4,[6]]]
输出:[1,4,6]
解释:通过重复调用 next 直到 hasNext 返回 false,next 返回的元素的顺序应该是: [1,4,6]
。
提示:
1 <= nestedList.length <= 500
- 嵌套列表中的整数值在范围
[-10^6, 10^6]
内
二、解题思路
为了实现一个能够扁平化嵌套整数列表的迭代器,我们需要在构造函数中预处理整个嵌套列表,将其转换为扁平化的整数列表。然后,在 next()
方法中返回下一个整数,在 hasNext()
方法中检查是否还有未遍历的整数。
以下是具体的步骤:
- 在构造函数中,使用一个队列(Queue)来存储扁平化后的整数。队列能够保证我们按照迭代顺序来处理元素。
- 使用深度优先搜索(DFS)遍历嵌套列表,每遇到一个整数就将其加入队列中。
- 在
next()
方法中,从队列中取出并返回下一个整数。 - 在
hasNext()
方法中,检查队列是否为空,如果不为空则说明还有未遍历的整数。
三、具体代码
import java.util.*;public class NestedIterator implements Iterator<Integer> {private Queue<Integer> queue;public NestedIterator(List<NestedInteger> nestedList) {queue = new LinkedList<>();flattenList(nestedList);}private void flattenList(List<NestedInteger> nestedList) {for (NestedInteger nestedInt : nestedList) {if (nestedInt.isInteger()) {queue.offer(nestedInt.getInteger());} else {flattenList(nestedInt.getList());}}}@Overridepublic Integer next() {return queue.poll();}@Overridepublic boolean hasNext() {return !queue.isEmpty();}
}
在这个实现中,我们首先在构造函数中初始化一个队列,并调用 flattenList
方法来处理整个嵌套列表。在 flattenList
方法中,我们递归地处理每个元素,如果是整数则直接加入队列,如果是列表则继续递归处理。next()
和 hasNext()
方法则直接操作队列,返回下一个整数和检查是否还有未遍历的整数。这样,我们就能通过迭代器来遍历整个扁平化的列表。
四、时间复杂度和空间复杂度
1. 时间复杂度
- 在构造函数中,我们调用了
flattenList
方法来处理整个嵌套列表。这个方法会遍历嵌套列表中的每一个元素。 - 对于每个元素,如果是整数,我们将其加入队列中,这是一个 O(1) 的操作。
- 如果是列表,我们递归调用
flattenList
方法。这意味着我们需要遍历这个子列表中的每一个元素。 - 因此,我们对于每个元素,无论它是整数还是列表,都至少进行一次处理。
- 假设嵌套列表中的元素总数为 N(这包括所有整数和列表中的整数),那么
flattenList
方法将处理每个元素一次,因此时间复杂度为 O(N)。
2. 空间复杂度
- 队列用于存储扁平化后的整数,在最坏情况下,如果嵌套列表中的所有元素都是整数,则队列将存储所有 N 个整数。
- 在递归调用
flattenList
方法时,可能会产生额外的调用栈空间。最坏情况下,如果嵌套列表完全不平衡(例如,每个列表只有一个元素),则递归的深度将达到 N。 - 因此,空间复杂度主要由队列和递归调用栈组成。队列的空间复杂度为 O(N),递归调用栈的空间复杂度在最坏情况下也是 O(N)。
- 综合来看,总的空间复杂度为 O(N)。
五、总结知识点
-
接口实现:
NestedIterator
类实现了Iterator<Integer>
接口,这意味着它必须实现接口中定义的next()
和hasNext()
方法。 -
内部类与接口:
NestedInteger
是一个接口,它定义了嵌套整数的操作,包括检查是否为单个整数以及获取整数值或列表。 -
泛型:
List<NestedInteger>
使用了泛型,它表示列表中存储的是NestedInteger
类型的对象。 -
队列的使用:
Queue<Integer>
被用来存储扁平化后的整数。队列是一种先进先出(FIFO)的数据结构,在这里用于保持元素的迭代顺序。 -
链表数据结构:
LinkedList
是一种实现了Queue
接口的类,它以链表的形式存储元素,支持高效的插入和删除操作。 -
迭代器遍历:在
flattenList
方法中,使用了增强型for
循环来遍历nestedList
,这是一种常见的遍历集合的方式。 -
递归算法:
flattenList
方法是一个递归方法,它会递归地处理嵌套列表,直到所有整数都被扁平化到队列中。 -
方法重写:
next()
和hasNext()
方法被重写以符合Iterator<Integer>
接口的要求,分别用于获取下一个元素和检查是否还有更多元素。 -
条件判断:在
flattenList
方法中,使用了if-else
语句来判断当前元素是单个整数还是嵌套列表。 -
队列操作:
offer()
方法用于将元素添加到队列的末尾,而poll()
方法用于从队列的头部移除并返回元素。 -
成员变量:
queue
是NestedIterator
类的成员变量,它在构造函数中被初始化,并在整个类的生命周期中保持状态。
以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。
相关文章:
LeetCode题练习与总结:扁平化嵌套列表迭代器--341
一、题目描述 给你一个嵌套的整数列表 nestedList 。每个元素要么是一个整数,要么是一个列表;该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化,使之能够遍历这个列表中的所有整数。 实现扁平迭代器类 NestedIterato…...
51单片机快速入门之 AD(模数) DA(数模) 转换 2024/10/25
51单片机快速入门之 AD(模数) DA(数模) 转换 2024/10/25 声明:本文图片来源于网络 A模拟信号特点: 电压或者电流 缓慢上升 随着时间连续缓慢上升或下降 D数字信号特点:电压或者电流 保持一段时间的高/低电平 状态 / 突变 (高电压瞬间低电压) 数字电路中 通常将0-1v电压称…...
Typora 、 Minio and PicGo 图床搭建
流程介绍 本地安装Typora笔记工具拥有一台装有docker的服务器配置minio云图床管理控制页面下载PicGo上传工具服务器Docker环境搭建—Ubuntu系统 删除旧docker的所有依赖(非root用户) # 删除docker及安装时自动安装的所有包 sudo apt-get autoremove docker docker-ce docker…...
【计网】UDP Echo Server与Client实战:从零开始构建简单通信回显程序
目录 前言: 1.实现udpserver类 1.1.创建udp socket 套接字 --- 必须要做的 socket()讲解 代码实现:编辑 代码讲解: 1.2.填充sockaddr_in结构 代码实现: 代码解析: 1.3.bind sockfd和…...
微服务网关Zuul
一、Zuul简介 Zuul是Netflix开源的微服务网关,包含对请求的路由和过滤两个主要功能。 1)路由功能:负责将外部请求转发到具体的微服务实例上,是实现外部访问统一入口的基础。 2)过滤功能:负责对请求的过程…...
BuildCTF线上赛WP
Build::CTF flag不到啊战队--WP 萌新战队,还请多多指教~ 目录 Build::CTF flag不到啊战队--WP Web ez!http find-the-id Pwn 我要成为沙威玛传奇 Misc what is this? 一念愚即般若绝,一念智即般若生 别真给我开盒了哥 四妹,你听…...
《使用Gin框架构建分布式应用》阅读笔记:p143-p207
《用Gin框架构建分布式应用》学习第10天,p143-p207总结,总计65页。 一、技术总结 1.auth0 本人实际工作中未遇到过,mark一下,参考:https://auth0.com/。 2.使用template (1)c.File() (2)router.Static() (3)rou…...
华为网络管理配置实例
目录 组网需求 数据规划 配置思路 操作步骤 结果验证 配置脚本 管理员可以通过eSight网管系统对FW进行监控和管理,接收FW的告警。 组网需求 如图1所示,某企业在网络边界处部署了FW作为安全网关,并部署了eSight网管系统对网络设备进行集中…...
大语言模型数据处理方法(基于llama模型)
文章目录 前言一、基于huggingface的DataCollatorForSeq2Seq方法解读1、DataCollatorForSeq2Seq方法2、batch最长序列填充3、指定长度填充二、构建大语言模型数据加工模块1、数据读取2、数据加工1、数据格式2、预训练(pretrain)数据加工3、微调(sft)数据加工①、sft数据加工…...
爱奇艺大数据多 AZ 统一调度架构
01# 导语 爱奇艺大数据技术广泛应用于运营决策、用户增长、广告分发、视频推荐、搜索、会员营销等场景,为公司的业务增长和用户体验提供了重要的数据驱动引擎。 多年来,随着公司业务的发展,爱奇艺大数据平台已积累了海量数据,这…...
【C++篇】栈的层叠与队列的流动:在 STL 的韵律中探寻数据结构的优雅之舞
文章目录 C 栈与队列详解:基础与进阶应用前言第一章:栈的介绍与使用1.1 栈的介绍1.2 栈的使用1.2.1 最小栈1.2.2 示例与输出 1.3 栈的模拟实现 第二章:队列的介绍与使用2.1 队列的介绍2.2 队列的使用2.2.1 示例与输出 2.3 队列的模拟实现2.3.…...
使用 Flask 实现简单的登录注册功能
目录 1. 引言 2. 环境准备 3. 数据库设置 4. Flask 应用基本配置 5. 实现用户注册 6. 实现用户登录 7. 路由配置 8. 创建前端页面 9. 结论 1. 引言 在这篇文章中,我们将使用 Flask 框架创建一个简单的登录和注册系统。Flask 是一个轻量级的 Python Web 框架…...
计算机毕业设计Python+大模型微博情感分析 微博舆情预测 微博爬虫 微博大数据 舆情分析系统 大数据毕业设计 NLP文本分类 机器学习 深度学习 AI
温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 《Python大模型微博情感分析…...
CTF--Misc题型小结
(萌新笔记,多多关照,不足之处请及时提出。) 不定时更新~ 目录 密码学相关 文件类型判断 file命令 文件头类型 strings读取 隐写术 尺寸修改 文件头等缺失 EXIF隐写 thumbnail 隐写 文件分离&提取 binwalk foremo…...
深度学习系列——RNN/LSTM/GRU,seq2seq/attention机制
1、RNN/LSTM/GRU可参考: https://zhuanlan.zhihu.com/p/636756912 (1)对于这里面RNN的表示中,使用了输入x和h的拼接描述,其他公式中也是如此 (2)各符号图含义如下 2、关于RNN细节,…...
通过call指令来学习指令摘要表的细节
E8 cw cw 表示E8后面跟随2 字节 (什么数不知道) rel16 指在与指令同一代码段内的相对地址偏移 D ,指向Instruction Operand Encoding 表中的D列, 他告诉我们 操作数1 是一个0FFSET N.S. 在64位模式下,某些指令需要使用“地址覆盖前缀”(address over…...
10分钟使用Strapi(无头CMS)生成基于Node.js的API接口,告别繁琐开发,保姆级教程,持续更新中。
一、什么是Strapi? Strapi 是一个开源的无头(headless) CMS,开发者可以自由选择他们喜欢的开发工具和框架,内容编辑人员使用自有的应用程序来管理和分发他们的内容。得益于插件系统,Strapi 是一个灵活的 C…...
创建插件 DLL 项目
Step 1: 创建插件 DLL 项目 在 Visual Studio 中创建一个新的 DLL 项目,并添加以下文件和代码。 头文件:CShapeBase.h cpp 复制代码 #pragma once #include <afxwin.h> // MFC 必需头文件 #include <string> #include <vector> #i…...
OpenCV双目相机外参标定C++
基于OpenCV库实现双目测量系统外参标定过程。通过分析双目测量系统左右相机拍摄的棋盘格标定板图像,包括角点检测、立体标定、立体校正和畸变校正的步骤,获取左右相机的相对位置关系和姿态。 a.检测每张图像中的棋盘格角点,并进行亚像素级精…...
【GESP】C++一级练习BCQM3055,4位数间隔输出
一级知识点取余、整除运算和格式化输出知识点应用。其实也可以用string去处理,那就属于GESP三级的知识点范畴了,孩子暂未涉及。 题目题解详见:https://www.coderli.com/gesp-1-bcqm3055/ https://www.coderli.com/gesp-1-bcqm3055/https://w…...
纯血鸿蒙的最难时刻才开始
关注卢松松,会经常给你分享一些我的经验和观点。 纯血鸿蒙(HarmonyOS NEXT)也正式发布了,绝对是一个历史性时刻,但最难的鸿蒙第二个阶段,也就是生态圈的建设,才刚刚开始。 目前,我劝你现在不要升级到鸿蒙…...
记一个mysql的坑
数据库表user, 存在一个name字段,字段为varchar类型 现在user表有这么两条记录: idnameageclass1NULL18一班2lisi20二班 假如我根据下面这一条件去更新,更新成功数据行显示为0 update user set age 19 where age 18 and class “一班”…...
Java中的设计模式:单例模式详解
摘要 单例模式(Singleton Pattern)是Java中最常用的设计模式之一,属于创建型模式。它的主要目的是确保一个类在系统中只有一个实例,并提供一个全局访问点来访问该实例。 1. 单例模式的定义 单例模式确保一个类只有一个实例&…...
NanoTrack原理与转tensorrt推理
文章目录 前言一、NanoTrack 工作原理二、运行demo与转换tensorrt模型2.1 运行pt模型demo2.2 转onnx模型2.3 转tensorrt模型2.4 运行trt模型推理 三、推理速度对比总结 前言 NanoTrack 是一种轻量级且高效的目标跟踪算法,基于Siamese网络架构,旨在在资源…...
YOLO11改进 | 卷积模块 | 卷积模块替换为选择性内核SKConv【附完整代码一键运行】
秋招面试专栏推荐 :深度学习算法工程师面试问题总结【百面算法工程师】——点击即可跳转 💡💡💡本专栏所有程序均经过测试,可成功执行💡💡💡 本文给大家带来的教程是将YOLO11的卷积替…...
CentOS进入单用户模式进行密码重置
一、单用户模式介绍 单用户模式是一种特殊的启动模式,主要用于系统维护和故障排除。在单用户模式下,系统以最小化的状态启动,只有最基本的系统服务会被加载,通常只有root用户可以登录。这种模式提供了对系统的完全控制࿰…...
bitpoke- mysql-operator cluster
sidecar版本只支持到8.0.35,35可以支持到mysql8.0.35 . 默认镜像是5.7的。需要自己打sidecar的镜像: # Docker image for sidecar containers # https://github.com/bitpoke/mysql-operator/tree/master/images/mysql-operator-sidecar-8.0 # 参考5…...
第5课 基本数据类型
一、数据类型的诞生 在Python的世界里,万物皆对象,每个对象都有自己的若干属性,每一个属性都能描述对象的某一个方面。就像我们每个人,都有自己的身高、年龄、姓名、性别等很多方面的信息,这里的身高、年龄、姓名、性…...
OceanBase 首席科学家阳振坤:大模型时代的数据库思考
2024年 OceanBase 年度大会 即将于10月23日,在北京举行。 欢迎到现场了解更多“SQL AI ” 的探讨与分享! 近期,2024年金融业数据库技术大会在北京圆满举行,聚焦“大模型时代下数据库的创新发展”议题,汇聚了国内外众多…...
国内知名的几个镜像源
在国内,有许多常用的Python库镜像源可以帮助加速库的下载。以下是几个知名的镜像源: 1. 清华大学TUNA协会 网址: https://pypi.tuna.tsinghua.edu.cn/simple命令示例:pip install numpy --index-url https://pypi.tuna.tsinghua.edu.cn/simple2. 阿里云…...
深圳华企立方/英文网站seo
DOM概述 什么是DOM?DOM和JavaScriptDOM的数据类型DOM常用核心接口 什么是DOM? 1.文档对象模型 (DOM) 是HTML和XML文档的编程接口 。它提供了对文档的结构化的表述,并定义了一种方式可以使从程序中对该结构进行访问,从而改变文档…...
长沙网站建立公司/营销网店推广的软文
1、动态投影(ArcMap)所谓动态投影是指ArcMap中的Data空间参考或是说坐标系统是默认为第一加载到当前工作区的那个文件的坐标系统,后加入的数据如果和当前工作区坐标系统不相同,则ArcMap会自动做投影变换,把后加入的数据投影变换到当前坐标系统…...
wordpress 内容隐藏/seo网站推广软件 快排
I、数据库使用版本信息 neo4j 3.1.0 社区版本 neo4j 4.0.9 社区版本 neo4j 4.2.11 企业版本 II、Neo4j 4.2.11企业版本 主要用作性能测试: 参考:Database management - Neo4j Cypher Manual III、数据库操作 0、数据库browser 查询结果配置 显示所有配…...
wordpress 安卓接口/全球搜索引擎市场份额
1,在扩展节点M时,计算了其后继节点N的F值,发现N节点已经在open链表中,并且新的F值小于老的F值,但是此时不进行F值的更新,那么修改过的算法正确吗?很简单不正确的,看下面这个图 图…...
学校网站建设作用/衡阳网站建设
前言 自定义 View 时Android 开发中的一个热点知识,我们结合源码了解绘制 View 的必备知识。 流程 measure 测量layout 位置draw 绘制 measure 测量 view 大小的测量是在 onMeasure 中实现的,测量过程用到了MeasureSpac,MeasureSpec是一…...
微商怎么做网站/成都移动seo
一.问答题1. 简述电子计算机的用途和特点。电子计算机的用途非常广泛,主要应用领域有:(1)科学计算。 (2)自动控制。(3)信息处理。(4)计算机辅助设计。(5)人工智能。 (6)网络通信。(7)多媒体技术。电子计算机的特点主要有如下几点:…...