[LeetCode] Flatten Nested List Iterator

2021.04.23

问题描述

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

NestedIterator(List nestedList) Initializes the iterator with the nested list nestedList.

int next() Returns the next integer in the nested list.

boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Example 1:

Input: nestedList = [[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: nestedList = [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].

Constraints:

1 <= nestedList.length <= 500
The values of the integers in the nested list is in the range [-10^6, 10^6].

问题分析

题目提供了自定义数据类型 NestedInteger 以及相应的方法；对于这种嵌套层级来说，常见做法是利用 stack进行，这里也不例外，唯一需要注意的是，在判断是否有下一个元素时，对空元素的处理

代码如下:

示例代码

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * type NestedInteger struct {
 * }
 *
 * // Return true if this NestedInteger holds a single integer, rather than a nested list.
 * func (this NestedInteger) IsInteger() bool {}
 *
 * // Return the single integer that this NestedInteger holds, if it holds a single integer
 * // The result is undefined if this NestedInteger holds a nested list
 * // So before calling this method, you should have a check
 * func (this NestedInteger) GetInteger() int {}
 *
 * // Set this NestedInteger to hold a single integer.
 * func (n *NestedInteger) SetInteger(value int) {}
 *
 * // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 * func (this *NestedInteger) Add(elem NestedInteger) {}
 *
 * // Return the nested list that this NestedInteger holds, if it holds a nested list
 * // The list length is zero if this NestedInteger holds a single integer
 * // You can access NestedInteger's List element directly if you want to modify it
 * func (this NestedInteger) GetList() []*NestedInteger {}
 */

// 迭代器内部保存一个stack即可
type NestedIterator struct {
	stack *stack
}

func Constructor(nestedList []*NestedInteger) *NestedIterator {
	it := &NestedIterator{
		stack: &stack{},
	}
    // 逆序压栈
	for i := len(nestedList) - 1; i >= 0; i-- {
		it.stack.Push(nestedList[i])
	}
	return it
}

// Next()只会在 HasNext()为true的情况下调用，所以这里直接pop，返回对应的值即可
func (this *NestedIterator) Next() int {
	elem := this.stack.Pop()
	return elem.GetInteger()
}

func (this *NestedIterator) HasNext() bool {
    // 循环判断栈顶元素是否为 Integer
    // 如果不是，需要将list取出，再次逆序压栈；并重复以上判断过程
	for {
		if this.stack.Empty() {
			return false
		}
        // 栈顶元素
		top := this.stack.Top()
        // 如果栈顶元素为空，直接Pop掉，进入下一轮判断
		if top == nil {
			this.stack.Pop()
			continue
		}
        // 如果栈顶元素是 Integer，中断循环
		if top.IsInteger() {
			break
		}
        // 如果非Integer，则将list中元素逆序压栈
		list := this.stack.Pop().GetList()
		for i := len(list) - 1; i >= 0; i-- {
			this.stack.Push(list[i])
		}
	}
	return !this.stack.Empty()
}

type stack struct {
	list []*NestedInteger
}

func (s *stack) Pop() *NestedInteger {
	if len(s.list) == 0 {
		return nil
	}
	ans := s.list[0]
	s.list = s.list[1:]
	return ans
}

func (s *stack) Push(elem *NestedInteger) {
	s.list = append([]*NestedInteger{elem}, s.list...)
}

func (s *stack) Empty() bool {
	return len(s.list) == 0
}

func (s *stack) Top() *NestedInteger {
	if len(s.list) == 0 {
		return nil
	}
	return s.list[0]
}

原题链接

Flatten Nested List Iterator



leetcode

stack

发表评论

不二