LintCode(22)将一个嵌套集合按照原顺序处理为Integer集合

港控/mmm° 2022-04-17 04:50 62阅读 0赞

问题

Given a list, each element in the list can be a list or integer. flatten it into a simply list with integers.

### Example ###

Given `[1,2,[1,2]]`, return `[1,2,1,2]`.

Given `[4,[3,[2,[1]]]]`, return `[4,3,2,1]`.

### Challenge ###

Do it in non-recursive.

### Notice ###

If the element in the given list is a list, it can contain list too.

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();
     * }
     * 思路
     * 参数合法性判断
     * 定义结果集合
     * 由于不能使用递归
     * 但是又需要循环，由于不能确定需要循环的深度，需要对源数据做数据处理，简化源数据
     * 将源数据看作一个栈，永远都是对栈顶的元素做判断，如果符合是单个Integer就加入结果集合，并弹出
     * 如果不是，就将栈顶元素遍历出来，倒序压栈
     * 循环判断栈是否为空，如果空就是处理完毕
     * 最后，返回结果集合
     */
    public class Solution {
    
        // @param nestedList a list of NestedInteger
        // @return a list of integer
        public List<Integer> flatten(List<NestedInteger> nestedList) {
            // Write your code here
            //参数合法性判断
            if(nestedList.size() < 1){
                return null;
            }
            //定义结果集合
            List<Integer> result = new ArrayList<Integer>();
            //定义标记变量
            boolean flag = false;
            //循环待处理集合
            while(nestedList.size() > 0){
                //获取栈顶元素的性质
                flag = nestedList.get(0).isInteger();
                //如果是单个Integer，则弹出到结果集合
                if(flag){
                    Integer inte = nestedList.remove(0).getInteger();
                    result.add(inte);
                }else{
                    //如果不是单个Integer
                    List<NestedInteger> tmp = nestedList.remove(0).getList();
                    //倒序压栈
                    for(int i = tmp.size() - 1; i >= 0; i--){
                        nestedList.add(0, tmp.get(i));
                    }
                }
            }
            return result;
        }
    }