leetcode 341 Flatten Nested List Iterator 以及其他Iter

chaosx110 发布于2019-08-14 18:00 / 900人阅读

摘要：返回的是表示是否走到了结尾。起到的就是缓存作用，因为调用之后马上就走到下一个了。如果调用，返回用得到和最初的输入相同的做相同的步骤存入不断拆开得到结果。思想就是来自括号，后面也会跟进的专题

Iterator其实就是一个单链表，无法回头看。java里很多数据结构都有这个接口，使用时需要initalize,得到一个iterator.
调用next()返回的是一个object, 指向的是下一个未访问过的部分。
hasnext()返回的是boolean, 表示是否走到了结尾。

284 Peeking Iterator

class PeekingIterator implements Iterator {
    Iterator iter;
    Integer next = null;    // 起到的就是缓存作用，因为next()调用之后马上就走到下一个object了。
    
    public PeekingIterator(Iterator iterator) {
        // initialize any member here.
        iter = iterator;
        if(iter.hasNext()){
            next = iter.next();
        }
    }

    // Returns the next element in the iteration without advancing the iterator.
    public Integer peek() {
        return next;
    }

    // hasNext() and next() should behave the same as in the Iterator interface.
    // Override them if needed.
    @Override
    public Integer next() {
        Integer res = next;
        next = iter.hasNext() ? iter.next() : null;
        return res;
    }

    @Override
    public boolean hasNext() {
        return next != null;
    }
}

281 Zigzag Iterator

public class ZigzagIterator {
    Queue list;
    
    public ZigzagIterator(List v1, List v2) {
        list = new LinkedList();
        if(!v1.isEmpty()) list.add(v1.iterator());
        if(!v2.isEmpty()) list.add(v2.iterator());
        // 如果给的是k个list, List> vs, 只需要把所有v1,v1...vk生成iterator放到q里
        // for(List v: List>) if(!v.isEmpty()) list.add(v.iterator());
    }

    public int next() {
        Iterator iter = list.poll();
        int res = (Integer) iter.next();
        if(iter.hasNext()) list.offer(iter);
        return res;
    }

    public boolean hasNext() {
        return !list.isEmpty();
    }
}

Zigzag Iterator这个题目和merge k sorted list很像，design twitter用到的就是merge k sorted list的思想加上OOD，会另写一篇。

173 BST Iterator

戳这里，BST inorder小专题。
bst iterator

341 Flatten Nested List Iterator

题目的意思定义了一个特殊的数据结构，用括号形成很多层，按从左到右的顺序输出。
括号是个强提示，要把括号里的东西拆开还保持原来的顺序，就需要用stack处理。
[1,[4,[6]]] 存到stack里，变成|[4,[6]], [1]|
栈顶调用isInteger()，返回true, 就要getInteger()输出。
如果调用isInteger()，返回false, 用getList()得到和最初的输入相同的list,做相同的步骤存入stack.
不断拆开NestedInteger, 得到结果。
这题就是给的API有点多，需要读懂题意，然后再拆开得到结果。stack思想就是来自括号，后面也会跟进stack的专题.

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List getList();
 * }
 */
public class NestedIterator implements Iterator {
    ArrayDeque stk;
    
    public NestedIterator(List nestedList) {
        stk = new ArrayDeque();
        for(int i = nestedList.size()-1; i >= 0; i--){
            stk.addLast(nestedList.get(i));
        }
    }

    @Override
    public Integer next() {
        return stk.pollLast().getInteger();
    }

    @Override
    public boolean hasNext() {
        while(!stk.isEmpty()){
            NestedInteger cur = stk.peekLast();
            if(cur.isInteger()){
                return true;
            }
            List list = stk.pollLast().getList();
            for(int i=list.size()-1; i>=0; i--){
                stk.addLast(list.get(i));
            }
        }
        return false;
    }
}```

服务器托管超融合服务器以及其他 Flatten okhttp341 Nested

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

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

leetcode341. Flatten Nested List Iterator

摘要：题目要求假设有一个嵌套形式的数组，要求按照顺序遍历数组中的元素。思路和代码首先可以想到通过深度优先递归的方式将嵌套形式的数组展开为一个无嵌套的列表。题目要求 Given a nested list of integers, implement an iterator to flatten it. Each element is either an integer, or a lis...

MartinHan 2019-08-15 15:54 评论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
Python 迭代器、生成器和列表解析

摘要：迭代器迭代器在版本中被加入它为类序列对象提供了一个类序列的接口。其中方法返回迭代器对象本身方法返回容器的下一个元素，在结尾时引发异常。迭代器协议迭代器协议即实现与方法。迭代器迭代器在 Python 2.2 版本中被加入, 它为类序列对象提供了一个类序列的接口。 Python 的迭代无缝地支持序列对象, 而且它还允许迭代非序列类型, 包括用户定义的对象。即迭代器可以迭代不是序列但表现...

dreamGong 2019-07-31 10:01 评论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