概念
深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。
深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。
因发明“深度优先搜索算法”，约翰·霍普克洛夫特与罗伯特·塔扬在1986年共同获得计算机领域的最高奖：图灵奖。（摘自-维基百科）
原题
339. Nested List Weight Sum
Given a nested list of integers, return the sum of all integers in the list weighted by their depth.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Example 1:
Input: [[1,1],2,[1,1]]
Output: 10
Explanation: Four 1's at depth 2, one 2 at depth 1.
Example 2:
Input: [1,[4,[6]]]
Output: 27
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 42 + 63 = 27.
339. 嵌套列表权重求和
给定一个嵌套整数列表，返回按照深度优先搜索得出的所有元素的权重和
每个元素都是整数或者列表——列表的元素也同样是整数或列表
例1：
输入：[[1,1],2,[1,1]]
输出：10
说明：4个“1”深度为2，一个2深度为1.
例2：
输入：[1,[4,[6]]]
输出：27
说明：1个“1”深度为1，一个4深度为2，一个6深度为3；1 + 42 +63 = 27.
- 本题在LeetCode上属于深度优先搜多算法分类下
原题提示
/**
* // 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 null if this NestedInteger holds a single integer
* public List<NestedInteger> getList();
* }
*/
题意分析
根据题目提示的数据结构，观察NestedInteger的方法，isInteger()表示当前元素是否包含Integer数据，true代表是，false代表嵌套包含列表。getInteger()表示获取当前元素包含的Integer数值。根据题意，由于嵌套存储的数据结构，不难联想到典型的深度优先搜索思路
思路设计
对当前列表搜索时，若当前元素仅包含Integer数而非嵌套结构则计算当前节点元素（深度*Integer）值得出当前元素的权重再进行累加；若当前元素为嵌套的List结构可递归计算当前子列表的权重和
伪代码：
一、声明dfs方法，dfs方法有两个参数，list列表以及节点深度；
1、声明int类型权重和变量sum=0;
2、循环遍历输入参数List<NestedInteger>列表；
i.若列表元素为Integer非列表（嵌套子列表）,计算当前元素的权重为Integer值*深度；将计算得到的权重值累加到总权重和变量sum中;
ii.若列表元素非Integer而是嵌套子列表，则递归调用dfs方法计算列表的权重和，而此时元素深度需要加1；
3、循环结束返回权重和sum；
二、最外层元素节点深度为1，直接调用dfs方法传入列表list,以及深度1直接得到权重总和；
编码实践
private int dfs(List<NestedInteger> list, int depth) {
int sum = 0;
for (NestedInteger e : list) {
sum += e.isInteger() ? e.getInteger() * depth : helper(e.getList(), depth + 1);
}
return sum;
}
public int depthSum(List<NestedInteger> nestedList) {
return helper(nestedList, 1);
}
image
结语
本篇题目相对简单，重点是理解深度优先遍历思想和简单实践，无彩蛋。关于深度优先算法，后续还有进阶博客题解说明，敬请期待～
关注订阅号 获取更多干货～
网友评论