/**
* // 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) {
}
};
/**
* // 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 {
maxDepth := getMaxDepth(nestedList)
var cal func(nestedList []*NestedInteger, depth int) int
cal = func(nestedList []*NestedInteger, depth int) int {
res := 0
for i := range nestedList {
if nestedList[i].IsInteger() {
res += nestedList[i].GetInteger()*(maxDepth-depth+1)
} else {
res += cal(nestedList[i].GetList(), depth+1)
}
}
return res
}
return cal(nestedList, 1)
}
func getMaxDepth(nestedList []*NestedInteger) int {
res := 1
// 空列表的最大深度无效
if len(nestedList) == 0 {
return math.MinInt32
}
for i := range nestedList {
if !nestedList[i].IsInteger() {
res = max(res, getMaxDepth(nestedList[i].GetList())+1)
}
}
return res
}
func max(a, b int) int {
if a < b {
return b
}
return a
}
/**
* // 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 res = 0;
vector<vector<int>> integersListByDepth;
for (auto& nl : nestedList) {
dfs(nl, 0, integersListByDepth);
}
int N = integersListByDepth.size();
for (int i = 0; i < N; i++) {
for (int j = 0; j < integersListByDepth[i].size(); j++) {
res += integersListByDepth[i][j] * (N - i);
}
}
return res;
}
private:
void dfs(NestedInteger& ni, int depth, vector<vector<int>>& integersListByDepth) {
if (depth == integersListByDepth.size()) {
integersListByDepth.push_back(vector<int>());
}
if (ni.isInteger()) {
integersListByDepth[depth].push_back(ni.getInteger());
} else {
for (auto& nl : ni.getList()) {
dfs(nl, depth + 1, integersListByDepth);
}
}
}
};
/**
* // 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 depthSumInverse(List<NestedInteger> nestedList) {
int result = 0;
if(nestedList == null || nestedList.size() == 0){
return result;
}
Queue<NestedInteger> queue = new LinkedList<NestedInteger>();
Stack<Integer> levelSum = new Stack<Integer>();
for(int i = 0; i < nestedList.size(); i++){
queue.offer(nestedList.get(i));
}
while(!queue.isEmpty()){
int size = queue.size();
int eachLevel = 0;
for(int i = 0; i < size; i++){
NestedInteger temp = queue.poll();
if(temp.isInteger()){
eachLevel += temp.getInteger();
}else{
for(NestedInteger one : temp.getList()){
queue.offer(one);
}
}
}
levelSum.push(eachLevel);
}
int n = 1;
while(!levelSum.isEmpty()){
result += n * levelSum.pop();
n++;
}
return result;
}
}
# """
# 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:
res, level_sum = 0, 0
while nestedList:
next_level = []
for n in nestedList:
if n.isInteger():
level_sum += n.getInteger()
else:
next_level.extend(n.getList())
nestedList = next_level
res += level_sum
return res
