一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1342|回复: 16
收起左侧

[算法题] 请教DFS和BFS

[复制链接] |试试Instant~ |关注本帖
抢楼 抢楼 本帖为抢楼帖,欢迎抢楼! 
love1point 发表于 2015-6-13 14:21:00 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 love1point 于 2015-6-13 20:43 编辑

有个问题困扰我有点久了,经常看到某贴子讨论说某题怎么做时,总有人回复,DFS, 或者BFS。然后就没了。我想知道,当你们说,DFS时,你们就把实现DFS的模板敲出来,然后修改一点去套用解决特定的题目吗?谁能给个具体一点的例子吗? 比如,你看到某题,说用DFS, 然后,接下来你怎么做啊,说出DFS之后怎么解决问题呢? 感激回答任何东西的任何人。


我用个例子问吧,比如 leetcode的word break 或者 combination sum这两道题有人就说用dfs做。我想知道当你们说完dfs,你们接下来怎么处理的?多谢。


我还是觉得这些题虽然思路简单,但实现起来还是不那么容易
2015fallcser 发表于 2015-6-13 14:53:54 | 显示全部楼层
说出dfs然后不就dfs了么。。。
回复

使用道具 举报

wny 发表于 2015-6-13 15:02:31 | 显示全部楼层
你要看DFS的对象是什么。 要是树,图什么的都好办。 接近于套模板。
要是状态空间的话,就不一样了。 通常可以设计递归进行状态空间搜索。

评分

1

查看全部评分

回复

使用道具 举报

billyli8866 发表于 2015-6-13 15:40:47 | 显示全部楼层
DFS用递归,一条路走到黑
BFS用队列,出一个进周围的。
这算是两种思想吧,具体怎么做要看具体题目吧

评分

2

查看全部评分

回复

使用道具 举报

stellari 发表于 2015-6-13 21:18:11 | 显示全部楼层
不说的原因是因为能用DFS解决的问题通常思路都是一样的——也就是,先找到第一步的所有可能,在每种第一步的可能下再试遍第二步的所有可能……以这种方式试遍所有的组合。但是如果中途发现某一个组合肯定没前途,则立刻放弃这个组合(Backtrack)。

比如Combination Sum,输入是[2, 3, 6, 7, 8], 7,我们要解决的是CombSum([2,3,6,7, 8], 7)

首先,第一步我们有2,3,6,7这4种选择,8因为超过sum,直接放弃。
如果第一步选了2,那么所剩的sum就变成了5;第二步就只有2, 3两种选择。如果第二步再选2,那么第三步的sum变成3,还是可以选[2, 3]……以此类推,直到sum变为0(找到解),或者没法选出<=sum的数字(没有解)。
如果第一步选了3,所剩的sum变成4,第二步就只有3这一种选择……
如果第一步选了6,所剩sum变成1,第二步没有办法选择,所以此解不可行。
……
以此类推。

这种DFS解法和在一个多叉树上的DFS没有本质区别。因为这种解法的实质就是把所有的组合编码到一个“Solution Tree”当中,然后用DFS在此树中找到符合条件的那些组合。

评分

3

查看全部评分

回复

使用道具 举报

 楼主| love1point 发表于 2015-6-13 22:42:33 | 显示全部楼层
stellari 发表于 2015-6-13 21:18
不说的原因是因为能用DFS解决的问题通常思路都是一样的——也就是,先找到第一步的所有可能,在每种第一步 ...

感谢你的又一次回复哈。

你的详细说明我觉得我还是能理解清楚,不是你说的不够好,从该算法思想到对应代码的实现,我还是觉得没那么容易。

我看了网上的别人答案,发现dfs的代码还真有那么一个套路或者说模板可以用。我先暂且把该模板给背诵好,多练几次,争取记忆下来。难一点的递归对我来说还是有点吃力,没那么轻松哈。
  1. public class Solution {
  2.     public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
  3.         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
  4.         ArrayList<Integer> curr = new ArrayList<Integer>();
  5.         
  6.         if(candidates == null || candidates.length == 0)
  7.         {
  8.             return result;
  9.         }
  10.         Arrays.sort(candidates);
  11.         combinationSum(candidates, target, 0, curr, result);
  12.         return result;
  13.     }
  14.    
  15.     public void combinationSum(int[] candidates, int target, int j, ArrayList<Integer> curr, ArrayList<ArrayList<Integer>> result)
  16.     {
  17.         //递归的终止条件,递归一定要有终止条件
  18.         if(target == 0)
  19.         {
  20.             ArrayList<Integer> temp = new ArrayList<Integer>(curr);
  21.             result.add(temp);
  22.             return;
  23.         }
  24.         
  25.         for(int i = j; i < candidates.length; i++)
  26.         {
  27.             //如果该元素大于target,超过了,肯定不符合,退出
  28.             if(target < candidates[i])
  29.             {
  30.                 return;
  31.             }
  32.             curr.add(candidates[i]);
  33.             //递归
  34.             combinationSum(candidates, target-candidates[i], i, curr, result);
  35.             //如果没找到,回溯
  36.             curr.remove(curr.size()-1);
  37.         }
  38.     }
  39. }
复制代码
回复

使用道具 举报

 楼主| love1point 发表于 2015-6-13 22:50:41 | 显示全部楼层
wny 发表于 2015-6-13 15:02
你要看DFS的对象是什么。 要是树,图什么的都好办。 接近于套模板。
要是状态空间的话,就不一样了。 通常 ...

