leetcode341. Flatten Nested List Iterator

MartinHan 发布于2019-08-15 15:54 / 1186人阅读

摘要：题目要求假设有一个嵌套形式的数组，要求按照顺序遍历数组中的元素。思路和代码首先可以想到通过深度优先递归的方式将嵌套形式的数组展开为一个无嵌套的列表。

题目要求

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Example 1:
Given the list [[1,1],2,[1,1]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:
Given the list [1,[4,[6]]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

假设有一个嵌套形式的数组，要求按照顺序遍历数组中的元素。

思路和代码

首先可以想到通过深度优先递归的方式将嵌套形式的数组展开为一个无嵌套的列表。那么有没有方法实现不将元素取出而是直接迭代的方式获取下一个元素呢？这里采用了嵌套迭代器的方式进行遍历

    public class FlattenNestedListIterator_341 implements Iterator{

        private List nestedList;
        private Iterator iterator;
        private int next;
        private int index;
        public FlattenNestedListIterator_341(List nestedList){
            this.nestedList = nestedList;
        }
        
         @Override
        public Integer next() {
             return next;
        }

        @Override
        public boolean hasNext() {
            if(iterator != null && iterator.hasNext()){
                this.next = iterator.next();
                return true;
            }
            
            if(index>=nestedList.size()){
                return false;
            }
            
            NestedInteger n = nestedList.get(index++);
            if(n.isInteger()){
                next = n.getInteger();
            }else{
                iterator = new FlattenNestedListIterator_341(n.getList());
                if(iterator.hasNext()){
                    next = iterator.next();
                }else{
                    return hasNext();
                }
            }
            return true;
        }
}

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~s

idc机房托管混合云 Flatten okhttp341 Nested Iterator

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69315.html

leetcode 341 Flatten Nested List Iterator 以及其他Iter

摘要：返回的是表示是否走到了结尾。起到的就是缓存作用，因为调用之后马上就走到下一个了。如果调用，返回用得到和最初的输入相同的做相同的步骤存入不断拆开得到结果。思想就是来自括号，后面也会跟进的专题 Iterator其实就是一个单链表，无法回头看。java里很多数据结构都有这个接口，使用时需要initalize,得到一个iterator. 调用next()返回的是一个object, 指向的是下一...

chaosx110 2019-08-14 18:00 评论0 收藏0
LeetCode 341. Flatten Nested List Iterator

摘要：设计一个迭代器，使其能够遍历这个整型列表中的所有整数。列表中的项或者为一个整数，或者是另一个列表。示例输入输出解释通过重复调用直到返回，返回的元素的顺序应该是。 Description Given a nested list of integers, implement an iterator to flatten it. Each element is either an integ...

mingzhong 2019-07-31 10:16 评论0 收藏0
[LintCode/LeetCode] Flatten Nested List Iterator

摘要：首先，根据迭代器需要不断返回下一个元素，确定用堆栈来做。堆栈初始化数据结构，要先从后向前向堆栈压入中的元素。在调用之前，先要用判断下一个是还是，并进行的操作对要展开并顺序压入对直接返回。 Problem Given a nested list of integers, implement an iterator to flatten it. Each element is either...

spacewander 2019-08-14 15:45 评论0 收藏0
[Leetcode] Flatten 2D Vector 整平二维向量

摘要：另一个则是的迭代器，它负责记录当前到哪一个的迭代器了。每次时，我们先调用一下，确保当前的迭代器有下一个值。代码当前列表的迭代器为空，或者当前迭代器中没有下一个值时，需要更新为下一个迭代器 Flatten 2D Vector Implement an iterator to flatten a 2d vector. For example, Given 2d vector = [ ...

MageekChiu 2019-08-14 12:36 评论0 收藏0
[LeetCode] 251. Flatten 2D Vector

Problem Implement an iterator to flatten a 2d vector. Example: Input: 2d vector = [ [1,2], [3], [4,5,6] ] Output: [1,2,3,4,5,6] Explanation: By calling next repeatedly until hasNext returns fals...

curried 2019-08-16 13:30 评论0 收藏0