LintCode(22)将一个嵌套集合按照原顺序处理为Integer集合
问题
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;
}
}