339. Nested List Weight Sum

Version #1 BFS

一刷

一道简单的bfs
不要被api吓到
每一层的weight是它的depth
所以记一下depth就好了

13.69 %
public class Solution {
    public int depthSum(List<NestedInteger> nestedList) {
        if (nestedList == null) return 0;
        int sum = 0;
        int depth = 0;
        Queue<NestedInteger> que = new LinkedList<>();
        for (NestedInteger ni : nestedList) que.offer(ni);
        NestedInteger curr = null;
        List<NestedInteger> neighbors = null;
        int levelSum = 0;
        while (!que.isEmpty()) {
            int size = que.size();
            depth++;
            while (size-- > 0) {
                curr = que.poll();
                if (curr.isInteger()) {
                    levelSum += curr.getInteger();
                } else {
                    neighbors = curr.getList();
                    for (NestedInteger neighbor : neighbors) {
                        que.offer(neighbor);
                    }
                }
            }
            sum += levelSum * depth;
            levelSum = 0;
        }
        return sum;
    }
}

Version #2 DFS

果然dfs比bfs快好多

按题意无脑做就行了

Runtime: 0 ms, faster than 100.00% of Java online submissions for Nested List Weight Sum.

Memory Usage: 36.4 MB, less than 75.85% of Java online submissions for Nested List Weight Sum.

class Solution {

    public int depthSum(List<NestedInteger> nestedList) {

        int res = 0;

        for (NestedInteger ni : nestedList) {

            res += sum(ni, 1);

        }

        return res;

    }

    

    private int sum(NestedInteger ni, int depth) {

        if (ni.isInteger()) {

          return depth * ni.getInteger();

        }

        int res = 0;

        for (NestedInteger nextNi : ni.getList()) {

            res += sum(nextNi, depth + 1);

        }

        return res;

    }

}