扁平化嵌套列表迭代器

  1. 扁平化嵌套列表迭代器
    1. 理解题意
    2. 解题思路
    3. 实现代码
    4. 进阶思路

扁平化嵌套列表迭代器

来源:

理解题意

首先,现在有一种数据结构NestedInteger这个结构中存的数据可能是一个Integer整数,也可能是一个NestedInteger列表。注意,这个列表里面装着的是NestedInteger,也就是说这个列表中的每一个元素可能是个整数,可能又是个列表,这样无限递归嵌套下去……

NestedInteger有如下 API:

public class NestedInteger {
    // 如果其中存的是一个整数,则返回 true,否则返回 false
    public boolean isInteger();

    // 如果其中存的是一个整数,则返回这个整数,否则返回 null
    public Integer getInteger();

    // 如果其中存的是一个列表,则返回这个列表,否则返回 null
    public List<NestedInteger> getList();
}

我们的算法会被输入一个NestedInteger列表,我们需要做的就是写一个迭代器类,将这个带有嵌套结构NestedInteger的列表「拍平」:

public class NestedIterator implements Iterator<Integer> {
    // 构造器输入一个 NestedInteger 列表
    public NestedIterator(List<NestedInteger> nestedList) {}

    // 返回下一个整数
    public Integer next() {}

    // 是否还有下一个整数?
    public boolean hasNext() {}
}

我们写的这个类会被这样调用,先调用hasNext方法,后调用next方法

NestedIterator i = new NestedIterator(nestedList);
while (i.hasNext())
    print(i.next());

示例 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]

解题思路

NestedInteger 结构:

public class NestedInteger {
    private Integer val;
    private List<NestedInteger> list;

    public NestedInteger(Integer val) {
        this.val = val;
        this.list = null;
    }
    public NestedInteger(List<NestedInteger> list) {
        this.list = list;
        this.val = null;
    }

    /**
     * 如果其中存的是一个整数,则返回 true,否则返回 false
     */
    public boolean isInteger() {
        return val != null;
    }

    /**
     * 如果其中存的是一个整数,则返回这个整数,否则返回 null
     */
    public Integer getInteger() {
        return this.val;
    }

    /**
     * 如果其中存的是一个列表,则返回这个列表,否则返回 null
     */
    public List<NestedInteger> getList() {
        return this.list;
    }
}

回顾前缀树结构

比如说输入是[[1,1],2,[1,1]],其实就是如下树状结构:

image-20211208165057395

对比:

class NestedInteger {
    Integer val;
    List<NestedInteger> list;
}

/* 基本的 N 叉树节点 */
class TreeNode {
    int val;
    TreeNode[] children;
}

这就是一棵 N 叉树吗?叶子节点是Integer类型,其val字段非空;其他节点都是List<NestedInteger>类型,其val字段为空,但是list字段非空,装着孩子节点

好的,刚才题目说什么来着?把一个NestedInteger扁平化对吧?这不就等价于遍历一棵 N 叉树的所有「叶子节点」吗

实现代码

这个框架可以遍历所有节点,而我们只对整数型的NestedInteger感兴趣,也就是我们只想要「叶子节点」,所以traverse函数只要在到达叶子节点的时候把val加入结果列表即可:

//给你一个嵌套的整数列表 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 
// 嵌套列表中的整数值在范围 [-10⁶, 10⁶] 内 
// 
// Related Topics 栈 树 深度优先搜索 设计 队列 迭代器 👍 387 👎 0

import com.tree.NestedInteger;
//leetcode submit region begin(Prohibit modification and deletion)


import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * // 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 empty list if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {

    private Iterator<Integer> it;

    public NestedIterator(List<NestedInteger> nestedList) {
        List<Integer> result = new LinkedList<>();
        for (NestedInteger node : nestedList) {
            traverse(node, result);
        }
        this.it = result.iterator();
    }

    private void traverse(NestedInteger root, List<Integer> result) {
        if (root.isInteger()) {
            result.add(root.getInteger());
            return;
        }

        for (NestedInteger child : root.getList()) {
            traverse(child, result);
        }
    }

    @Override
    public Integer next() {
        return it.next();
    }

    @Override
    public boolean hasNext() {
        return it.hasNext();
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */
//leetcode submit region end(Prohibit modification and deletion)

进阶思路

我们的解法中,一次性算出了所有叶子节点的值,全部装到result列表,也就是内存中,nexthasNext方法只是在对result列表做迭代。如果输入的规模非常大,构造函数中的计算就会很慢,而且很占用内存。

一般的迭代器求值应该是「惰性的」,也就是说,如果你要一个结果,我就算一个(或是一小部分)结果出来,而不是一次把所有结果都算出来。

如果想做到这一点,使用递归函数进行 DFS 遍历肯定是不行的,而且我们其实只关心「叶子节点」,所以传统的 BFS 算法也不行。实际的思路很简单:

调用hasNext时,如果nestedList的第一个元素是列表类型,则不断展开这个元素,直到第一个元素是整数类型

由于调用next方法之前一定会调用hasNext方法,这就可以保证每次调用next方法的时候第一个元素是整数型,直接返回并删除第一个元素即可。

看代码:

public class NestedIterator implements Iterator<Integer> {
    
    private LinkedList<NestedInteger> list;

    public NestedIterator(List<NestedInteger> nestedList) {
        // 不直接用 nestedList 的引用,是因为不能确定它的底层实现
        // 必须保证是 LinkedList,否则下面的 addFirst 会很低效
        list = new LinkedList<>(nestedList);
    }

    public Integer next() {
        // hasNext 方法保证了第一个元素一定是整数类型
        return list.remove(0).getInteger();
    }

    public boolean hasNext() {
        // 循环拆分列表元素,直到列表第一个元素是整数类型
        while (!list.isEmpty() && !list.get(0).isInteger()) {
            // 当列表开头第一个元素是列表类型时,进入循环
            List<NestedInteger> first = list.remove(0).getList();
            // 将第一个列表打平并按顺序添加到开头
            for (int i = first.size() - 1; i >= 0; i--) {
                list.addFirst(first.get(i));
            }
        }
        return !list.isEmpty();
    }
}


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 jungle8884@163.com

×

喜欢就点赞,疼爱就打赏