Version #1 BFS
一刷
39.18 %
public class Solution {
public int depthSumInverse(List<NestedInteger> nestedList) {
if (nestedList == null || nestedList.size() == 0) return 0;
int targetSum = 0;
Queue<NestedInteger> que = new LinkedList<>();
for (NestedInteger ni : nestedList) {
que.offer(ni);
}
int integerSum = 0;
NestedInteger curr;
while (!que.isEmpty()) {
int size = que.size();
while (size-- > 0) {
curr = que.poll();
if (curr.isInteger()) {
integerSum += curr.getInteger();
} else {
List<NestedInteger> children = curr.getList();
for (NestedInteger child : children) {
que.offer(child);
}
}
}
targetSum += integerSum;
}
return targetSum;
}
}
二刷
class Solution {
public int depthSumInverse(List<NestedInteger> nestedList) {
// 1 (layerSum)
// 1 (prevSum) 4(layerSum)
// 1 4 6
Queue<NestedInteger> que = new LinkedList<>();
for (NestedInteger ni : nestedList) {
que.offer(ni);
}
int prevSum = 0, sum = 0;
while (!que.isEmpty()) {
int size = que.size();
int layerSum = 0;
while (size-- > 0) {
NestedInteger curr = que.poll();
if (curr.isInteger()) {
layerSum += curr.getInteger();
continue;
}
for (NestedInteger ni : curr.getList()) {
que.offer(ni);
}
}
prevSum += layerSum;
sum += prevSum;
}
return sum;
}
}
No comments:
Post a Comment