LeetCode Top Interview Questions 341. Flatten Nested List Iterator (Java版; Medium)

小鱼儿 2023-07-02 12:25 19阅读 0赞

### [welcome to my blog][] ###

## LeetCode Top Interview Questions 341. Flatten Nested List Iterator (Java版; Medium) ##

#### 题目描述 ####

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].

#### 特殊案例, 为了解决这个问题, 需要在hasNext()中就将元素展平! 而不是在next()中展平 ####

输入:
    [[]]
    输出
    [null]
    预期结果
    []

#### 第一次做;关键要设计好hasNext()和flatten(), 本来是把展平操作放到next()里面的, 理解上面的特殊案例不能通过, 所以得放到hasNext()里面 ####

public class NestedIterator implements Iterator<Integer> { 
        private Stack<NestedInteger> stack;
        public NestedIterator(List<NestedInteger> nestedList) { 
            stack = new Stack<>();
            flatten(nestedList);
        }
    
        @Override
        public Integer next() { 
            //这里不用先判断是否有下一个, 因为调用next()之前会先调用hasNext()
            return stack.pop().getInteger();
        }
    
        @Override
        public boolean hasNext() { 
            while(!stack.isEmpty()){ 
                if(stack.peek().isInteger())
                    return true;
                flatten(stack.pop().getList());
            }
            //执行到这里说明栈为空, 并且没有Integer, 所以返回false, 可以处理特殊案例, 输入是[[]]
            return false;
        }
        
        //只负责把列表中的元素压栈, 不考虑展开
        private void flatten(List<NestedInteger> nestedList){ 
            for(int i=nestedList.size()-1; i>=0; i--){ 
                stack.push(nestedList.get(i));
            }
        }
    }
    
    /** * Your NestedIterator object will be instantiated and called as such: * NestedIterator i = new NestedIterator(nestedList); * while (i.hasNext()) v[f()] = i.next(); */

##### [leetcode优秀题解][leetcode] #####

[welcome to my blog]: https://littlehaes.com
[leetcode]: https://leetcode.com/problems/flatten-nested-list-iterator/discuss/80147/Simple-Java-solution-using-a-stack-with-explanation