2021-8-16 341. 扁平化嵌套列表迭代器(dfs,栈)

2024-03-10 21:18

本文主要是介绍2021-8-16 341. 扁平化嵌套列表迭代器(dfs,栈),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

注:

题目:
给你一个嵌套的整数列表 nestedList 。每个元素要么是一个整数,要么是一个列表;该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化,使之能够遍历这个列表中的所有整数。

实现扁平迭代器类 NestedIterator :

NestedIterator(List 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
嵌套列表中的整数值在范围 [-106, 106] 内

题解:
方法一 dfs
思路
嵌套的整型列表是一个树形结构,树上的叶子节点对应一个整数,非叶节点对应一个列表。

在这棵树上深度优先搜索的顺序就是迭代器遍历的顺序。

我们可以先遍历整个嵌套列表,将所有整数存入一个数组,然后遍历该数组从而实现 next 和 hasNext 方法。

复杂度分析
时间复杂度:初始化为 O(n),next 和 hasNext 为 O(1)。其中 nn 是嵌套的整型列表中的元素个数。

空间复杂度:O(n)。需要一个数组存储嵌套的整型列表中的所有元素。

/*** // This is the interface that allows for creating nested lists.* // You should not implement it, or speculate about its implementation* class NestedInteger {*   public:*     // Return true if this NestedInteger holds a single integer, rather than a nested list.*     bool isInteger() const;**     // Return the single integer that this NestedInteger holds, if it holds a single integer*     // The result is undefined if this NestedInteger holds a nested list*     int getInteger() const;**     // Return the nested list that this NestedInteger holds, if it holds a nested list*     // The result is undefined if this NestedInteger holds a single integer*     const vector<NestedInteger> &getList() const;* };*/class NestedIterator {
public:vector<int> result;vector<int>::iterator cur;void dfs(vector<NestedInteger> lists){for(auto list:lists){if(list.isInteger()){result.push_back(list.getInteger());}else{dfs(list.getList());}}} NestedIterator(vector<NestedInteger> &nestedList) {dfs(nestedList);cur=result.begin();}int next() {return *(cur++);}bool hasNext() {return cur!=result.end();}
};/*** Your NestedIterator object will be instantiated and called as such:* NestedIterator i(nestedList);* while (i.hasNext()) cout << i.next();*/

方法二 栈
思路
我们可以用一个栈来代替方法一中的递归过程。

具体来说,用一个栈来维护深度优先搜索时,从根节点到当前节点路径上的所有节点。由于非叶节点对应的是一个列表,我们在栈中存储的是指向列表当前遍历的元素的指针(下标)。每次向下搜索时,取出列表的当前指针指向的元素并将其入栈,同时将该指针向后移动一位。如此反复直到找到一个整数。循环时若栈顶指针指向了列表末尾,则将其从栈顶弹出。

复杂度分析
时间复杂度:初始化和next 为 O(1),hasNext 为均摊 O(1)。

空间复杂度:O(n)。最坏情况下嵌套的整型列表是一条链,我们需要一个 O(n) 大小的栈来存储链上的所有元素。

/*** // This is the interface that allows for creating nested lists.* // You should not implement it, or speculate about its implementation* class NestedInteger {*   public:*     // Return true if this NestedInteger holds a single integer, rather than a nested list.*     bool isInteger() const;**     // Return the single integer that this NestedInteger holds, if it holds a single integer*     // The result is undefined if this NestedInteger holds a nested list*     int getInteger() const;**     // Return the nested list that this NestedInteger holds, if it holds a nested list*     // The result is undefined if this NestedInteger holds a single integer*     const vector<NestedInteger> &getList() const;* };*/class NestedIterator {
public:stack<pair<vector<NestedInteger>::iterator,vector<NestedInteger>::iterator>> stk;NestedIterator(vector<NestedInteger> &nestedList) {stk.emplace(nestedList.begin(),nestedList.end());}int next() {return stk.top().first++->getInteger();}bool hasNext() {while(!stk.empty()){pair<vector<NestedInteger>::iterator,vector<NestedInteger>::iterator> &p=stk.top();if(p.first==p.second){stk.pop();continue;}// 若当前元素为整数,则返回trueif(p.first->isInteger()==true){return true;}// 若当前元素为列表,则将其入栈,且迭代器p指向下一个元素vector<NestedInteger> &t=p.first++->getList();stk.emplace(t.begin(),t.end());}return false;}
};/*** Your NestedIterator object will be instantiated and called as such:* NestedIterator i(nestedList);* while (i.hasNext()) cout << i.next();*/

这篇关于2021-8-16 341. 扁平化嵌套列表迭代器(dfs,栈)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/795526

相关文章

Python如何计算两个不同类型列表的相似度

《Python如何计算两个不同类型列表的相似度》在编程中,经常需要比较两个列表的相似度,尤其是当这两个列表包含不同类型的元素时,下面小编就来讲讲如何使用Python计算两个不同类型列表的相似度吧... 目录摘要引言数字类型相似度欧几里得距离曼哈顿距离字符串类型相似度Levenshtein距离Jaccard相

Redis存储的列表分页和检索的实现方法

《Redis存储的列表分页和检索的实现方法》在Redis中,列表(List)是一种有序的数据结构,通常用于存储一系列元素,由于列表是有序的,可以通过索引来访问元素,因此可以很方便地实现分页和检索功能,... 目录一、Redis 列表的基本操作二、分页实现三、检索实现3.1 方法 1:客户端过滤3.2 方法

windos server2022里的DFS配置的实现

《windosserver2022里的DFS配置的实现》DFS是WindowsServer操作系统提供的一种功能,用于在多台服务器上集中管理共享文件夹和文件的分布式存储解决方案,本文就来介绍一下wi... 目录什么是DFS?优势:应用场景:DFS配置步骤什么是DFS?DFS指的是分布式文件系统(Distr

C#使用yield关键字实现提升迭代性能与效率

《C#使用yield关键字实现提升迭代性能与效率》yield关键字在C#中简化了数据迭代的方式,实现了按需生成数据,自动维护迭代状态,本文主要来聊聊如何使用yield关键字实现提升迭代性能与效率,感兴... 目录前言传统迭代和yield迭代方式对比yield延迟加载按需获取数据yield break显式示迭

Spring常见错误之Web嵌套对象校验失效解决办法

《Spring常见错误之Web嵌套对象校验失效解决办法》:本文主要介绍Spring常见错误之Web嵌套对象校验失效解决的相关资料,通过在Phone对象上添加@Valid注解,问题得以解决,需要的朋... 目录问题复现案例解析问题修正总结  问题复现当开发一个学籍管理系统时,我们会提供了一个 API 接口去

Python实现将实体类列表数据导出到Excel文件

《Python实现将实体类列表数据导出到Excel文件》在数据处理和报告生成中,将实体类的列表数据导出到Excel文件是一项常见任务,Python提供了多种库来实现这一目标,下面就来跟随小编一起学习一... 目录一、环境准备二、定义实体类三、创建实体类列表四、将实体类列表转换为DataFrame五、导出Da

使用JavaScript将PDF页面中的标注扁平化的操作指南

《使用JavaScript将PDF页面中的标注扁平化的操作指南》扁平化(flatten)操作可以将标注作为矢量图形包含在PDF页面的内容中,使其不可编辑,DynamsoftDocumentViewer... 目录使用Dynamsoft Document Viewer打开一个PDF文件并启用标注添加功能扁平化

Python中列表的高级索引技巧分享

《Python中列表的高级索引技巧分享》列表是Python中最常用的数据结构之一,它允许你存储多个元素,并且可以通过索引来访问这些元素,本文将带你深入了解Python列表的高级索引技巧,希望对... 目录1.基本索引2.切片3.负数索引切片4.步长5.多维列表6.列表解析7.切片赋值8.删除元素9.反转列表

SpringBoot嵌套事务详解及失效解决方案

《SpringBoot嵌套事务详解及失效解决方案》在复杂的业务场景中,嵌套事务可以帮助我们更加精细地控制数据的一致性,然而,在SpringBoot中,如果嵌套事务的配置不当,可能会导致事务不生效的问题... 目录什么是嵌套事务?嵌套事务失效的原因核心问题:嵌套事务的解决方案方案一:将嵌套事务方法提取到独立类

hdu1254(嵌套bfs,两次bfs)

/*第一次做这种题感觉很有压力,思路还是有点混乱,总是wa,改了好多次才ac的思路:把箱子的移动当做第一层bfs,队列节点要用到当前箱子坐标(x,y),走的次数step,当前人的weizhi(man_x,man_y),要判断人能否将箱子推到某点时要嵌套第二层bfs(人的移动);代码如下: