Question
Formatted question description: https://leetcode.ca/all/339.html
339 Nested List Weight Sum
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)
Algorithm
Traverse the given nested linked list array, for each nested linked list object, call the dfs
function, assign a depth value of 1, and add up and return.
In the dfs
function, first determine whether it is an integer,
- If yes, it returns the current depth multiplied by an integer
- If not, then we traverse the nested array again, call the recursive function for each nested linked list, and add up the return value to return
Code
Java
-
import java.util.List; public class Nested_List_Weight_Sum { /** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * public interface NestedInteger { * * // @return true if this NestedInteger holds a single integer, rather than a nested list. * public boolean isInteger(); * * // @return the single integer that this NestedInteger holds, if it holds a single integer * // Return null if this NestedInteger holds a nested list * public Integer getInteger(); * * // @return the nested list that this NestedInteger holds, if it holds a nested list * // Return null if this NestedInteger holds a single integer * public List<NestedInteger> getList(); * } */ public class Solution_dfs { public int depthSum(List<NestedInteger> nestedList) { if (nestedList == null || nestedList.size() == 0) { return 0; } return depthSumHelper(nestedList, 1); } private int depthSumHelper(List<NestedInteger> list, int depth) { if (list.isEmpty()) { return 0; } int sum = 0; for (NestedInteger curr: list){ // for each in list, perform a dfs if (curr.isInteger()) { sum += curr.getInteger() * depth; } else { sum += depthSumHelper(curr.getList(), depth + 1); } } return sum; } } public class Solution_stack { /* 用一个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; } } 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 current = stack.pop(); if (current.nestedInteger.isInteger()) { sum += current.depth * current.nestedInteger.getInteger(); } else { List<NestedInteger> list = current.nestedInteger.getList(); for (int i = 0; i < list.size(); i++) { stack.push(new Node(current.depth + 1, list.get(i))); } } } return sum; } } // This is the interface that allows for creating nested lists. // You should not implement it, or speculate about its implementation private interface NestedInteger { // @return true if this NestedInteger holds a single integer, rather than a nested list. public boolean isInteger(); // @return the single integer that this NestedInteger holds, if it holds a single integer // Return null if this NestedInteger holds a nested list public Integer getInteger(); // @return the nested list that this NestedInteger holds, if it holds a nested list // Return null if this NestedInteger holds a single integer public List<NestedInteger> getList(); } }
-
// OJ: https://leetcode.com/problems/nested-list-weight-sum/ // Time: O(N) // Space: O(D) where D is the max depth of the list. class Solution { private: int depthSum(vector<NestedInteger>& nestedList, int depth) { int sum = 0; for (auto &i : nestedList) { if (i.isInteger()) sum += i.getInteger() * depth; else sum += depthSum(i.getList(), depth + 1); } return sum; } public: int depthSum(vector<NestedInteger>& nestedList) { return depthSum(nestedList, 1); } };
-
# """ # This is the interface that allows for creating nested lists. # You should not implement it, or speculate about its implementation # """ # class NestedInteger(object): # def isInteger(self): # """ # @return True if this NestedInteger holds a single integer, rather than a nested list. # :rtype bool # """ # # def getInteger(self): # """ # @return the single integer that this NestedInteger holds, if it holds a single integer # Return None if this NestedInteger holds a nested list # :rtype int # """ # # def getList(self): # """ # @return the nested list that this NestedInteger holds, if it holds a nested list # Return None if this NestedInteger holds a single integer # :rtype List[NestedInteger] # """ class Solution(object): def depthSum(self, nestedList): """ :type nestedList: List[NestedInteger] :rtype: int """ def helper(root, depth): res = 0 for nested in root: if nested.isInteger(): res += depth * nested.getInteger() else: res += helper(nested.getList(), depth + 1) return res return helper(nestedList, 1)