两种方式实现一个「扁平化嵌套列表迭代器」|Java 刷题打卡

简介: 两种方式实现一个「扁平化嵌套列表迭代器」|Java 刷题打卡

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 341. 扁平化嵌套列表迭代器 ,难度为 中等


Tag : 「DFS」、「队列」、「栈」


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


列表中的每一项或者为一个整数,或者是另一个列表。其中列表的元素也可能是整数或是其他列表。

 

示例 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]。
复制代码


DFS + 队列



由于所有的元素都是在初始化时提供的,因此一个朴素的做法是在初始化的时候进行处理。


由于存在嵌套,比较简单的做法是通过 DFS 进行处理,将元素都放至队列。


代码:


public class NestedIterator implements Iterator<Integer> {
    Deque<Integer> queue = new ArrayDeque<>();
    public NestedIterator(List<NestedInteger> nestedList) {
        dfs(nestedList);
    }
    @Override
    public Integer next() {
        return hasNext() ? queue.pollFirst() : -1;
    }
    @Override
    public boolean hasNext() {
        return !queue.isEmpty();
    }
    void dfs(List<NestedInteger> list) {
        for (NestedInteger item : list) {
            if (item.isInteger()) {
                queue.addLast(item.getInteger());
            } else {
                dfs(item.getList());
            }
        }
    }
}
复制代码


  • 时间复杂度:构建迭代器的复杂度为 O(n)O(n),调用 next()next()hasNext()hasNext() 的复杂度为 O(1)O(1)
  • 空间复杂度:O(n)O(n)


递归 + 栈



另外一个做法是,我们不对所有的元素进行预处理。


而是先将所有的 NestedInteger 逆序放到栈中,当需要展开的时候才进行展开。


代码:


public class NestedIterator implements Iterator<Integer> {
    Deque<NestedInteger> stack = new ArrayDeque<>();
    public NestedIterator(List<NestedInteger> list) {
        for (int i = list.size() - 1; i >= 0; i--) {
            NestedInteger item = list.get(i);
            stack.addLast(item);
        }
    }
    @Override
    public Integer next() {
        return hasNext() ? stack.pollLast().getInteger() : -1;
    }
    @Override
    public boolean hasNext() {
        if (stack.isEmpty()) {
            return false;
        } else {
            NestedInteger item = stack.peekLast();
            if (item.isInteger()) {
                return true;
            } else {
                item = stack.pollLast();
                List<NestedInteger> list = item.getList();
                for (int i = list.size() - 1; i >= 0; i--) {
                    stack.addLast(list.get(i));
                }
                return hasNext();
            }
        }
    }
}
复制代码


  • 时间复杂度:构建迭代器的复杂度为 O(n)O(n)hasNext()hasNext() 的复杂度为均摊 O(1)O(1)next()next() 严格按照迭代器的访问顺序( 先 hasNext()hasNext()next()next() )的话为 O(1)O(1),防御性编程生效的情况下为均摊 O(1)O(1)
  • 空间复杂度:O(n)O(n)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.341 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
7月前
|
人工智能 JSON Java
列表结构与树结构转换分析与工具类封装(java版)
本文介绍了将线性列表转换为树形结构的实现方法及工具类封装。核心思路是先获取所有根节点,将其余节点作为子节点,通过递归构建每个根节点的子节点。关键在于节点需包含 `id`、`parentId` 和 `children` 三个属性。文中提供了两种封装方式:一是基于基类 `BaseTree` 的通用工具类,二是使用函数式接口实现更灵活的方式。推荐使用后者,因其避免了继承限制,更具扩展性。代码示例中使用了 Jackson 库进行 JSON 格式化输出,便于结果展示。最后总结指出,理解原理是进一步优化和封装的基础。
206 0
|
7月前
|
人工智能 Java
Java 中数组Array和列表List的转换
本文介绍了数组与列表之间的相互转换方法,主要包括三部分:1)使用`Collections.addAll()`方法将数组转为列表,适用于引用类型,效率较高;2)通过`new ArrayList&lt;&gt;()`构造器结合`Arrays.asList()`实现类似功能;3)利用JDK8的`Stream`流式计算,支持基本数据类型数组的转换。此外,还详细讲解了列表转数组的方法,如借助`Stream`实现不同类型数组间的转换,并附带代码示例与执行结果,帮助读者深入理解两种数据结构的互转技巧。
376 1
Java 中数组Array和列表List的转换
|
11月前
|
Java 编译器 API
如何在 Java 中避免使用迭代器
在Java中,为了避免使用迭代器,可以采用foreach循环来遍历集合或数组,简化代码,提高可读性。此外,Java 8引入的Stream API提供了更强大的功能,如filter、map等方法,能够以函数式编程风格处理数据,进一步减少对传统迭代器的依赖。
192 7
|
设计模式 安全 Java
Java Iterator(迭代器)详解
在Java中,`Iterator`是一种设计模式,用于遍历如`List`、`Set`等集合,提供统一访问元素的方式而不暴露内部结构。它包括`hasNext()`、`next()`和`remove()`方法,通过集合的`iterator()`方法获取实例,可用于安全删除元素,避免`ConcurrentModificationException`。
163 14
|
存储 搜索推荐 算法
在 Java 中如何更改数组列表的顺序
【8月更文挑战第23天】
500 0
|
存储 安全 Java
在 Java 中如何存储数组列表
【8月更文挑战第23天】
177 0
|
存储 Java API
如何在 Java 中创建 ArrayList 列表?
【8月更文挑战第23天】
376 0
|
存储 Java API
如何在 Java 中填充数组列表?
【8月更文挑战第23天】
130 0
|
存储 Java
如何在 Java 中打印字符串数组列表
【8月更文挑战第23天】
173 2
|
安全 Java
Java 中嵌套公共静态类与顶级类的区别
【8月更文挑战第22天】
136 0

热门文章

最新文章