364. Nested List Weight Sum II π ο
Descriptionο
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. Let maxDepth be the maximum depth of any integer.
The weight of an integer is maxDepth - (the depth of the integer) + 1.
Return the sum of each integer in nestedList multiplied by its weight.
Example 1:
Input: nestedList = [[1,1],2,[1,1]] Output: 8 Explanation: Four 1's with a weight of 1, one 2 with a weight of 2. 1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8
Example 2:
Input: nestedList = [1,[4,[6]]] Output: 17 Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1. 1*3 + 4*2 + 6*1 = 17
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. - There are no empty lists.
Solutionsο
Solution 1: DFSο
Let's assume the integers are $a_1, a_2, \cdots, a_n$, their depths are $d_1, d_2, \cdots, d_n$, the maximum depth is $\textit{maxDepth}$, then the answer is:
$$ a_1 \times \textit{maxDepth} - a_1 \times d_1 + a_1 + a_2 \times \textit{maxDepth} - a_2 \times d_2 + a_2 + \cdots + a_n \times \textit{maxDepth} - a_n \times d_n + a_n $$
which is:
$$ (\textit{maxDepth} + 1) \times (a_1 + a_2 + \cdots + a_n) - (a_1 \times d_1 + a_2 \times d_2 + \cdots + a_n \times d_n) $$
If we denote the sum of all integers as $s$, and the sum of each integer multiplied by its depth as $ws$, then the answer is:
$$ (\textit{maxDepth} + 1) \times s - ws $$
Therefore, we design a function $dfs(x, d)$, which starts searching from $x$ with depth $d$. The execution process of $dfs(x, d)$ is as follows:
We first update $\textit{maxDepth} = \max(\textit{maxDepth}, d)$;
If $x$ is an integer, then we update $s = s + x$, $ws = ws + x \times d$;
Otherwise, we recursively traverse each element $y$ of $x$, and call $dfs(y, d + 1)$.
We traverse the entire list, for each element $x$, we call $dfs(x, 1)$, and finally return $(\textit{maxDepth} + 1) \times s - ws$.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the number of integers.
Python3ο
# """
# 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 depthSumInverse(self, nestedList: List[NestedInteger]) -> int:
def dfs(x, d):
nonlocal maxDepth, s, ws
maxDepth = max(maxDepth, d)
if x.isInteger():
s += x.getInteger()
ws += x.getInteger() * d
else:
for y in x.getList():
dfs(y, d + 1)
maxDepth = s = ws = 0
for x in nestedList:
dfs(x, 1)
return (maxDepth + 1) * s - ws
Javaο
/**
* // 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 {
private int maxDepth;
private int ws;
private int s;
public int depthSumInverse(List<NestedInteger> nestedList) {
for (NestedInteger x : nestedList) {
dfs(x, 1);
}
return (maxDepth + 1) * s - ws;
}
private void dfs(NestedInteger x, int d) {
maxDepth = Math.max(maxDepth, d);
if (x.isInteger()) {
ws += x.getInteger() * d;
s += x.getInteger();
} else {
for (NestedInteger y : x.getList()) {
dfs(y, d + 1);
}
}
}
}
C++ο
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* public:
* // Constructor initializes an empty nested list.
* NestedInteger();
*
* // Constructor initializes a single integer.
* NestedInteger(int value);
*
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* bool isInteger() const;
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* int getInteger() const;
*
* // Set this NestedInteger to hold a single integer.
* void setInteger(int value);
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* void add(const NestedInteger &ni);
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The result is undefined if this NestedInteger holds a single integer
* const vector<NestedInteger> &getList() const;
* };
*/
class Solution {
public:
int depthSumInverse(vector<NestedInteger>& nestedList) {
int maxDepth = 0, ws = 0, s = 0;
function<void(NestedInteger&, int)> dfs = [&](NestedInteger& x, int d) {
maxDepth = max(maxDepth, d);
if (x.isInteger()) {
ws += x.getInteger() * d;
s += x.getInteger();
} else {
for (auto& y : x.getList()) {
dfs(y, d + 1);
}
}
};
for (auto& x : nestedList) {
dfs(x, 1);
}
return (maxDepth + 1) * s - ws;
}
};
Goο
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* type NestedInteger struct {
* }
*
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* func (n NestedInteger) IsInteger() bool {}
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* // So before calling this method, you should have a check
* func (n NestedInteger) GetInteger() int {}
*
* // Set this NestedInteger to hold a single integer.
* func (n *NestedInteger) SetInteger(value int) {}
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* func (n *NestedInteger) Add(elem NestedInteger) {}
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The list length is zero if this NestedInteger holds a single integer
* // You can access NestedInteger's List element directly if you want to modify it
* func (n NestedInteger) GetList() []*NestedInteger {}
*/
func depthSumInverse(nestedList []*NestedInteger) int {
var maxDepth, ws, s int
var dfs func(*NestedInteger, int)
dfs = func(x *NestedInteger, d int) {
maxDepth = max(maxDepth, d)
if x.IsInteger() {
ws += x.GetInteger() * d
s += x.GetInteger()
} else {
for _, y := range x.GetList() {
dfs(y, d+1)
}
}
}
for _, x := range nestedList {
dfs(x, 1)
}
return (maxDepth+1)*s - ws
}
TypeScriptο
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* If value is provided, then it holds a single integer
* Otherwise it holds an empty nested list
* constructor(value?: number) {
* ...
* };
*
* Return true if this NestedInteger holds a single integer, rather than a nested list.
* isInteger(): boolean {
* ...
* };
*
* Return the single integer that this NestedInteger holds, if it holds a single integer
* Return null if this NestedInteger holds a nested list
* getInteger(): number | null {
* ...
* };
*
* Set this NestedInteger to hold a single integer equal to value.
* setInteger(value: number) {
* ...
* };
*
* Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
* add(elem: NestedInteger) {
* ...
* };
*
* Return the nested list that this NestedInteger holds,
* or an empty list if this NestedInteger holds a single integer
* getList(): NestedInteger[] {
* ...
* };
* };
*/
function depthSumInverse(nestedList: NestedInteger[]): number {
let [maxDepth, ws, s] = [0, 0, 0];
const dfs = (x: NestedInteger, d: number) => {
maxDepth = Math.max(maxDepth, d);
if (x.isInteger()) {
ws += x.getInteger() * d;
s += x.getInteger();
} else {
for (const y of x.getList()) {
dfs(y, d + 1);
}
}
};
for (const x of nestedList) {
dfs(x, 1);
}
return (maxDepth + 1) * s - ws;
}
JavaScriptο
/**
* // 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 depthSumInverse = function (nestedList) {
let [maxDepth, ws, s] = [0, 0, 0];
const dfs = (x, d) => {
maxDepth = Math.max(maxDepth, d);
if (x.isInteger()) {
ws += x.getInteger() * d;
s += x.getInteger();
} else {
for (const y of x.getList()) {
dfs(y, d + 1);
}
}
};
for (const x of nestedList) {
dfs(x, 1);
}
return (maxDepth + 1) * s - ws;
};