Personal comments: Design iterator = DFS recursion; Initial constructs can be optimized using stacks, but subsequent operations are relatively complex; Another test of certain understanding ability and basic modeling

Simple questions: 🌟 🌟 (reference LeeCode 🌟, moderate 🌟 🌟, difficult 🌟 🌟 🌟)

In addition, algorithm questions usually examine and analyze time complexity and space complexity, which can be referred to the author’s previous article

“Data Structures & Algorithms” series: 3. Time & Space Complexity (2)

Flat nested list iterator

Topic describes

341. Flat nested list iterator

Give you a nested list of integers. You can design an iterator that iterates through all integers in this list of integers.

Each item in the list is either an integer or another list. The elements of a list can also be integers or other lists.

Example 1:

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

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

Explanation: by calling next repeatedly until hasNext returns false, next should return elements in the order: [1,1,2,1,1].

Example 2:

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

Output: [1 minus 2]

Explanation: by calling next repeatedly until hasNext returns false, next should return elements in the order: [1,4,6].

Their thinking

Methods a

If you just expand the nested list, it’s not hard to solve, and check for the least granular element: integer/integer array

So, the key is the expanded recursive function, which Golang implements as follows:

func flatten(n *NestedInteger) []int {
    res := []int{}
    if n.IsInteger() { // Whether it is a number
        res = append(res, n.GetInteger()) // Add numbers
    } else { / / the number
        for _, child := range n.GetList() {
            res = append(res, flatten(child)...) / / recursion}}return res // Returns a flattened array of results
}
Copy the code

(struct NestedIterator) (struct NestedIterator) (struct NestedIterator) (struct NestedIterator) (struct NestedIterator)

Golang implementation reference is as follows:

type NestedIterator struct {
    vals []int // The expanded array
    index int  // index is the number of index that should be returned by the current Next call
}

func Constructor(nestedList []*NestedInteger) *NestedIterator {
    list := []int{}
    for _, n := range nestedList { / / traverse nestedList
      list = append(list, flatten(n)...) // Current element append flatten(n)
    }
    return &NestedIterator{index: 0, vals: list} // Create and return an iterator with an initial index of 0
}
Copy the code

The Next() method and deciding whether to end HasNext() should be easy to understand

func (this *NestedIterator) Next(a) int {
    val := this.vals[this.index] // Get the element
    this.index++                 / / update the index
    return val
}

func (this *NestedIterator) HasNext(a) bool {
    return this.index < len(this.vals)
}
Copy the code

Complexity?

  • Time complexity: initialized to O(n), where n is the number of elements in the nested list of integers.Next()O (1)
  • Spatial complexity: O(n) requires an array to store all elements in a nested list of integers

Method 2

Refer to the netizen solution, the explanation is quite incisive, ah ha ha ~

The stack is like a labor camp, with elements pushed in from back to front (first in, then in, then out, Next gets the first elements), and everyone gets off the stack for a while.

When Next calls, it’s time to grab integer, so it’s time to clean up the top of the stack

If it’s an integer, it doesn’t matter. If it’s a nested list, pop it out and push it onto the stack one by one

It is possible that the new top of the stack is not yet integer, so continue until the top of the stack is INTEGER or the stack is empty

After that, either the stack is empty, or the top of the stack must be integer

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source

Source: LeetCode

type NestedIterator struct {
	Stack []*NestedInteger // the stack is used to hold elements temporarily
}

func Constructor(nestedList []*NestedInteger) *NestedIterator {
	stack := []*NestedInteger{}
	for i := len(nestedList) - 1; i >= 0; i-- { // Push elements one by one from the back
		stack = append(stack, nestedList[i]) // From the back is last in first out, and those in the front are first out
	}
	return &NestedIterator{Stack: stack} // Initialize and return the iterator
}

func (this *NestedIterator) Next(a) int {
	this.stackTop2Integer()                     // Convert the top element to integer
	top := this.Stack[len(this.Stack)- 1]        // Get the top of stack
	this.Stack = this.Stack[:len(this.Stack)- 1] // Pop off the stack
	return top.GetInteger()                     / / returns an integer
}

func (this *NestedIterator) HasNext(a) bool {
	this.stackTop2Integer()    // Convert the top element to integer
	return len(this.Stack) > 0 // If the stack is empty. Note Integer can be obtained
}

// Change the top of the stack to an INTEGER (by popping the top of the list and placing the elements in it one by one)
func (this *NestedIterator) stackTop2Integer(a) {
	for len(this.Stack) > 0 { // Until the stack is empty
		top := this.Stack[len(this.Stack)- 1] // Get the top of stack
		if top.IsInteger() {                 // The top of the stack is already integer, do nothing
			return
		}
		this.Stack = this.Stack[:len(this.Stack)- 1] // The top of the stack is a list
		list := top.GetList()                       / / get the list
		for i := len(list) - 1; i >= 0; i-- {       // Start at the end of the list
			this.Stack = append(this.Stack, list[i])  // Push the elements of list onto the stack}}}Copy the code

Complexity? Build complexity reduced to the number of elements in one layer, len(nestedList)

conclusion

In my opinion, this problem can be developed using recursive violence, which requires a certain understanding and recursive use method.

The use of a stack makes it easier to operate one by one at Next() rather than having to expand one by one at build time.

Wait until the Next call, to take integer, only busy to clean up the stack top <(￣▽￣)/