339. Nested List Weight Sum & 364.Nested List Weight Sum II
Question 1
This question says that there is a special data type as follows:
This data structure provides several method interfaces to manipulate the data (shown in code 1).
The depth of an element is how many levels of list nesting he consists of. Find the sum of the products of the elements and the depths.
Algorithm 1
The first thing that comes to my mind with this topic is that the array looks like a tiled tree result or graph. Then the first level is the root, the second level is his child nodes, and so on. By traversing through them we can easily get information about the number of layers. Then by determining whether he is an integer at this level, we can decide whether to compute it or not.
I used the recursive way of writing bfs.
Code 1
/*
* // 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().
*
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) {
if (nestedList == null || nestedList.size() == 0) {
return 0.
}
int res = 0.
Queue<NestedInteger> queue = new LinkedList<>().
for (int i = 0; i < nestedList.size(); i++) {
queue.offer(nestedList.get(i)).
}
int depth = 0.
while (!queue.isEmpty()) {
depth++.
int size = queue.size().
for (int i = 0; i < size; i++) {
NestedInteger integer = queue.poll().
if (integer.isInteger()) {
res += depth*integer.getInteger().
} else {
for (int j = 0; j < integer.getList().size(); j++) {
queue.offer(integer.getList().get(j)).
}
}
}
}
return res.
}
}
Problem 2
The difference between this problem and the one above is that instead of calculating the sum of the product of the depth and the integer elements, we calculate the sum of the product of the weights and the integer elements. The value of the weight is equal to the maximum depth - the depth of the current element + 1.
Algorithm 2
The rest of the topic is unchanged, as it iterates once to find the maximum depth before iterating to find the sum.
I actually thought at the beginning of the same traversal, there should be a way to find both the maximum depth and the summation in another traversal. The knowledge was not implemented in the end, but I guess it is through recursion down to the bottom layer and then return the maximum value for the upper layer to calculate.
You can refer to the discussion forum on the official website. The official solution has an onepass solution but no explanation.
Code 2
class Solution {
int maxDepth = 0.
int res = 0.
public int depthSumInverse(List<NestedInteger> nestedList) {
for (NestedInteger ele : nestedList) {
getMaxDepth(ele, 1).
}
for (NestedInteger integer : nestedList) {
dfs(integer, 1).
}
return res.
}
private void dfs(NestedInteger integer, int depth) {
depth++.
if (integer.isInteger()) {
res += (maxDepth - depth + 1) * integer.getInteger().
} else {
for (NestedInteger ele : integer.getList()) {
dfs(ele, depth).
}
}
}
private void getMaxDepth(NestedInteger integer, int depth) {
depth++.
if (!integer.isInteger()) {
for (NestedInteger ele : integer.getList()) {
getMaxDepth(ele, depth).
}
}
maxDepth = Math.max(maxDepth, depth).
}
}
问题1
这个题目是说，有一个特殊的数据类型，如下：
这个数据结构提供了几个操作数据的方法接口（在代码1中展示）。
一个元素的深度，就是他有几层列表嵌套组成。求元素和深度的乘积的和。
算法1
这个题目，我首先想到的就是这个数组看起来就像一个平铺的树结果或者图。那么第一层就是根，第二层就是他的子节点，以此类推。通过遍历我们可以很容易的拿到他们的层数信息。再通过判断他在这一层是否是一个整数，来决定是否要计算。
我使用了bfs的递归写法。
代码1
/**
* // 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) {
if (nestedList == null || nestedList.size() == 0) {
return 0;
}
int res = 0;
Queue<NestedInteger> queue = new LinkedList<>();
for (int i = 0; i < nestedList.size(); i++) {
queue.offer(nestedList.get(i));
}
int depth = 0;
while (!queue.isEmpty()) {
depth++;
int size = queue.size();
for (int i = 0; i < size; i++) {
NestedInteger integer = queue.poll();
if (integer.isInteger()) {
res += depth*integer.getInteger();
} else {
for (int j = 0; j < integer.getList().size(); j++) {
queue.offer(integer.getList().get(j));
}
}
}
}
return res;
}
}
问题2
这个题目和上面题目有不同的地方是我们不再计算深度和整数元素的乘积和，而是计算权重和整数元素的乘积和。权重的值等于最大深度-当前元素深度+1。
算法2
这个题目其他的地方没什么变化，在遍历求和之前先遍历一次找到最大深度。
我其实一开始也想到了同样是遍历，应该有方法再一次遍历中既可以找到最大深度也可以求和计算。知识最后没有实现，猜测是通过递归不断向下直到最底层然后返回最大值供上层计算。
可以参考官方的网站的讨论区。官方的解答虽然有onepass解答但是并没有解释。
代码2
class Solution {
int maxDepth = 0;
int res = 0;
public int depthSumInverse(List<NestedInteger> nestedList) {
for (NestedInteger ele : nestedList) {
getMaxDepth(ele, 1);
}
for (NestedInteger integer : nestedList) {
dfs(integer, 1);
}
return res;
}
private void dfs(NestedInteger integer, int depth) {
depth++;
if (integer.isInteger()) {
res += (maxDepth - depth + 1) * integer.getInteger();
} else {
for (NestedInteger ele : integer.getList()) {
dfs(ele, depth);
}
}
}
private void getMaxDepth(NestedInteger integer, int depth) {
depth++;
if (!integer.isInteger()) {
for (NestedInteger ele : integer.getList()) {
getMaxDepth(ele, depth);
}
}
maxDepth = Math.max(maxDepth, depth);
}
}