LeetCode:扁平化嵌套列表迭代器_341

思路

这题我使用了两种解法

遍历N叉树

首先分析题目得知,该数据结构是N叉树,需要的是所有叶子节点

迭代器惰性求值

  • 从时间复杂度的角度来看,遍历N叉树为O(N),遍历了所有节点,但我们是不需要非叶子节点的,不过要得到叶子结点,不得不遍历非叶子结点,所以没有提升空间了。
  • 从空间复杂度的角度来看,提前遍历出所有叶子结点放到数组里,这里就可以优化。优化方向:惰性求值(stream也是惰性求值)。

题目

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

实现扁平迭代器类 NestedIterator

  • NestedIterator(List<NestedInteger> 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]
Related Topics
  • 深度优先搜索
  • 设计
  • 队列
  • 迭代器
  • 👍 388
  • 👎 0
  • 代码

        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 empty list if this NestedInteger holds a single integer
            public List<NestedInteger> getList();
        }
    
        public class NestedIterator implements Iterator<Integer> {
            private List<NestedInteger> temp;
    
            public NestedIterator(List<NestedInteger> nestedList) {
                temp = new LinkedList<>(nestedList);
            }
    
            @Override
            public boolean hasNext() {
                while (!temp.isEmpty() && !temp.get(0).isInteger()) {
                    List<NestedInteger> firstList = temp.remove(0).getList();
                    for (int i = firstList.size() - 1; i >= 0; i--) {
                        temp.add(0, firstList.get(i));
                    }
                }
                return !temp.isEmpty();
            }
    
            @Override
            public Integer next() {
                return temp.remove(0).getInteger();
            }
        }
    
        public class NestedIterator implements Iterator<Integer> {
    
            private Iterator<Integer> iterator;
            private List<Integer> result;
    
            public NestedIterator(List<NestedInteger> nestedList) {
                result = new ArrayList<>();
                for (NestedInteger item : nestedList) {
                    traverse(item);
                }
                iterator = result.iterator();
            }
    
            public void traverse(NestedInteger nestedInteger) {
                if (nestedInteger.isInteger()) {
                    result.add(nestedInteger.getInteger());
                    return;
                }
                for (NestedInteger item : nestedInteger.getList()) {
                    traverse(item);
                }
            }
    
            @Override
            public Integer next() {
                return iterator.next();
            }
    
            @Override
            public boolean hasNext() {
                return iterator.hasNext();
            }
    作者:Yuyy
    博客:https://yuyy.info
    暂无评论

    发送评论 编辑评论

    
    				
    |´・ω・)ノ
    ヾ(≧∇≦*)ゝ
    (☆ω☆)
    (╯‵□′)╯︵┴─┴
     ̄﹃ ̄
    (/ω\)
    ∠( ᐛ 」∠)_
    (๑•̀ㅁ•́ฅ)
    →_→
    ୧(๑•̀⌄•́๑)૭
    ٩(ˊᗜˋ*)و
    (ノ°ο°)ノ
    (´இ皿இ`)
    ⌇●﹏●⌇
    (ฅ´ω`ฅ)
    (╯°A°)╯︵○○○
    φ( ̄∇ ̄o)
    ヾ(´・ ・`。)ノ"
    ( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
    (ó﹏ò。)
    Σ(っ °Д °;)っ
    ( ,,´・ω・)ノ"(´っω・`。)
    ╮(╯▽╰)╭
    o(*////▽////*)q
    >﹏<
    ( ๑´•ω•) "(ㆆᴗㆆ)
    😂
    😀
    😅
    😊
    🙂
    🙃
    😌
    😍
    😘
    😜
    😝
    😏
    😒
    🙄
    😳
    😡
    😔
    😫
    😱
    😭
    💩
    👻
    🙌
    🖕
    👍
    👫
    👬
    👭
    🌚
    🌝
    🙈
    💊
    😶
    🙏
    🍦
    🍉
    😣
    Source: github.com/k4yt3x/flowerhd
    颜文字
    Emoji
    小恐龙
    花!
    上一篇
    下一篇