## Saturday, June 25, 2016

### LeetCode 364 - Nested List Weight Sum II

Related: LeetCode 339 - Nested List Weight Sum
http://blog.csdn.net/qq508618087/article/details/51743408
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.
Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.
Example 1:
Given the list `[[1,1],2,[1,1]]`, return 8. (four 1's at depth 1, one 2 at depth 2)
Example 2:
Given the list `[1,[4,[6]]]`, return 17. (one 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 1*3 + 4*2 + 6*1 = 17)
1.  * public interface NestedInteger {
2.  *
3.  *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
4.  *     public boolean isInteger();
5.  *
6.  *     // @return the single integer that this NestedInteger holds, if it holds a single integer
7.  *     // Return null if this NestedInteger holds a nested list
8.  *     public Integer getInteger();
9.  *
10.  *     // @return the nested list that this NestedInteger holds, if it holds a nested list
11.  *     // Return null if this NestedInteger holds a single integer
12.  *     public List<NestedInteger> getList();
13.  * }
X. BFS
https://discuss.leetcode.com/topic/49041/no-depth-variable-no-multiplication/
Inspired by lzb700m's solution and one of mine. Instead of multiplying by depth, add integers multiple times (by going level by level and adding the unweighted sum to the weighted sum after each level).
``````public int depthSumInverse(List<NestedInteger> nestedList) {
int unweighted = 0, weighted = 0;
while (!nestedList.isEmpty()) {
List<NestedInteger> nextLevel = new ArrayList<>();
for (NestedInteger ni : nestedList) {
if (ni.isInteger())
unweighted += ni.getInteger();
else
}
weighted += unweighted;
nestedList = nextLevel;
}
return weighted;
}``````
http://www.cnblogs.com/grandyang/p/5615583.html

```    int depthSumInverse(vector<NestedInteger>& nestedList) {
int unweighted = 0, weighted = 0;
while (!nestedList.empty()) {
vector<NestedInteger> nextLevel;
for (auto a : nestedList) {
if (a.isInteger()) {
unweighted += a.getInteger();
} else {
nextLevel.insert(nextLevel.end(), a.getList().begin(), a.getList().end());
}
}
weighted += unweighted;
nestedList = nextLevel;
}
return weighted;
}```
https://discuss.leetcode.com/topic/49023/share-my-2ms-intuitive-one-pass-no-multiplication-solution
The idea is to pass the current found integer sum into the next level of recursion, and return it back again. So that we don't have to count the number of levels in the nested list.
``````    public int depthSumInverse(List<NestedInteger> nestedList) {
return helper(nestedList, 0);
}

private int helper(List<NestedInteger> niList, int prev) {
int intSum = prev;
List<NestedInteger> levelBreak = new ArrayList<>();

for (NestedInteger ni : niList) {
if (ni.isInteger()) {
intSum += ni.getInteger();
} else {
}
}

int listSum = levelBreak.isEmpty()? 0 : helper(levelBreak, intSum);

return listSum + intSum;
}``````
X. DFS

https://segmentfault.com/a/1190000005937820

``````public int DFS(List<NestedInteger> nestedList, int intSum) {
//关键点在于把上一层的integer sum传到下一层去，这样的话，接下来还有几层，每一层都会加上这个integer sum,也就等于乘以了它的层数
List<NestedInteger> nextLevel = new ArrayList<>();
int listSum = 0;
for (NestedInteger list : nestedList) {
if (list.isInteger()) {
intSum += list.getInteger();
} else {
}
}
listSum = nextLevel.isEmpty() ? 0 : DFS(nextLevel, intSum);
return listSum + intSum;
}

public int depthSumInverse(List<NestedInteger> nestedList) {
return DFS(nestedList, 0);
}``````

```    void DFS(vector<NestedInteger>& nestedList, int depth)
{
maxDepth = max(maxDepth, depth);
for(auto val: nestedList)
{
if(!val.isInteger()) DFS(val.getList(), depth+1);
else nums.push_back(make_pair(val.getInteger(), depth));
}
}

int depthSumInverse(vector<NestedInteger>& nestedList) {
if(nestedList.size() ==0) return 0;
DFS(nestedList, 1);
for(auto val: nums) result+= (maxDepth-val.second+1)*val.first;
return result;
}
private:
vector<pair<int, int>> nums;
int maxDepth = 0, result = 0;
```

```    private int maxDepth(List<NestedInteger> nestedList, int depth) {
int max = depth;
for(NestedInteger ni : nestedList) {
if (!ni.isInteger()) {
max = Math.max(max, maxDepth(ni.getList(), depth + 1));
}
}
return max;
}
private int sum(List<NestedInteger> nestedList, int depth) {
int sum = 0;
for(NestedInteger ni : nestedList) {
if (ni.isInteger()) {
sum += ni.getInteger() * depth;
} else {
sum += sum(ni.getList(), depth - 1);
}
}
return sum;
}
public int depthSumInverse(List<NestedInteger> nestedList) {
if (nestedList == null || nestedList.isEmpty()) return 0;
int max = maxDepth(nestedList, 1);
return sum(nestedList, max);
}```
X. BFS
https://discuss.leetcode.com/topic/49488/java-ac-bfs-solution
``````public int depthSumInverse(List<NestedInteger> nestedList) {
if (nestedList == null) return 0;
int prev = 0;
int total = 0;
for (NestedInteger next: nestedList) {
queue.offer(next);
}

while (!queue.isEmpty()) {
int size = queue.size();
int levelSum = 0;
for (int i = 0; i < size; i++) {
NestedInteger current = queue.poll();
if (current.isInteger()) levelSum += current.getInteger();
List<NestedInteger> nextList = current.getList();
if (nextList != null) {
for (NestedInteger next: nextList) {
queue.offer(next);
}
}
}
prev += levelSum;
total += prev;
}
}``````
What @dianhua1560 is trying to say is using `prev` in place of `levelSum` - updating `prev` with current level elements, and adding it to `total` at each level, allowing the previous elements to be added repeatedly at each level.
``````    while (!queue.isEmpty()) {
int size = queue.size();
// int levelSum = 0;
for (int i = 0; i < size; i++) {
NestedInteger current = queue.poll();
if (current.isInteger()) prev += current.getInteger(); // <-- prev is not reset to 0
List<NestedInteger> nextList = current.getList();
if (nextList != null) {
for (NestedInteger next: nextList) {
queue.offer(next);
}
}
}
//prev += levelSum;
total += prev;
}``````
http://www.cnblogs.com/grandyang/p/5615583.html

```    int depthSumInverse(vector<NestedInteger>& nestedList) {
int unweighted = 0, weighted = 0;
queue<vector<NestedInteger>> q;
q.push(nestedList);
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; ++i) {
vector<NestedInteger> t = q.front(); q.pop();
for (auto a : t) {
if (a.isInteger()) unweighted += a.getInteger();
else q.push(a.getList());
}
}
weighted += unweighted;
}
return weighted;
}```
https://discuss.leetcode.com/topic/49008/java-easy-to-understand-solution
http://fangde2.blogspot.com/2016/07/leetcode-q364-nested-list-weight-sum-ii.html
``````public class Solution {
Map<Integer, Integer> map = new HashMap<>();

public int depthSumInverse(List<NestedInteger> nestedList) {
int ret = 0;

//use dfs to travese the List and put (depth, number) to the map
dfs(nestedList, 1);

int maxDepth = Integer.MIN_VALUE;

//get the max depth
for (int n : map.keySet()) {
if (n>maxDepth)
maxDepth = n;
}

//get the sum
for (int n : map.keySet()) {
ret += (maxDepth-n+1)*map.get(n);
}

return ret;
}

void dfs(List<NestedInteger> nestedList, int depth) {

for (NestedInteger item : nestedList) {
if (item.isInteger()) {
Integer num = map.get(depth);
if (num == null) {
map.put(depth, item.getInteger());
}
else {
map.put(depth, map.get(depth) + item.getInteger());
}
}
else {
dfs(item.getList(), depth+1);
}
}
}
}``````
X.
https://discuss.leetcode.com/topic/49017/java-two-pass-dfs-solution
http://blog.csdn.net/jmspan/article/details/51747784
Java Two Pass DFS solution
``````    public int depthSumInverse(List<NestedInteger> nestedList) {
if(nestedList == null || nestedList.size() == 0) return 0;
int h = helper(nestedList);
int res = getSum(nestedList, h);
return res;
}
private int getSum(List<NestedInteger> l, int layer) {
int sum = 0;
if(l == null || l.size() == 0) return sum;
for(NestedInteger n : l) {
if(n.isInteger()) sum += n.getInteger() * layer;
else sum += getSum(n.getList(), layer - 1);
}
return sum;
}
private int helper(List<NestedInteger> l) {
if(l == null || l.size() == 0) return 0;
int max = 0;
for(NestedInteger n : l) {
if(n.isInteger()) max = Math.max(max, 1);
else max = Math.max(max, helper(n.getList()) + 1);
}
return max;
}``````
X. Using stack
http://www.programcreek.com/2014/08/leetcode-nested-list-weight-sum-ii-java/

[[1,1],2,[1,1]]：
1 1 1 1
2
[1,[4,[6]]]：
1
4
6

```    int depthSumInverse(vector<NestedInteger>& nestedList) {
int res = 0;
vector<vector<int>> v;
for (auto a : nestedList) {
helper(a, 0, v);
}
for (int i = v.size() - 1; i >= 0; --i) {
for (int j = 0; j < v[i].size(); ++j) {
res += v[i][j] * (v.size() - i);
}
}
return res;
}
void helper(NestedInteger &ni, int depth, vector<vector<int>> &v) {
vector<int> t;
if (depth < v.size()) t = v[depth];
else v.push_back(t);
if (ni.isInteger()) {
t.push_back(ni.getInteger());
if (depth < v.size()) v[depth] = t;
else v.push_back(t);
} else {
for (auto a : ni.getList()) {
helper(a, depth + 1, v);
}
}
}```

```    int depthSumInverse(vector<NestedInteger>& nestedList) {
int res = 0;
vector<int> v;
for (auto a : nestedList) {
helper(a, 0, v);
}
for (int i = v.size() - 1; i >= 0; --i) {
res += v[i] * (v.size() - i);
}
return res;
}
void helper(NestedInteger ni, int depth, vector<int> &v) {
if (depth >= v.size()) v.resize(depth + 1);
if (ni.isInteger()) {
v[depth] += ni.getInteger();
} else {
for (auto a : ni.getList()) {
helper(a, depth + 1, v);
}
}
}```