X

LEETCODE 341. Flatten Nested List Iterator 解题思路分析

题目大意:

扁平化嵌套列表迭代器

给定一个嵌套的整型列表。设计一个迭代器,使其能够遍历这个整型列表中的所有整数。

列表中的项或者为一个整数,或者是另一个列表。

示例 1:

输入: [[1,1],2,[1,1]]
输出: [1,1,2,1,1]
解释: 通过重复调用 next 直到 hasNext 返回false,next 返回的元素的顺序应该是: [1,1,2,1,1]。

示例 2:

输入: [1,[4,[6]]]
输出: [1,4,6]
解释: 通过重复调用 next 直到 hasNext 返回false,next 返回的元素的顺序应该是: [1,4,6]。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=341

解题思路分析:

本题难度不大,只要将题目给出的嵌套列表预处理成普通的List即可。对于嵌套方式的列表,最有效的遍历手段即是使用递归,递归函数中,循环列表中的每一个对象,如果当前对象是数字,直接将其加入普通List,如果不是数字而是子列表,那么将该子列表递归至子问题解决即可。子问题的逻辑与当前逻辑完全一致。

实现代码:

List<Integer> list = new ArrayList<>(); // 普通List
int index=0;
public NestedIterator(List<NestedInteger> nestedList) {
    // 预处理,扁平化嵌套list
    help(nestedList);
}

void help(List<NestedInteger> nestedList){
    // 循环List中每一个对象
    for(NestedInteger i : nestedList){
        // 如果是数字
        if(i.isInteger()){
            // 将该数字加入普通List
            list.add(i.getInteger());
        }else{
            // 如果不是数字,递归子问题解决
            help(i.getList());
        }
    }
}

@Override
public Integer next() {
    if(!hasNext()) return null;
    return list.get(index++);
}

@Override
public boolean hasNext() {
    return index<list.size();
}

本题解法执行时间为2ms。

Runtime: 2 ms, faster than 99.86% of Java online submissions for Flatten Nested List Iterator.

Memory Usage: 42.5 MB, less than 5.00% of Java online submissions for Flatten Nested List Iterator.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-341-flatten-nested-list-iterator-解题思路分析/
Categories: leetcode
kwantong: