卖萌的弱渣

I am stupid, I am hungry.

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:

Given the list [[1,1],2,[1,1]],

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

Example 2:

Given the list [1,[4,[6]]],

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

Solution

  • nestedList: List[NestedInteger]. NestedInteger有可能是integer也有可能还是一个List[NestedInteger]

  • Java

(Flatten-Nested-List-Iterator.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public class NestedIterator implements Iterator<Integer> {
    Stack<NestedInteger> stack = new Stack<>();
    public NestedIterator(List<NestedInteger> nestedList) {
        for(int i=nestedList.size()-1; i>=0; i--)
            stack.push(nestedList.get(i));

    }

    @Override
    public Integer next() {
        return stack.pop().getInteger();
    }

    @Override
    public boolean hasNext() {
        while(!stack.isEmpty())
        {
            NestedInteger cur = stack.peek();
            if(cur.isInteger()) return true;
            stack.pop();
            for(int j=cur.getList().size()-1; j>=0; j--)
                stack.push(cur.getList().get(j));
        }
        return false;
    }
}
  • Python
(Flatten-Nested-List-Iterator.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger(object):
#    def isInteger(self):
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        :rtype bool
#        """
#
#    def getInteger(self):
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        :rtype int
#        """
#
#    def getList(self):
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        :rtype List[NestedInteger]
#        """

class NestedIterator(object):

    def __init__(self, nestedList):
        """
        Initialize your data structure here.
        :type nestedList: List[NestedInteger]
        """
        self.array = []

        def fill(nl):
            for ni in nl:
                # 找到一个integer
                if ni.isInteger():
                    self.array.append(ni.getInteger())
                else:
                    # 找到一个List[NestedInteger]
                    fill(ni.getList())

        fill(nestedList)
        self.index = 0

    def next(self):
        """
        :rtype: int
        """
        i = self.index
        self.index += 1
        return self.array[i]

    def hasNext(self):
        """
        :rtype: bool
        """
        return self.index<len(self.array)