Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/339.html
You are given a nested list of integers nestedList
. Each element is either an integer or a list whose elements may also be integers or other lists.
The depth of an integer is the number of lists that it is inside of. For example, the nested list [1,[2,2],[[3],2],1]
has each integer's value set to its depth.
Return the sum of each integer in nestedList
multiplied by its depth.
Example 1:
Input: nestedList = [[1,1],2,[1,1]] Output: 10 Explanation: Four 1's at depth 2, one 2 at depth 1. 1*2 + 1*2 + 2*1 + 1*2 + 1*2 = 10.
Example 2:
Input: nestedList = [1,[4,[6]]] Output: 27 Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 1*1 + 4*2 + 6*3 = 27.
Example 3:
Input: nestedList = [0] Output: 0
Constraints:
1 <= nestedList.length <= 50
- The values of the integers in the nested list is in the range
[-100, 100]
. - The maximum depth of any integer is less than or equal to
50
.
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
-
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(); } } ############ /** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * public interface NestedInteger { * // Constructor initializes an empty nested list. * public NestedInteger(); * * // Constructor initializes a single integer. * public NestedInteger(int value); * * // @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(); * * // Set this NestedInteger to hold a single integer. * public void setInteger(int value); * * // Set this NestedInteger to hold a nested list and adds a nested integer to it. * public void add(NestedInteger ni); * * // @return the nested list that this NestedInteger holds, if it holds a nested list * // Return empty list if this NestedInteger holds a single integer * public List<NestedInteger> getList(); * } */ class Solution { public int depthSum(List<NestedInteger> nestedList) { return dfs(nestedList, 1); } private int dfs(List<NestedInteger> nestedList, int depth) { int depthSum = 0; for (NestedInteger item : nestedList) { if (item.isInteger()) { depthSum += item.getInteger() * depth; } else { depthSum += dfs(item.getList(), depth + 1); } } return depthSum; } }
-
// 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: # def __init__(self, value=None): # """ # If value is not specified, initializes an empty list. # Otherwise initializes a single integer equal to value. # """ # # def isInteger(self): # """ # @return True if this NestedInteger holds a single integer, rather than a nested list. # :rtype bool # """ # # def add(self, elem): # """ # Set this NestedInteger to hold a nested list and adds a nested integer elem to it. # :rtype void # """ # # def setInteger(self, value): # """ # Set this NestedInteger to hold a single integer equal to value. # :rtype void # """ # # 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: def depthSum(self, nestedList: List[NestedInteger]) -> int: def dfs(nestedList, depth): depth_sum = 0 for item in nestedList: if item.isInteger(): depth_sum += item.getInteger() * depth else: depth_sum += dfs(item.getList(), depth + 1) return depth_sum return dfs(nestedList, 1) class Solution: # iterative def depthSum(self, nestedList): stack = [] for nestedInteger in nestedList: stack.append((1, nestedInteger)) ans = 0 while stack: depth, current = stack.pop() if current.isInteger(): ans += depth * current.getInteger() else: lst = current.getList() for nestedInteger in lst: stack.append((depth+1, nestedInteger)) return ans ############ # """ # 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)
-
/** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * function NestedInteger() { * * Return true if this NestedInteger holds a single integer, rather than a nested list. * @return {boolean} * this.isInteger = function() { * ... * }; * * Return the single integer that this NestedInteger holds, if it holds a single integer * Return null if this NestedInteger holds a nested list * @return {integer} * this.getInteger = function() { * ... * }; * * Set this NestedInteger to hold a single integer equal to value. * @return {void} * this.setInteger = function(value) { * ... * }; * * Set this NestedInteger to hold a nested list and adds a nested integer elem to it. * @return {void} * this.add = function(elem) { * ... * }; * * Return the nested list that this NestedInteger holds, if it holds a nested list * Return null if this NestedInteger holds a single integer * @return {NestedInteger[]} * this.getList = function() { * ... * }; * }; */ /** * @param {NestedInteger[]} nestedList * @return {number} */ var depthSum = function (nestedList) { const dfs = (nestedList, depth) => { let depthSum = 0; for (const item of nestedList) { if (item.isInteger()) { depthSum += item.getInteger() * depth; } else { depthSum += dfs(item.getList(), depth + 1); } } return depthSum; }; return dfs(nestedList, 1); };