谢谢回答,的确,dfs有个大概框架或模板可套。dfs往往又用递归来实现
回复

使用道具 举报

 楼主| love1point 发表于 2015-6-13 22:51:23 | 显示全部楼层
billyli8866 发表于 2015-6-13 15:40
DFS用递归,一条路走到黑
BFS用队列,出一个进周围的。
这算是两种思想吧,具体怎么做要看具体题目吧

是啊,dfs往往用递归来实现
回复

使用道具 举报

一剑终情 发表于 2015-6-14 03:27:35 | 显示全部楼层
你的问题应该在从idea到implementation之间的这一步上。当你看到别人说一个题目可以用某个算法解决之后,自己考虑下怎么实现那个算法(假设你对该算法的思想已经理解),如果实现不了,看看自己是哪里有困难,多看别人的代码,重点看该算法中自己有困难的部分。
回复

使用道具 举报

 楼主| love1point 发表于 2015-6-14 16:09:40 | 显示全部楼层
一剑终情 发表于 2015-6-14 03:27
你的问题应该在从idea到implementation之间的这一步上。当你看到别人说一个题目可以用某个算法解决之后,自 ...

最近这个是我的突破口哈,感谢你的建议
回复

使用道具 举报

 楼主| love1point 发表于 2015-6-14 19:20:40 | 显示全部楼层
感谢大家回复和自己发了这个帖子,我记下了dfs模板和 combination sum 和 subsets这两道题
回复

使用道具 举报

oio14644 发表于 2015-6-15 01:03:21 | 显示全部楼层
love1point 发表于 2015-6-13 22:42
感谢你的又一次回复哈。

你的详细说明我觉得我还是能理解清楚,不是你说的不够好,从该算法思想到对应 ...

curr.remove(curr.size()-1); 这句什么意思?
回复

使用道具 举报

 楼主| love1point 发表于 2015-6-15 07:49:03 | 显示全部楼层
oio14644 发表于 2015-6-15 01:03
curr.remove(curr.size()-1); 这句什么意思?

是回溯吧。

比如现在curr是[1,2,3],它抹掉3,剩下[1,2]
回复

使用道具 举报

 楼主| love1point 发表于 2015-6-28 19:03:26 | 显示全部楼层
问题  问题  问题   问题  问题  问题  问题   问题  问题


Path sum ii:  https://leetcode.com/problems/path-sum-ii/

发现所有dfs题目,为什么总要这三行代码的写法,我一直在想用 result.add(l) 这一行代替这三行。但总是不行。?求指教

   ArrayList<Integer> temp = new ArrayList<Integer>();
             temp.addAll(l);
             result.add(temp);
  1. /**
  2. * Definition for a binary tree node.
  3. * public class TreeNode {
  4. *     int val;
  5. *     TreeNode left;
  6. *     TreeNode right;
  7. *     TreeNode(int x) { val = x; }
  8. * }
  9. */
  10. public class Solution {
  11.     public List<List<Integer>> pathSum(TreeNode root, int sum) {
  12.         List<List<Integer>> result = new ArrayList();
  13.         if(root == null)
  14.         {
  15.             return result;
  16.         }
  17.         ArrayList<Integer> l = new ArrayList<Integer>();
  18.         l.add(root.val);
  19.         dfs(root, sum-root.val, l, result);
  20.         return result;
  21.     }
  22.    
  23.     public void dfs(TreeNode node, int sum, ArrayList<Integer> l, List<List<Integer>> result)
  24.     {
  25.         if(node.left == null && node.right == null && sum == 0)
  26.         {
  27.              ArrayList<Integer> temp = new ArrayList<Integer>();
  28.              temp.addAll(l);
  29.              result.add(temp);
  30.         }
  31.         
  32.         if(node.left != null)
  33.         {
  34.             l.add(node.left.val);
  35.             dfs(node.left, sum - node.left.val, l, result);
  36.             l.remove(l.size()-1);
  37.         }
  38.         
  39.         if(node.right != null)
  40.         {
  41.             l.add(node.right.val);
  42.             dfs(node.right, sum - node.right.val, l, result);
  43.             l.remove(l.size()-1);
  44.         }
  45.     }
  46. }
复制代码
回复

使用道具 举报

 楼主| love1point 发表于 2015-6-28 19:05:02 | 显示全部楼层
stellari 发表于 2015-6-13 21:18
不说的原因是因为能用DFS解决的问题通常思路都是一样的——也就是,先找到第一步的所有可能,在每种第一步 ...

讨论一下我14楼的问题?谢啦
回复

使用道具 举报

DK_BurNing 发表于 2015-7-8 05:01:12 | 显示全部楼层
love1point 发表于 2015-6-28 19:05
讨论一下我14楼的问题?谢啦

我的理解: Java 里面class是引用,你传进去l,l 下面会remove,remove之后你result里面的结果就会改变,就不对了。 其实你可以result.add(new ArrayList<Integer>(l)); 应该也是可以的。
回复

使用道具 举报

 楼主| love1point 发表于 2015-7-9 10:04:31 | 显示全部楼层
DK_BurNing 发表于 2015-7-8 05:01
我的理解: Java 里面class是引用,你传进去l,l 下面会remove,remove之后你result里面的结果就会改变, ...

这个result.add(new ArrayList<Integer>(l));  是可以的哈
thx
回复

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 02:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表