Dada una lista anidada de enteros, devuelve la suma de todos los enteros en la lista ponderados por su profundidad.
Cada elemento es un número entero o una lista, cuyos elementos también pueden ser números enteros u otras listas.
A diferencia de la pregunta anterior donde el peso aumenta de raíz a hoja, ahora el peso se define de abajo hacia arriba. es decir, los números enteros a nivel de hoja tienen un peso 1 y los números enteros a nivel de raíz tienen el peso más grande.
Ejemplo 1:
Dada la lista [[1,1], 2,[1,1]]devuelve 8. (cuatro unos en la profundidad 1, uno 2 en la profundidad 2)
Ejemplo 2:
Dada la lista [1,[4,[6]]]devuelve 17. (uno 1 en profundidad 3, uno 4 en profundidad 2 y uno 6 en profundidad 1; 1 * 3 + 4 * 2 + 6 * 1 = 17)
Solución Java
public int depthSumInverse(List<NestedInteger> nestedList) { if(nestedList==null||nestedList.size()==0) return 0; HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>(); //two stacks: one is for processing nested integer, the other is for tracking layers. Stack<NestedInteger> stack = new Stack<NestedInteger>(); Stack<Integer> layers = new Stack<Integer>(); //put all NestedIntegers to Stack and record its layer to be 1 for(NestedInteger ni: nestedList){ stack.push(ni); layers.push(1); } int maxLayer=Integer.MIN_VALUE; while(!stack.isEmpty()){ NestedInteger top = stack.pop(); int topLayer = layers.pop(); maxLayer=Math.max(maxLayer, topLayer); if(top.isInteger()){ if(map.containsKey(topLayer)){ map.get(topLayer).add(top.getInteger()); }else{ ArrayList<Integer> list = new ArrayList<Integer>(); list.add(top.getInteger()); map.put(topLayer, list); } }else{ for(NestedInteger ni: top.getList()){ stack.push(ni); layers.push(topLayer+1); } } } // calcualte sum int result=0; for(int i=maxLayer; i>=1; i--){ if(map.get(i)!=null){ for(int v: map.get(i)){ result += v*(maxLayer-i+1); } } } return result; } |
