Nested List Weight Sum

本文主要是介绍Nested List Weight Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这应是很简单最入门的dfs问题，但自己却犯了两个问题，

1. 一开始自己只是想着迭代，根本没意识到是dfs问题

2. 看看注释的那个bug，肉眼没发现，最后只能自己编程发现。。。。

/*** // 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 {public int depthSum(List<NestedInteger> nestedList) {int sum = 0;if (nestedList == null) {return sum;}List<NestedInteger> list = nestedList;sum = depthSumHelper(list, 1);return sum;}private int depthSumHelper(List<NestedInteger> nestedList, int depth) {if(nestedList == null || nestedList.size() == 0) {return 0;}int sum = 0;for (NestedInteger nestedInteger: nestedList) {if (nestedInteger.isInteger()) {sum = sum + nestedInteger.getInteger() * depth;} else {//sum = depthSumHelper(nestedInteger.getList(), depth + 1);sum = sum + depthSumHelper(nestedInteger.getList(), depth + 1);}}return sum;}}

完整测试

import java.util.LinkedList;
import java.util.List;public class NestedListWeightSum {public static void main(String[] args) {// TODO Auto-generated method stubNestedInteger n1 = new NestedInteger(1, null);NestedInteger n2 = new NestedInteger(1, null);NestedInteger n3 = new NestedInteger(1, null);NestedInteger n4 = new NestedInteger(1, null);List<NestedInteger> sublist1 = new LinkedList<>();sublist1.add(n1);sublist1.add(n2);NestedInteger list1 = new NestedInteger(null, sublist1);List<NestedInteger> sublist2 = new LinkedList<>();sublist2.add(n3);sublist2.add(n4);NestedInteger list2 = new NestedInteger(null, sublist2);NestedInteger n5 = new NestedInteger(2, null);List<NestedInteger> list = new LinkedList<>();list.add(list1);list.add(n5);list.add(list2);NestedListWeightSum NestedListWeightSum = new NestedListWeightSum();NestedListWeightSum.depthSum(list);}public int depthSum(List<NestedInteger> nestedList) {int sum = 0;if (nestedList == null) {return sum;}List<NestedInteger> list = nestedList;sum = depthSumHelper(list, 1);return sum;}private int depthSumHelper(List<NestedInteger> nestedList, int depth) {if(nestedList == null || nestedList.size() == 0) {return 0;}int sum = 0;for (NestedInteger nestedInteger: nestedList) {if (nestedInteger.isInteger()) {sum = sum + nestedInteger.getInteger() * depth;} else {sum = depthSumHelper(nestedInteger.getList(), depth + 1);}}return sum;}
}class NestedInteger {Integer value;List<NestedInteger> list;public NestedInteger (Integer value, List<NestedInteger> list) {this.value = value;this.list = list;}// @return true if this NestedInteger holds a single integer, rather than a nested list.public boolean isInteger() {if (value == null) {return false;} else {return true;}}// @return the single integer that this NestedInteger holds, if it holds a single integer// Return null if this NestedInteger holds a nested listpublic Integer getInteger() {return value;}// @return the nested list that this NestedInteger holds, if it holds a nested list// Return null if this NestedInteger holds a single integerpublic List<NestedInteger> getList() {return list;}
}

这篇关于Nested List Weight Sum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---