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

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() 方法中检查是否还有未遍历的整数。

以下是具体的步骤:

  1. 在构造函数中,使用一个队列(Queue)来存储扁平化后的整数。队列能够保证我们按照迭代顺序来处理元素。
  2. 使用深度优先搜索(DFS)遍历嵌套列表,每遇到一个整数就将其加入队列中。
  3. 在 next() 方法中,从队列中取出并返回下一个整数。
  4. 在 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)。

五、总结知识点

  1. 接口实现NestedIterator 类实现了 Iterator<Integer> 接口,这意味着它必须实现接口中定义的 next() 和 hasNext() 方法。

  2. 内部类与接口NestedInteger 是一个接口,它定义了嵌套整数的操作,包括检查是否为单个整数以及获取整数值或列表。

  3. 泛型List<NestedInteger> 使用了泛型,它表示列表中存储的是 NestedInteger 类型的对象。

  4. 队列的使用Queue<Integer> 被用来存储扁平化后的整数。队列是一种先进先出(FIFO)的数据结构,在这里用于保持元素的迭代顺序。

  5. 链表数据结构LinkedList 是一种实现了 Queue 接口的类,它以链表的形式存储元素,支持高效的插入和删除操作。

  6. 迭代器遍历:在 flattenList 方法中,使用了增强型 for 循环来遍历 nestedList,这是一种常见的遍历集合的方式。

  7. 递归算法flattenList 方法是一个递归方法,它会递归地处理嵌套列表,直到所有整数都被扁平化到队列中。

  8. 方法重写next() 和 hasNext() 方法被重写以符合 Iterator<Integer> 接口的要求,分别用于获取下一个元素和检查是否还有更多元素。

  9. 条件判断:在 flattenList 方法中,使用了 if-else 语句来判断当前元素是单个整数还是嵌套列表。

  10. 队列操作offer() 方法用于将元素添加到队列的末尾,而 poll() 方法用于从队列的头部移除并返回元素。

  11. 成员变量queue 是 NestedIterator 类的成员变量,它在构造函数中被初始化,并在整个类的生命周期中保持状态。

以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。

相关文章:

LeetCode题练习与总结:扁平化嵌套列表迭代器--341

一、题目描述 给你一个嵌套的整数列表 nestedList 。每个元素要么是一个整数&#xff0c;要么是一个列表&#xff1b;该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化&#xff0c;使之能够遍历这个列表中的所有整数。 实现扁平迭代器类 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实战:从零开始构建简单通信回显程序

目录 前言&#xff1a; 1.实现udpserver类 1.1.创建udp socket 套接字 --- 必须要做的 socket&#xff08;&#xff09;讲解 代码实现&#xff1a;​编辑 代码讲解&#xff1a; 1.2.填充sockaddr_in结构 代码实现&#xff1a; 代码解析&#xff1a; 1.3.bind sockfd和…...

微服务网关Zuul

一、Zuul简介 Zuul是Netflix开源的微服务网关&#xff0c;包含对请求的路由和过滤两个主要功能。 1&#xff09;路由功能&#xff1a;负责将外部请求转发到具体的微服务实例上&#xff0c;是实现外部访问统一入口的基础。 2&#xff09;过滤功能&#xff1a;负责对请求的过程…...

BuildCTF线上赛WP

Build::CTF flag不到啊战队--WP 萌新战队&#xff0c;还请多多指教~ 目录 Build::CTF flag不到啊战队--WP Web ez!http find-the-id Pwn 我要成为沙威玛传奇 Misc what is this? 一念愚即般若绝&#xff0c;一念智即般若生 别真给我开盒了哥 四妹&#xff0c;你听…...

《使用Gin框架构建分布式应用》阅读笔记:p143-p207

《用Gin框架构建分布式应用》学习第10天&#xff0c;p143-p207总结&#xff0c;总计65页。 一、技术总结 1.auth0 本人实际工作中未遇到过&#xff0c;mark一下&#xff0c;参考&#xff1a;https://auth0.com/。 2.使用template (1)c.File() (2)router.Static() (3)rou…...

