## Friday, April 1, 2016

### LeetCode 339 - Nested List Weight Sum

Related: LeetCode 364 - Nested List Weight Sum II
http://www.cnblogs.com/grandyang/p/5340305.html
-- Same as LinkedIn: Nested Integer
Given a nested list of integers, return the sum of all integers in the list weighted by their depth.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Example 1:
Given the list `[[1,1],2,[1,1]]`, return 10. (four 1's at depth 2, one 2 at depth 1)
Example 2:
Given the list `[1,[4,[6]]]`, return 27. (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 4*2 + 6*3 = 27)
```    int depthSum(vector<NestedInteger>& nestedList) {
return helper(nestedList, 1);
}
int helper(vector<NestedInteger>& nl, int depth) {
int res = 0;
for (auto a : nl) {
res += a.isInteger() ? a.getInteger() * depth : helper(a.getList(), depth + 1);
}
return res;
}```
https://leetcode.com/discuss/94956/2ms-easy-to-understand-java-solution
The time complexity of my solution is O(n), n is the number of elements or Integer within the list.
the space complexity would be O(k) where k is the max level of depth.
``````    public int depthSum(List<NestedInteger> nestedList) {
return depthSum(nestedList, 1);
}
public int depthSum(List<NestedInteger> nestedList, int level) {
int result = 0;
for(NestedInteger ni : nestedList) {
if (ni.isInteger()) {
result = result + (level * ni.getInteger());
}else {
result = result + depthSum(ni.getList(), level+1);
}
}
return result;
}``````

public int depthSum(List<NestedInteger> nestedList) { return helper(nestedList, 1); } private int helper(List<NestedInteger> list, int depth) { int ret = 0; for (NestedInteger e: list) { ret += e.isInteger()? e.getInteger() * depth: helper(e.getList(), depth + 1); } return ret; }
https://discuss.leetcode.com/topic/41738/java-dfs-and-bfs-simple-code
``````    private int sum;
public int depthSum(List<NestedInteger> nestedList) {
if (nestedList == null) {
return 0;
}
sum = 0;
for (NestedInteger nestedInt : nestedList) {
depthSumHelper(nestedInt, 1);
}
return sum;
}

private void depthSumHelper(NestedInteger nestedInt, int depth) {
if (nestedInt.isInteger()) {
sum += depth * nestedInt.getInteger();
return;
}
for (NestedInteger innerInt : nestedInt.getList()) {
depthSumHelper(innerInt, depth + 1);
}
}``````
X. BFS
public int depthSum(List<NestedInteger> nestedList) { if(nestedList == null){ return 0; } int sum = 0; int level = 1; Queue<NestedInteger> queue = new LinkedList<NestedInteger>(nestedList); while(queue.size() > 0){ int size = queue.size(); for(int i = 0; i < size; i++){ NestedInteger ni = queue.poll(); if(ni.isInteger()){ sum += ni.getInteger() * level; }else{ queue.addAll(ni.getList()); } } level++; } return sum; }
https://discuss.leetcode.com/topic/44325/simple-java-iterative-solution-10-lines
``````    public int depthSum(List<NestedInteger> nestedList) {
int level = 1, total = 0;
while(nestedList.size() != 0){
for(NestedInteger nInt : nestedList){
if(nInt.isInteger())
total += nInt.getInteger() * level;
else
}
level++;
nestedList = next;
}
}``````
X. Using stack
https://zhengyang2015.gitbooks.io/lintcode/nested_list_weight_sum_551.html
DFS: 用一个stack来实现。遍历list，将当前元素和深度加入stack中。依次取出栈顶元素，若取出元素为数，则将其乘以其深度并加入sum，若取出元素是list，则将该list中元素依次加入stack中，同时这些元素的深度比之前取出元素深度＋1。
``````class Node{
int depth;
NestedInteger nestedInteger;
public Node(int depth, NestedInteger nestedInteger){
this.depth = depth;
this.nestedInteger = nestedInteger;
}
}
//DFS version
public int depthSum(List<NestedInteger> nestedList) {
Stack<Node> stack = new Stack<Node>();
for(int i = 0; i < nestedList.size(); i++){
stack.push(new Node(1, nestedList.get(i)));
}

int sum = 0;
while(!stack.isEmpty()){
Node curt = stack.pop();
if(curt.nestedInteger.isInteger()){
sum += curt.depth * curt.nestedInteger.getInteger();
}else{
List<NestedInteger> list = curt.nestedInteger.getList();
for(int i = 0; i < list.size(); i++){
stack.push(new Node(curt.depth + 1, list.get(i)));
}
}
}

return sum;
}``````
https://discuss.leetcode.com/topic/41357/2ms-easy-to-understand-java-solution/6
``````    public int depthSum(List<NestedInteger> nestedList) {
int res = 0;
Stack<Iterator<NestedInteger>> stk = new Stack<>();
stk.push (nestedList.iterator());

while (!stk.isEmpty()) {
Iterator<NestedInteger> itr = stk.peek ();
while (itr.hasNext()) {
NestedInteger n = itr.next();
if (n.isInteger()) res += n.getInteger() * stk.size ();
else {
stk.push (n.getList().iterator());
break; //??
}
}
if (!stk.peek ().hasNext()) stk.pop ();
}
return res;
}``````
http://coderchen.blogspot.com/2015/11/getweight-recurseive-structure.html
1 given [1, [2,3], [[4]]], return sum. 计算sum的方法是每向下一个level权重+1， 例子的sum = 1 * 1 + (2 + 3) * 2 + 4 * 3。follow up：每向下一个level 权重 - 1， sum = 3 * 1 +（2 + 3）* 2 + 4 * 1
public static class Node {}
public static class ValNode extends Node {
int val;
public ValNode(int v) {
this.val = v;
}
}

public static class ListNode extends Node {
List<Node> nodes;
public ListNode() {
nodes = new ArrayList<Node>();
}

}
}

public static int getWeightIncrease(Node node, int weight) {
int res = 0;
if (node instanceof ValNode) {
res += weight * ((ValNode) node).val;
} else {
ListNode list = (ListNode) node;
for (Node child : list.nodes) {
res += getWeightIncrease(child, weight + 1);
}
}
return res;
}