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

相关文章

hdu1254(嵌套bfs,两次bfs)

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

hdu 2489 (dfs枚举 + prim)

题意: 对于一棵顶点和边都有权值的树,使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值,找到一个该图含有m 个顶点的子图,并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析: 因为数据量不大,先用dfs枚举搭配出m个子节点,算出点和,然后套个prim算出边和,每次比较大小即可。 dfs没有写好,A的老泪纵横。 错在把index在d

poj 3050 dfs + set的妙用

题意: 给一个5x5的矩阵,求由多少个由连续6个元素组成的不一样的字符的个数。 解析: dfs + set去重搞定。 代码: #include <iostream>#include <cstdio>#include <set>#include <cstdlib>#include <algorithm>#include <cstring>#include <cm

c++的初始化列表与const成员

初始化列表与const成员 const成员 使用const修饰的类、结构、联合的成员变量,在类对象创建完成前一定要初始化。 不能在构造函数中初始化const成员,因为执行构造函数时,类对象已经创建完成,只有类对象创建完成才能调用成员函数,构造函数虽然特殊但也是成员函数。 在定义const成员时进行初始化,该语法只有在C11语法标准下才支持。 初始化列表 在构造函数小括号后面,主要用于给

ural 1149. Sinus Dances dfs

1149. Sinus Dances Time limit: 1.0 second Memory limit: 64 MB Let  An = sin(1–sin(2+sin(3–sin(4+…sin( n))…) Let  Sn = (…( A 1+ n) A 2+ n–1) A 3+…+2) An+1 For given  N print  SN Input One

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn

Spring+MyBatis+jeasyui 功能树列表

java代码@EnablePaging@RequestMapping(value = "/queryFunctionList.html")@ResponseBodypublic Map<String, Object> queryFunctionList() {String parentId = "";List<FunctionDisplay> tables = query(parent

迭代器模式iterator

学习笔记,原文链接 https://refactoringguru.cn/design-patterns/iterator 不暴露集合底层表现形式 (列表、 栈和树等) 的情况下遍历集合中所有的元素

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

深度优先(DFS)和广度优先(BFS)——算法

深度优先 深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访