华为网络管理配置实例

目录 组网需求 数据规划 配置思路 操作步骤 结果验证 配置脚本 管理员可以通过eSight网管系统对FW进行监控和管理&#xff0c;接收FW的告警。 组网需求 如图1所示&#xff0c;某企业在网络边界处部署了FW作为安全网关&#xff0c;并部署了eSight网管系统对网络设备进行集中…...

大语言模型数据处理方法(基于llama模型)

文章目录 前言一、基于huggingface的DataCollatorForSeq2Seq方法解读1、DataCollatorForSeq2Seq方法2、batch最长序列填充3、指定长度填充二、构建大语言模型数据加工模块1、数据读取2、数据加工1、数据格式2、预训练(pretrain)数据加工3、微调(sft)数据加工①、sft数据加工…...

爱奇艺大数据多 AZ 统一调度架构

01# 导语 爱奇艺大数据技术广泛应用于运营决策、用户增长、广告分发、视频推荐、搜索、会员营销等场景&#xff0c;为公司的业务增长和用户体验提供了重要的数据驱动引擎。 多年来&#xff0c;随着公司业务的发展&#xff0c;爱奇艺大数据平台已积累了海量数据&#xff0c;这…...

【C++篇】栈的层叠与队列的流动:在 STL 的韵律中探寻数据结构的优雅之舞

文章目录 C 栈与队列详解&#xff1a;基础与进阶应用前言第一章&#xff1a;栈的介绍与使用1.1 栈的介绍1.2 栈的使用1.2.1 最小栈1.2.2 示例与输出 1.3 栈的模拟实现 第二章&#xff1a;队列的介绍与使用2.1 队列的介绍2.2 队列的使用2.2.1 示例与输出 2.3 队列的模拟实现2.3.…...

使用 Flask 实现简单的登录注册功能

目录 1. 引言 2. 环境准备 3. 数据库设置 4. Flask 应用基本配置 5. 实现用户注册 6. 实现用户登录 7. 路由配置 8. 创建前端页面 9. 结论 1. 引言 在这篇文章中&#xff0c;我们将使用 Flask 框架创建一个简单的登录和注册系统。Flask 是一个轻量级的 Python Web 框架…...

计算机毕业设计Python+大模型微博情感分析 微博舆情预测 微博爬虫 微博大数据 舆情分析系统 大数据毕业设计 NLP文本分类 机器学习 深度学习 AI

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 《Python大模型微博情感分析…...

CTF--Misc题型小结

&#xff08;萌新笔记&#xff0c;多多关照&#xff0c;不足之处请及时提出。&#xff09; 不定时更新~ 目录 密码学相关 文件类型判断 file命令 文件头类型 strings读取 隐写术 尺寸修改 文件头等缺失 EXIF隐写 thumbnail 隐写 文件分离&提取 binwalk foremo…...

深度学习系列——RNN/LSTM/GRU,seq2seq/attention机制

1、RNN/LSTM/GRU可参考&#xff1a; https://zhuanlan.zhihu.com/p/636756912 &#xff08;1&#xff09;对于这里面RNN的表示中&#xff0c;使用了输入x和h的拼接描述&#xff0c;其他公式中也是如此 &#xff08;2&#xff09;各符号图含义如下 2、关于RNN细节&#xff0c;…...

通过call指令来学习指令摘要表的细节

E8 cw cw 表示E8后面跟随2 字节 (什么数不知道) rel16 指在与指令同一代码段内的相对地址偏移 D ,指向Instruction Operand Encoding 表中的D列, 他告诉我们 操作数1 是一个0FFSET N.S. 在64位模式下&#xff0c;某些指令需要使用“地址覆盖前缀”&#xff08;address over…...

10分钟使用Strapi(无头CMS)生成基于Node.js的API接口,告别繁琐开发,保姆级教程,持续更新中。

一、什么是Strapi&#xff1f; Strapi 是一个开源的无头&#xff08;headless&#xff09; CMS&#xff0c;开发者可以自由选择他们喜欢的开发工具和框架&#xff0c;内容编辑人员使用自有的应用程序来管理和分发他们的内容。得益于插件系统&#xff0c;Strapi 是一个灵活的 C…...

创建插件 DLL 项目

Step 1: 创建插件 DLL 项目 在 Visual Studio 中创建一个新的 DLL 项目&#xff0c;并添加以下文件和代码。 头文件&#xff1a;CShapeBase.h cpp 复制代码 #pragma once #include <afxwin.h> // MFC 必需头文件 #include <string> #include <vector> #i…...

OpenCV双目相机外参标定C++

基于OpenCV库实现双目测量系统外参标定过程。通过分析双目测量系统左右相机拍摄的棋盘格标定板图像&#xff0c;包括角点检测、立体标定、立体校正和畸变校正的步骤&#xff0c;获取左右相机的相对位置关系和姿态。 a.检测每张图像中的棋盘格角点&#xff0c;并进行亚像素级精…...

【GESP】C++一级练习BCQM3055,4位数间隔输出

一级知识点取余、整除运算和格式化输出知识点应用。其实也可以用string去处理&#xff0c;那就属于GESP三级的知识点范畴了&#xff0c;孩子暂未涉及。 题目题解详见&#xff1a;https://www.coderli.com/gesp-1-bcqm3055/ https://www.coderli.com/gesp-1-bcqm3055/https://w…...

纯血鸿蒙的最难时刻才开始

关注卢松松&#xff0c;会经常给你分享一些我的经验和观点。 纯血鸿蒙(HarmonyOS NEXT)也正式发布了&#xff0c;绝对是一个历史性时刻&#xff0c;但最难的鸿蒙第二个阶段&#xff0c;也就是生态圈的建设&#xff0c;才刚刚开始。 目前&#xff0c;我劝你现在不要升级到鸿蒙…...

记一个mysql的坑

数据库表user&#xff0c; 存在一个name字段&#xff0c;字段为varchar类型 现在user表有这么两条记录: idnameageclass1NULL18一班2lisi20二班 假如我根据下面这一条件去更新&#xff0c;更新成功数据行显示为0 update user set age 19 where age 18 and class “一班”…...

Java中的设计模式:单例模式详解

摘要 单例模式&#xff08;Singleton Pattern&#xff09;是Java中最常用的设计模式之一&#xff0c;属于创建型模式。它的主要目的是确保一个类在系统中只有一个实例&#xff0c;并提供一个全局访问点来访问该实例。 1. 单例模式的定义 单例模式确保一个类只有一个实例&…...

NanoTrack原理与转tensorrt推理

文章目录 前言一、NanoTrack 工作原理二、运行demo与转换tensorrt模型2.1 运行pt模型demo2.2 转onnx模型2.3 转tensorrt模型2.4 运行trt模型推理 三、推理速度对比总结 前言 NanoTrack 是一种轻量级且高效的目标跟踪算法&#xff0c;基于Siamese网络架构&#xff0c;旨在在资源…...

YOLO11改进 | 卷积模块 | 卷积模块替换为选择性内核SKConv【附完整代码一键运行】

秋招面试专栏推荐 &#xff1a;深度学习算法工程师面试问题总结【百面算法工程师】——点击即可跳转 &#x1f4a1;&#x1f4a1;&#x1f4a1;本专栏所有程序均经过测试&#xff0c;可成功执行&#x1f4a1;&#x1f4a1;&#x1f4a1; 本文给大家带来的教程是将YOLO11的卷积替…...

CentOS进入单用户模式进行密码重置

一、单用户模式介绍 单用户模式是一种特殊的启动模式&#xff0c;主要用于系统维护和故障排除。在单用户模式下&#xff0c;系统以最小化的状态启动&#xff0c;只有最基本的系统服务会被加载&#xff0c;通常只有root用户可以登录。这种模式提供了对系统的完全控制&#xff0…...

