341.Flatten Nested List Iterator

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Example 1:

Input: [[1,1],2,[1,1]]
Output: [1,1,2,1,1]

Explanation: By calling next repeatedly until hasNext returns false,   the order of elements returned by next should be: [1,1,2,1,1].

Example 2:

Input: [1,[4,[6]]]
Output: [1,4,6]

Explanation: By calling next repeatedly until hasNext returns false,   the order of elements returned by next should be: [1,4,6].

analyze

该题需注意的点: [1, [4]] 里的子项 1, [4] 分别通过 getIntegergetList 获取到。

递归法

/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* function NestedInteger() {
*
* Return true if this NestedInteger holds a single integer, rather than a nested list.
* @return {boolean}
* this.isInteger = function() {
* ...
* };
*
* Return the single integer that this NestedInteger holds, if it holds a single integer
* Return null if this NestedInteger holds a nested list
* @return {integer}
* this.getInteger = function() {
* ...
* };
*
* Return the nested list that this NestedInteger holds, if it holds a nested list
* Return null if this NestedInteger holds a single integer
* @return {NestedInteger[]}
* this.getList = function() {
* ...
* };
* };
*/
/**
* @constructor
* @param {NestedInteger[]} nestedList
*/
var NestedIterator = function(nestedList) {
this.printArr = []
this.resetArr(nestedList)
}
NestedIterator.prototype.resetArr = function(nestedList) {
if (!nestedList && !nestedList.length) return
for (let i = 0; i < nestedList.length; i++) {
const curList = nestedList[i]
if (curList.isInteger()) {
this.printArr.unshift(curList.getInteger())
} else {
this.resetArr(curList.getList())
}
}
}
/**
* @this NestedIterator
* @returns {boolean}
*/
NestedIterator.prototype.hasNext = function() {
return this.printArr.length > 0
}
/**
* @this NestedIterator
* @returns {integer}
*/
NestedIterator.prototype.next = function() {
return this.printArr.pop()
}
/**
* Your NestedIterator will be called like this:
* var i = new NestedIterator(nestedList), a = [];
* while (i.hasNext()) a.push(i.next());
*/

迭代法

相对递归法, 迭代法需要额外维护一个系统调用栈, 然后使用颜色标记法完成题解。

颜色标记法思路:

  • 未访问过的列表标记为白色, 访问过的列表标记为灰色;
  • 从栈顶取出访问元素:
    • 若为灰色元素, 则打印之;
    • 若为白色元素, 则遍历子列表:
      • 若子列表为列表, 则将其标记为白色并推入栈;
      • 若子列表为数字, 则将其标记为灰色并推入栈;
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* function NestedInteger() {
*
* Return true if this NestedInteger holds a single integer, rather than a nested list.
* @return {boolean}
* this.isInteger = function() {
* ...
* };
*
* Return the single integer that this NestedInteger holds, if it holds a single integer
* Return null if this NestedInteger holds a nested list
* @return {integer}
* this.getInteger = function() {
* ...
* };
*
* Return the nested list that this NestedInteger holds, if it holds a nested list
* Return null if this NestedInteger holds a single integer
* @return {NestedInteger[]}
* this.getList = function() {
* ...
* };
* };
*/
/**
* @constructor
* @param {NestedInteger[]} nestedList
*/
var NestedIterator = function(nestedList) {
this.printArr = []
if (!nestedList) return
this.stackList = []
this.stackList.push({ color: 'white', list: nestedList })
while (this.stackList.length > 0) {
const { color, list } = this.stackList.pop()
if (color === 'gray') {
this.printArr.unshift(list)
} else {
for (let i = 0; i < list.length; i++) {
if (list[i].isInteger()) {
this.stackList.push({ color: 'gray', list: list[i].getInteger() })
} else {
this.stackList.push({ color: 'white', list: list[i].getList() })
}
}
}
}
}
/**
* @this NestedIterator
* @returns {boolean}
*/
NestedIterator.prototype.hasNext = function() {
return this.printArr.length > 0
}
/**
* @this NestedIterator
* @returns {integer}
*/
NestedIterator.prototype.next = function() {
return this.printArr.shift()
}
/**
* Your NestedIterator will be called like this:
* var i = new NestedIterator(nestedList), a = [];
* while (i.hasNext()) a.push(i.next());
*/

Similar Title

94、144、145