leetcode-341-扁平化嵌套列表迭代器-java

题目及测试

package pid341;
/*  扁平化嵌套列表迭代器

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

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

 

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


*/
public class main {
	
	public static void main(String[] args) {

	}


}
package pid341;

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

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 null if this NestedInteger holds a single integer
	public List<NestedInteger> getList();
}

解法1(成功,4ms,较快)

内部有一个stack,index大的先放进去,小的后放进去。next时,弹出最上面的,如果是数字,直接返回。如果不是数字,将列表从后到前依次放进stack,然后再次调用next方法。

hasNext,由于会出现stack不为空,但是NestInteger为{}的情况,需要先调用next得到返回的结果不为null,再返回true,同时把返回的结果放到nextInteger里面,next方法优先返回nextInteger,然后清空这个字段

package pid341;

import java.util.Iterator;
import java.util.List;
import java.util.Stack;

/**
 * // 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 null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {
	
	private Stack<NestedInteger> stack = new Stack<>();
	
	// 如果调用了hasNext方法,会把下一次返回的结果存在里面,next方法会返回这个结果,并清空这个字段
	Integer nextInteger = null;

    public NestedIterator(List<NestedInteger> nestedList) {
    	if(nestedList.size() == 0){
    		return;
    	}
        for(int i=nestedList.size()-1;i>=0;i--){
        	stack.push(nestedList.get(i));
        }
    }

    @Override
    public Integer next() {
    	if(nextInteger != null){
    		Integer result = nextInteger;
    		nextInteger = null;
    		return result;
    	}
    	if(stack.isEmpty()){
    		return null;
    	}
    	NestedInteger now = stack.pop();
    	if(now.isInteger()){
    		return now.getInteger();
    	}else{
    		List<NestedInteger> nestedList = now.getList();
    		if(nestedList.size() != 0){
    			for(int i=nestedList.size()-1;i>=0;i--){
                	stack.push(nestedList.get(i));
                }
        	}   		
    		return next();
    	}
    }

    @Override
    public boolean hasNext() {       
    	if(stack.isEmpty()){
    		return false;
    	}else{
    		Integer now = next();
    		if(now==null){
    			return false;
    		}else{
    			nextInteger = now;
    			return true;
    		}
    	}
    }
}

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

 

解法2(别人的)

简单粗暴,在初始化迭代器的时候就直接把结果遍历出来,递归遍历列表中的数据,是整数就放入List,不是则再递归遍历,代码结构简单。

public class NestedIterator implements Iterator<Integer> {

    private List<Integer> list;
    private int index;

    public NestedIterator(List<NestedInteger> nestedList) {
        list = integerIterator(nestedList);
        index = -1;
    }

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

    @Override
    public boolean hasNext() {
        if (index + 1 < list.size()) return true;
        return false;
    }

    private static List<Integer> integerIterator(List<NestedInteger> nestedIntegerList) {
        ArrayList<Integer> list = new ArrayList<>(nestedIntegerList.size());
        for (NestedInteger tmp : nestedIntegerList) {
            if (tmp.isInteger()) 
                list.add(tmp.getInteger());
            else 
                list.addAll(integerIterator(tmp.getList()));
        }
        return list;
    }
}

解法3(别人的)

在类中添加nestedList、stack、iteratot、integer四个属性,分别对应嵌套列表、迭代器存储栈、当前迭代器、当前遍历整数

构造函数初始化nestedList、iterator,iterator对应的就是构造参数的迭代器。

重写hasNext()函数,主要逻辑为:

    当前迭代器若hasNext()为true
        判断next()是否为整数,若为整数则赋值integer,返回``true`
        判断next()是否为列表,则将当前迭代器暂存至stack,并更新iterator为当前列表的迭代器,递归hasNext()函数

    当前迭代器若hasNext()为false且stack非空,则迭代器出栈更新为当前iterator,递归hasNext()函数

    其他情况则代表,整个扁平化嵌套列表已遍历完毕,返回false

重写next()函数,迭代器的使用规则是hasNext()返回为true时调用next()函数获取下一值,再次直接返回integer(当前遍历整数)即可。

public class NestedIterator implements Iterator<Integer> {
		//嵌套列表
  		private  List<NestedInteger> nestedList = null;
        //迭代器存储栈
    	private Stack<Iterator<NestedInteger>> stack = new Stack<>();
    	//当前迭代器
        private Iterator<NestedInteger> iterator = null;
    	//当前遍历整数
        private Integer integer = 0;
        public NestedIterator(List<NestedInteger> nestedList) {
            //嵌套列表初始化
            this.nestedList = nestedList;
            iterator = nestedList.iterator();
        }

        @Override
        public Integer next() {
            return integer;
        }

        @Override
        public boolean hasNext() {
            if(iterator.hasNext()) {
                NestedInteger nestedInteger = iterator.next();
                if (!nestedInteger.isInteger()) {
                    //该值为列表
                    stack.push(iterator);
                    iterator = nestedInteger.getList().iterator();
                    return hasNext();
                } else {
                    integer = nestedInteger.getInteger();
                    return true;
                }
            }else if(!iterator.hasNext() && !stack.isEmpty()) {
                //当前迭代器至列表末尾并且栈非空
                //迭代器更新为上一级
                iterator = stack.pop();
                return hasNext();
            }else{
                return false;
            }
        }
}

热门文章

暂无图片
编程学习 ·

spring Security

spring Security简单介绍:Spring Security是一个功能强大且高度可定制的身份验证和访问控制框架,它是用于保护基于Spring的应用程序的实际标准。Spring Security是一个框架,致力于为Java应用程序提供身份验证和授权。与所有Spring项目一样,Spring Security的真正强大之处在…
暂无图片
编程学习 ·

JS 中的展开运算符你了解多少 ?

什么是展开运算符 (...)?展开运算符 :允许一个表达式在某处展开。展开运算符在多个参数(用于函数调用)或多个元素(用于数组字面量)或者多个变量(用于解构赋值)等地方可以使 用,作用就是 展开数组或字符串为一个新数组。注意 : 展开运算符不能用在对象当中,因为目前…
暂无图片
编程学习 ·

7-9 1.2.5 双重回文数 (70分)

如果一个数从左往右读和从右往左读都是一样,那么这个数就叫做“回文数”.例如,12321 就是一个回文数,而 77778 就不是. 当然,回文数的首和尾都应是非零的,因此 0220 就不是回文数. 事实上,有一些数(如 21),在十进制时不是回文数,但在其它进制(如二进制时为 10101)时就是 回…
暂无图片
编程学习 ·

反射 枚举和lambda

1 反射(reflect) 是在运行状态中,对于任意一个类,都能够知道这个类的所有属性和方法. 对于任意 一个对象,都能够调用它的任意方法和属性. 既然能拿到那么,我们就可以修改部分类型信息. 这种动态获取信息以及动态调用对象方法的功能称为java语言的反射机制. 2 使用场景: 可…
暂无图片
编程学习 ·

两种判断对象类型的方法

两种判断对象类型的方法: 1.通过instanceof *缺点:不能准确的判断该对象是Dog的实例,如果该对象是类的子类对象也会返回true 2.对象.getClass().getName()获取对象的实例类名 (1)对象.getClass():返回该对象对应的Class对象 (2)对象.getClass().getName():该对象对应的class对…
暂无图片
编程学习 ·

kafka+zookeeper消息队列

软件包提取码:u3s1 kafka: 起初是做采集日志的,和zookeeper一起才能做消息队列,可持久化。kafka broker(server): 消息中间件处理的节点 一个Kafka节点就是一个broker(server) topic = vhost -类消息 对消息进行分类主题-个类型-个主题topic可以有多个 partition = que…
暂无图片
编程学习 ·

【GNURadio RTL-SDR】双RTL-SDR信号源的FM调频广播接收机

文章目录1. 前言2. 实验过程2.1 制作流图2.2 RTL-SDR的设备参数1. 前言 两个RTL-SDR的dongle“电视棒”,芯片 RTL2832U + R820T ,淘宝50左右那种能收FM和我国DTMB频段,想都接到同一台电脑去用软件无线电(GNURadio)的方式收多个FM调频广播信号。 2. 实验过程 在谷歌搜了不少…
暂无图片
编程学习 ·

Docker学习(一)

一、docker安装环境Ubuntu16.04 x64二、docker安装安装过程需要获取外网资源包,因此首先需要配置本地服务器DNS追加这两个DNS nameserver 8.8.8.8 nameserver 8.8.4.4Ubuntu配置DNS参考: https://blog.csdn.net/deep_kang/article/details/79599796 https://blog.csdn.net/wa…
暂无图片
编程学习 ·

2016 年实验班选拔试题

SUM(10 分) 题目描述:求出在 1 到 N 之间的所有整数的总和。 输入格式:输入包含多组测试数据。每行是一组测试数据,该数据是一个绝对值不 大于 10000 的整数 N。N=0 时,表示输入结束。 输出格式:对于每组测试数据,输出一行,改行包含一个整数,是所有在 1 到 N 之 间的…
暂无图片
编程学习 ·

Flink Table API运用与UDF实现

本文使用Table Api实现word count,自定义UDF实现单词切割。 object TestUDFByWordCount {def main(args: Array[String]): Unit = {val env = StreamExecutionEnvironment.getExecutionEnvironmentval settings = EnvironmentSettings.newInstance().useBlinkPlanner().inStrea…
暂无图片
编程学习 ·

Easyui网上书城前端界面

Easyui网上书城前端界面登录界面注册界面首页界面查询书籍界面购物车界面login.htmlregister.htmlindex.htmlsearch.htmlshopping.html 接上一篇博客. 首先,前端界面所需要的界面有 登录 注册 首页 查询书籍 购物车 登录界面注册界面首页界面查询书籍界面购物车界面login.html…
暂无图片
编程学习 ·

docker方式部署ELK

1.拉取原始镜像: docker pull sebp/elk:6602.启动下镜像方便进入,进行自定义配置修改:docker run -dit --name elk \-p 5601:5601 \-p 9200:9200 \-p 5044:5044 \-v /data/elasticsearch:/var/lib/elasticsearch \-v /etc/localtime:/etc/localtime \sebp/elk:660这里说明下560…
暂无图片
编程学习 ·

其实AQS并不难

不啰嗦,直接上干货 文章目录上锁解锁总结条件队列 newConditionCLH队列的数据结构扩展 interrupted 上锁ReentrantLock reentrantLock = new ReentrantLock(true);或者ReentrantLock reentrantLock = new ReentrantLock();看构造函数://无参的构造函数,默认为非公平锁public…
暂无图片
编程学习 ·

Yarn工作原理自我总结

如图所示 1.由Client(客户端)提交一个作业请求给ResourceManager(资源管理器) 2.ResourceManager生成一个ApplicationMaster(程序管理员),并根据Node Status(状态)在空闲的NodeManager节点上运行ApplicationMaster 3.ApplicationMaster向ResourceManager注册其信息,并发送资源…
暂无图片
编程学习 ·

mysql 获取本周每天时间

mysql 获取本周每天时间语句 (evt_t_event换成自己的表) SELECT@date := DATE_ADD(@date, INTERVAL + 1 DAY) daysFROM(SELECT@date := DATE_ADD(SUBDATE(CURDATE(),DATE_FORMAT(CURDATE(),%w)-1), INTERVAL - 1 DAY)FROMevt_t_eventLIMIT 7) time
暂无图片
编程学习 ·

ubuntu 安装多个CUDA版本并可以随时切换

CUDA是什么就不介绍了,直接讲怎么实现CUDA多版本的共存和实时切换。1、安装多个版本的CUDA 这里,我们以cuda9-1版本和cuda9-0版本为例(先安装哪个无所谓) 首先,在cuda版本库中选择自己需要的cuda版本。 然后,选择对应的安装包,这里选择runfile类型的安装文件,以便后面…
暂无图片
编程学习 ·

MySQL在dos命令行中输入中文时报错

情景:在DOS命令行中操作中文时报错 insert into category(cid,cname) values(c010,中文); ERROR 1366 (HY000): Incorrect string value:\xB7\xFE\XD7\xB0 for colum cname at row 1原因:mysql的客户端设置编码是utf8,而系统的cmd窗口编码是gbk 解决:查看mysql内部设置的编…
暂无图片
编程学习 ·

CDN和DNS的区别

相信有很多的朋友会被这几个名词绕的有些头大,很多朋友觉得智能DNS跟双线加速、CDN加速是类似的技术。其实不然,虽然他们的目的都是一个:让用户更快的访问网站。但是他们的应用原理却大相径庭。大家一定很清楚这几种都是比较常见的主机加速的方式。所以文本主要介绍一下“智…
暂无图片
编程学习 ·

【C数据结构】简单顺序队列代码

#include<stdio.h> #include<stdlib.h>#define MAXLEN 10 typedef int datatype; typedef struct{datatype data[MAXLEN];int front;//头int rear;//尾 }SeqQueue; /* 队头front+1是头元素下标,队尾rear是尾元素下标 */ void InitQueue(SeqQueue *&Q); int …