抹平列表

原题链接http://www.lintcode.com/zh-cn/problem/flatten-list/

题目

一个广义列表,其中元素可能为整数或者列表,将列表变成简单列表(即其中元素只有整数,没有列表),并且不能使用递归算法。

分析

如果允许使用递归,这道题目并不难,遍历原始列表,如果遇到元素为列表,就递归调用函数即可。但禁止使用递归算法,就需要使用栈来实现递归过程。抹平过程如下:

  • 遍历广义数组,若当前元素为整数,则直接将之添加到结果列表中
  • 若当前元素为数组,则先将当前正在处理的列表入栈,然后处理当前的数组元素
  • 由于数组元素可能嵌套,且数组元素可能出现在任何位置,在入栈时,当前处理的位置,也应当一并保存

实现


public class Solution {
/*
 * 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 getList();
 * }
*/
    // @param nestedList a list of NestedInteger
    // @return a list of integer
    public List<Integer> flatten(List<NestedInteger> nestedList) {
        List<Integer> list = new ArrayList();
        Stack<List> stack = new Stack<List<NestedInteger>>();
        Stack<Integer> istack = new Stack();
        // 将初始列表入栈
        stack.push(nestedList);
        istack.push(0);
        
        while(stack.size()>0){
            nestedList = stack.pop();
            NestedInteger el = null;
            
            for(int i=istack.pop(); i < nestedList.size(); i++){
                el = nestedList.get(i);
                if(el.isInteger()){
                    list.add(el.getInteger());
                }else{
                    // 保存当前处理列表和位置
                    stack.push(nestedList);
                    istack.push(i+1);
                    // 将新列表入栈,准备处理
                    stack.push(el.getList());
                    istack.push(0);
                    break;
                }
            }
        }
        return list;
    }
}
Show Comments

Get the latest posts delivered right to your inbox.