leetcode341. Flatten Nested List Iterator

MartinHan 發布于2019-08-15 15:54 / 1285人閱讀

摘要：題目要求假設有一個嵌套形式的數組，要求按照順序遍歷數組中的元素。思路和代碼首先可以想到通過深度優先遞歸的方式將嵌套形式的數組展開為一個無嵌套的列表。

題目要求

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

GPU云服務器云服務器 Flatten okhttp341 Nested Iterator

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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