原创智能优化,原创度检查,一键采集,文章组合(DFS快速入门DFS相关概念在非二叉树上的深度优先搜索)

　　原创智能优化,原创度检查,一键采集,文章组合(DFS快速入门DFS相关概念在非二叉树上的深度优先搜索)

　　DFS 入门

　　DFS 相关概念

　　在非二叉树的深度优先搜索中，90% 的问题要么是组合要么是排列。特别是复合类的深度优先搜索问题特别多。排列组合类的搜索问题本质上是一个“隐图”搜索问题。

　　隐式图搜索问题：

　　如果一个问题没有明确地告诉你什么是点什么是边，而是需要你去搜索，那么它就是一个隐式图搜索问题。所以对于这类问题，首先要分析什么是点，什么是边。

　　BFS 与 DFS

　　广度优先搜索的空间复杂度取决于宽度

　　深度优先搜索的空间复杂度取决于深度

　　我们在使用DFS的时候，需要注意三个要素：

　　DFS主要可以分为：

　　DFS分类问题模型判断条件时间复杂度

　　置换问题

　　找到所有满足条件的“组合”

　　组合中的元素与顺序无关

　　O(2^n * n)

　　置换问题

　　找到满足条件的所有“排列”

　　合成中的元素是顺序“相关的”

　　O(n! * n)

　　DFS时间复杂度的一般计算公式：

　　O(计划数量*构建每个计划的时间)

　　所以排列问题 = O(n! * n) 组合问题 = O(2^n * n)

　　算法模板

　　public ReturnType dfs(参数列表){

if(递归出口){

记录答案

return;

}

for(所有的拆解可能性){

修改所有参数

dfs(参数列表）;

还原所有被修改过的参数

}

return something;

//很多时候不需要return, 除了分治的写法

　　组合类组合DFS

　　首先，我们来提一个问题，让大家知道什么叫复合DFS：

　　LeetCode 71.子集

　　LeetCode 71. 的一个子集

　　给定一个整数数组 nums，其元素彼此不同。返回此数组的所有可能子集（幂集）。

　　解决方案集不能收录重复的子集。您可以按任何顺序返回解决方案集。

　　示例 1：

输入：nums = [1,2,3]

输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]

输出：[[],[0]]

　　解决方案：

　　class Solution {

public List subsets(int[] nums) {

//首先进行异常检测

if(nums == null){

return results;

}

//创建答案集合

List results = new ArrayList();

Arrays.sort(nums);

dfs(nums, 0 , new ArrayList(), results);

return results;

}

private void dfs(int[]nums,

int startIndex,

ArrayListsubset,

List results){

//直接加加的是reference，这时候后面pop也会让results里的对应pop

results.add(new ArrayList(subset));

for(int i = startIndex; i [1,2]

subset.add(nums[i]);

//去寻找以[1,2] 开头的子集

dfs(nums, i + 1, subset, results);

//[1,2] -> [1]

subset.remove(subset.size() -1 );

}

}

}

　　跟进：

　　克服上述问题后，请同学们思考这个问题：如果给定的集合是[1,2,2,3]，而我输出的子集中不允许有两个[1,2,3]，那怎么办我们改变搜索过程？

　　LeetCode 90.子集 ll

　　LeetCode 90. 子集 ll

　　给定一个可能收录重复元素的整数数组 nums，返回该数组的所有可能子集（幂集）。

　　说明: 解决方案集不能收录重复的子集。

　　例子：

　　输入: [1,2,2]

输出:

[

[2],

[1],

[1,2,2],

[2,2],

[1,2],

[]

]

　　这个问题是经典的全子集问题的后续问题。稍微想了想，看看这种有重复元素的集合是怎么处理的。

　　选择代表：从几个相同数量但顺序不同的小集合中取一个有序集合作为代表，丢弃剩余的无序集合。

　　class Solution {

public List subsetsWithDup(int[] nums) {

List results = new ArrayList();

if(nums == null){

return results;

}

Arrays.sort(nums);

dfs(nums, 0 , new ArrayList(), results);

return results;

}

private void dfs(int[]nums, int startIndex, ArrayList subset,

List results){

results.add(new ArrayList(subset));

for(int i = startIndex; i startIndex){

continue;

}

subset.add(nums[i]);

dfs(nums, i + 1, subset, results);

subset.remove(subset.size() -1 );

}

}

}

　　有没有可以完成去重工作的数据结构？答案自然是散列，所以我们可以散列所有的集合。每次我们将当前搜索到的子集子集放入结果集子集时，只要把这个集合作为key，如果对应的值不存在，就证明这个集合是一个之前没有出现过的新集合，那么将新集合放入子集中。

<p>public class Solution {

/**

* @param nums: A set of numbers.

* @return: A list of lists. All valid subsets.

*/

public List subsetsWithDup(int[] nums) {

List subsets = new ArrayList();

HashMap visited = new HashMap();

Arrays.sort(nums);

dfs(nums, 0, new ArrayList(), subsets, visited);

return subsets;

}

String getHash(List subset) {

String hashString = "";

for (int i = 0;i