写点什么

LeetCode 题解:341. 扁平化嵌套列表迭代器,DFS,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2021 年 05 月 17 日
LeetCode题解:341. 扁平化嵌套列表迭代器,DFS,JavaScript,详细注释

原题链接:341. 扁平化嵌套列表迭代器


解题思路:


  1. 输入: nestedList=[[1,1],2,[1,1]]时,nestedList[0]也是一个NestedInteger类型,只是nestedList[0].getInteger() === null

  2. 可以将nestedList当做一个树,每个节点可以通过getInteger方法获取当前值,通过getList方法获取下一层节点。

  3. 使用DFS,先搜索出树的所有节点的值,将值都存入数组。

  4. 使用一个指针index,始终指向next对应的取值位置。每次调用next,都将指针向后移动一位。如果index指向类型为numberhasNext返回true


/** * @constructor * @param {NestedInteger[]} nestedList */var NestedIterator = function (nestedList) {  this.list = []; // 使用数组存储每个节点的值  this.index = 0; // 用一个指针,始终指向下一个元素
// 使用DFS,搜索所有结果,并进行初始化 const dfs = (nestedList) => { // 遍历数组的每个元素 for (const nestedInteger of nestedList) { // 获取当前元素的值 const value = nestedInteger.getInteger();
// 若当前值存在,则将其存入数组 if (typeof value === 'number') { this.list.push(value); }
// 继续搜索下一级元素列表 dfs(nestedInteger.getList()); } }; // 搜索nestedList dfs(nestedList);};
/** * @this NestedIterator * @returns {boolean} */NestedIterator.prototype.hasNext = function () { // 如果指针对应的值类型为number,表示下一项存在,否则为undefined return typeof this.list[this.index] === 'number';};
/** * @this NestedIterator * @returns {integer} */NestedIterator.prototype.next = function () { // 将当前值返回,并向后移动指针 return this.list[this.index++];};
复制代码


发布于: 2021 年 05 月 17 日阅读数: 11
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:341. 扁平化嵌套列表迭代器,DFS,JavaScript,详细注释