🌕🌗 341. 扁平化嵌套列表迭代器

难度: 🌕🌗

问题描述

---

解法 1 - 递归

/**
 * // 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> {
    // 思路：
    // 可以看出是嵌套的 链表 | 整数 的数据结构
    // 最直接的方法就是，一次把所有整数元素均得出，放入一个集合中，然后依次取出
    // 嵌套 结构中取元素相当于 递归 - 深度优先遍历
    LinkedList<Integer> list;

    public NestedIterator(List<NestedInteger> nestedList) {
        this.list = new LinkedList<>();
        // 初始化 list
        init(nestedList);
    }

    private void init(List<NestedInteger> nestedList) {
        for(NestedInteger cur: nestedList) {
            if(cur.isInteger()) {
                list.addLast(cur.getInteger());
            } else {
                // 递归
                init(cur.getList());
            }
        }
    }

    @Override
    public Integer next() {
        // 返回数组中最后一个元素，同时删除最后一个元素
        Integer res = list.removeFirst();
        return res;
    }

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

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

---

输出 1

---

解法 2 - 借助栈

/**
 * // 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> {
    // 思路：
    // 之前的做法是，一次性把所有元素放入集合中，若元素过多可能出现内存放不下的情况，因此理论上应该是惰性处理的思路
    // 只有在想要求下一个元素时，才处理一小部分元素
    // 借助 辅助栈 实现
    // 每次只取出队头元素，如果是整数，直接取出，如果是集合，则进行拆分，直到能够取出整数
    LinkedList<NestedInteger> stack;

    public NestedIterator(List<NestedInteger> nestedList) {
        this.stack = new LinkedList<>(nestedList);
    }

    @Override
    public Integer next() {
        return stack.pollFirst().getInteger();
    }

    @Override
    public boolean hasNext() {
        if(stack.isEmpty()) {
            return false;
        }
        if(stack.peekFirst().isInteger()) {
            return true;
        }
        // 队头为集合，需要拆分，查看分解后是否存在整数
        while(!stack.isEmpty() && !stack.peekFirst().isInteger()) {
            List<NestedInteger> cur = stack.pollFirst().getList(); // 获取队头的集合
            // 将集合元素依次压栈放入队头
            int len = cur.size();
            for(int i = len - 1; i >= 0; i --) {
                stack.addFirst(cur.get(i));
            }
        }
        return !stack.isEmpty();
    }
}

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

---

输出 2