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

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

概念

深度优先搜索算法(英语: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上属于深度优先搜索算法分类下

原题提示

  1. /**

  2. * // This is the interface that allows for creating nested lists.

  3. * // You should not implement it, or speculate about its implementation

  4. * public interface NestedInteger {

  5. * // Constructor initializes an empty nested list.

  6. * public NestedInteger();

  7. *

  8. * // Constructor initializes a single integer.

  9. * public NestedInteger(int value);

  10. *

  11. * // @return true if this NestedInteger holds a single integer, rather than a nested list.

  12. * public boolean isInteger();

  13. *

  14. * // @return the single integer that this NestedInteger holds, if it holds a single integer

  15. * // Return null if this NestedInteger holds a nested list

  16. * public Integer getInteger();

  17. *

  18. * // Set this NestedInteger to hold a single integer.

  19. * public void setInteger(int value);

  20. *

  21. * // Set this NestedInteger to hold a nested list and adds a nested integer to it.

  22. * public void add(NestedInteger ni);

  23. *

  24. * // @return the nested list that this NestedInteger holds, if it holds a nested list

  25. * // Return null if this NestedInteger holds a single integer

  26. * public List<NestedInteger> getList();

  27. * }

  28. */

题意分析

根据题目提示的数据结构,观察NestedInteger的方法,isInteger()表示当前元素是否包含Integer数据,true代表是,false代表嵌套包含列表。getInteger()表示获取当前元素包含的Integer数值。根据题意,由于嵌套存储的数据结构,不难联想到典型的深度优先搜索思路

思路设计

对当前列表搜索时,若当前元素仅包含Integer数而非嵌套结构则计算当前节点元素(深度*Integer)值得出当前元素的权重再进行累加;若当前元素为嵌套的List结构可递归计算当前子列表的权重和

伪代码

  1. 一、声明dfs方法,dfs方法有两个参数,list列表以及节点深度;

  2. 1、声明int类型权重和变量sum=0;

  3. 2、循环遍历输入参数List<NestedInteger>列表;

  4. i.若列表元素为Integer非列表(嵌套子列表),计算当前元素的权重为Integer值*深度;将计算得到的权重值累加到总权重和变量sum中;

  5. ii.若列表元素非Integer而是嵌套子列表,则递归调用dfs方法计算列表的权重和,而此时元素深度需要加1

  6. 3、循环结束返回权重和sum


  7. 二、最外层元素节点深度为1,直接调用dfs方法传入列表list,以及深度1直接得到权重总和;

编码实践

  1. private int dfs(List<NestedInteger> list, int depth) {

  2. int sum = 0;

  3. for (NestedInteger e : list) {

  4. sum += e.isInteger() ? e.getInteger() * depth : helper(e.getList(), depth + 1);

  5. }

  6. return sum;

  7. }


  8. public int depthSum(List<NestedInteger> nestedList) {

  9. return helper(nestedList, 1);

  10. }

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

结语

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

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

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


原文始发于微信公众号(Aeiric):LeetCode进阶339-深度优先搜索(DFS)