LeetCode进阶339-深度优先搜索(DFS)

1,074 阅读4分钟

概念

深度优先搜索算法(英语: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);
	}	

结语

本篇题目相对简单,重点是理解深度优先遍历思想和简单实践,无彩蛋。关于深度优先算法,后续还有进阶博客题解说明,敬请期待~

关注订阅号 获取更多干货~