Flatten Nested List Iterator (M)

題目

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

題意

給定一個任意嵌套的整數串列，要求按順序輸出所有整數，

思路

迭代處理：用兩個堆疊分別取存盤暫時掛起的串列和對應的下標，每當遇到一個嵌套串列時，就把當前串列和下標壓堆疊，進入嵌套串列繼續處理；當當前串列已經遍歷完時，則出堆疊之前的串列和下標繼續處理，

也可直接用遞回展開，

代碼實作

Java

迭代處理

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */

public class NestedIterator implements Iterator<Integer> {
    private Deque<List<NestedInteger>> lists = new ArrayDeque<>();
    private Deque<Integer> indices = new ArrayDeque<>();
    private List<NestedInteger> list;
    private int index;
    private Integer num;

    public NestedIterator(List<NestedInteger> nestedList) {
        list = nestedList;
        index = -1;
        generate();
    }

    @Override
    public Integer next() {
        Integer res = num;
        generate();
        return res;
    }

    @Override
    public boolean hasNext() {
        return num != null;
    }

    private void generate() {
        index++;

        while (index < list.size() || !lists.isEmpty()) {
            if (index == list.size()) {
                list = lists.pop();
                index = indices.pop() + 1;
            } else if (!list.get(index).isInteger()) {
                lists.push(list);
                indices.push(index);
                list = list.get(index).getList();
                index = 0;
            } else {
                break;
            }
        }

        num = index < list.size() ? list.get(index).getInteger() : null;
    }
}

遞回展開

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */

public class NestedIterator implements Iterator<Integer> {
    List<Integer> list = new ArrayList<>();
    int index = 0;

    public NestedIterator(List<NestedInteger> nestedList) {
        generate(nestedList);
    }

    @Override
    public Integer next() {
        return list.get(index++);
    }

    @Override
    public boolean hasNext() {
        return index != list.size();
    }

    private void generate(List<NestedInteger> nestedList) {
        for (NestedInteger item : nestedList) {
            if (item.isInteger()) {
                list.add(item.getInteger());
            } else {
                generate(item.getList());
            }
        }
    }
}

標籤：其他

上一篇：0343. Integer Break (M)

下一篇：Girls and Boys POJ - 1466（最大獨立集）