本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有,分而治之,深度搜索,动态规划,回溯,贪心等,结合这些思想再去思考如今很火的大数据,云计算和机器学习,是不是也别有一番风味呢? 踏上算法之路,风景这边独好!
01
—
通过这篇文章,你学到什么
通过这篇文章,我们可以进一步体会到深度优先搜索算法在具体问题中的应用,通过详细地示意图,深刻明白递归调用时的进栈,出栈过程;最后通过Leetcode 相似解法的题目进一步加深对深度搜索算法的理解。
02
—
搜索算法
搜索算法,常见的几种形式,深度优先,广度优先,二分搜索,应用搜索算法的前提是求解空间是有限的,然后在这个空间中找出满足题意的解。有些问题如果能用二分搜索,那是最高效的,因为每次都会使求解空间减掉一半。
03
—
DFS
Depth first search algorithm,它是首先沿着深度方向搜索,然后再在广度方向搜索的。例如,要求某个序列的全排列,就可以用深度优先搜索。
04
—
全排序深度搜索算法
1 某个序列的全排序算法题目
The set [1,2,3,…,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3): "123" "132" "213" "231" "312" "321"
2 题目分析
如何写出深度优先搜索的代码呢?
3 源码实现
public class Solution
{
public IList<IList<int>> GetPermutation(int n)
{
IList<IList<int>> rslt = new List<IList<int>>();
dfs(rslt, new List<int>(),1,n);
return rslt;
}
// start 是dfs抽出的一个关键参数
private void dfs(IList<IList<int>> rslt,
List<int> curItem,
int start,
int digits)
{
//找到一个解
if (curItem.Count == digits)
{
rslt.Add(new List<int>(curItem));
return;
}
//广度方向搜索
for (int i = 1; i <= digits; i++)
{
//跳过重复元素
if (curItem.Contains(i))
continue;
curItem.Add(i);
//深度方向上的递归
dfs(rslt, curItem, i,digits);
//后进栈的元素优先出栈
curItem.RemoveAt(curItem.Count - 1);
}
}
}
05
—
图解源码
dfs递归调用的进、出栈示意图
dfs 在深度方向递归进、出栈过程,广度方向首先遍历到1,但是不展开,而是在深度方向展开,1,2,3 的 dfs 依次入栈,出栈顺序依次为 3,2,1,1,如下图所示,
然后再在广度方向上搜索【补充,可以看出深度优先搜索在前,广度方向上搜索在后,所以叫做 DFS】,此时 广度方向 for 遍历到 i = 2,然后再在深度方向搜索,出栈顺序依次为 3,2,1,2,如下图所示,
同理,广度方向搜索到 i=3,然后再在深度方向搜索,出栈顺序依次为 3,2,1,3,如下图所示,
dfs 终止
06
—
融会贯通
1 Leetcode 78. Subsets
Given a set of distinct integers, nums, return all possible subsets. Note: The solution set must not contain duplicate subsets. For example, If nums = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
2 Leetcode 90. Subsets II
Given a collection of integers that might contain duplicates, nums, return all possible subsets.Note: The solution set must not contain duplicate subsets. For example, If nums = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
3 Leetcode 47. Permutations II
Given a collection of numbers that might contain duplicates, return all possible unique permutations.For example, [1,1,2] have the following unique permutations:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
4 Leetcode 131. Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. For example, given s = “aab”, Return
[ [“aa”,”b”], [“a”,”a”,”b”] ]
看看 Leetcode 上这些应用了 DFS 的题目,这些题目与 讲解的那道题思路非常相似,灵活运用的这个思考过程还是很重要的,仔细体会下吧。
以上答案的链接,请参考如下引用:
http://blog.csdn.net/column/details/14761.html?&page=1
本文分享自 程序员郭震zhenguo 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!