bitpoke- mysql-operator cluster

sidecar版本只支持到8.0.35&#xff0c;35可以支持到mysql8.0.35 . 默认镜像是5.7的。需要自己打sidecar的镜像&#xff1a; # Docker image for sidecar containers # https://github.com/bitpoke/mysql-operator/tree/master/images/mysql-operator-sidecar-8.0 # 参考5…...

第5课 基本数据类型

一、数据类型的诞生 在Python的世界里&#xff0c;万物皆对象&#xff0c;每个对象都有自己的若干属性&#xff0c;每一个属性都能描述对象的某一个方面。就像我们每个人&#xff0c;都有自己的身高、年龄、姓名、性别等很多方面的信息&#xff0c;这里的身高、年龄、姓名、性…...

OceanBase 首席科学家阳振坤:大模型时代的数据库思考

2024年 OceanBase 年度大会 即将于10月23日&#xff0c;在北京举行。 欢迎到现场了解更多“SQL AI ” 的探讨与分享&#xff01; 近期&#xff0c;2024年金融业数据库技术大会在北京圆满举行&#xff0c;聚焦“大模型时代下数据库的创新发展”议题&#xff0c;汇聚了国内外众多…...

国内知名的几个镜像源

在国内&#xff0c;有许多常用的Python库镜像源可以帮助加速库的下载。以下是几个知名的镜像源&#xff1a; 1. 清华大学TUNA协会 网址: https://pypi.tuna.tsinghua.edu.cn/simple命令示例:pip install numpy --index-url https://pypi.tuna.tsinghua.edu.cn/simple2. 阿里云…...

如何用群晖做自己的网站/移动端seo关键词优化

SQL循环语句declare i intset i1while i<30begininsert into test (userid) values(i)set ii1end---------------while 条件begin执行操作set ii1endWHILE设置重复执行 SQL 语句或语句块的条件。只要指定的条件为真&#xff0c;就重复执行语句。可以使用 BREAK 和 CONTINUE …...

营销网站制作全包/seo指导

通常网站的性能瓶颈在数据库查询&#xff0c;如果你希望你的网站在一定阶段之内保持稳定&#xff0c;优化你的SQL和数据库是非常必要的一个优化环节。优化数据库是一个很大的话题&#xff0c;这里只是摘要一些比较关键的优化参考建议&#xff0c;并且需要具体分析项目的情况才能…...

大连网站制作.net/全面落实疫情防控优化措施

想要在uniapp中使用echarts&#xff0c;需要进行以下操作步骤&#xff1a; 一&#xff1a;操作步骤 1.定义存放图表的div; 2.引入echarts.min,js,可以去echarts的官网“在线定制”; 3.在需要使用echarts的图表vue页面引入echarts.min.js; 4.开始使用echarts绘制图表&#xff0c…...

中国建设银行重庆网站首页/上海百度提升优化

简介 这里我想说的是&#xff0c;程序本身不需要关心表的结构&#xff0c;只需要按照视图定义来取数据或更新数据。 什么是视图 说起视图呢&#xff0c;就是说它相当于一个虚拟的表&#xff0c;你看不到它&#xff0c;但是你可以根据它来更新和操作表&#xff0c;视图中的wi…...

标题制作网站/100%能上热门的文案

题目链接&#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid1255 求矩形面积的交的线段树题目&#xff0c;刚做了求并的题目&#xff0c;再做这个刚觉良好啊&#xff0c;只要再加一个表示覆盖次数大于1次的长度变量即可 代码&#xff1a; 1 #include<iostream>2 #i…...

二手书哪个网站做的好/付费推广外包

EnableAutoConfiguration注解通常用在Spring Boot项目的主类上&#xff0c;用于启用自动配置。它通过扫描项目中的依赖和类路径配置自动配置Spring应用程序上下文&#xff0c;从而简化了配置过程。这样&#xff0c;您可以快速构建和运行Spring Boot应用程序&#xff0c;而无需手…...