做了一阵时间的leetcode，多多少少已经做了150左右的题量了。做多了对题目也有自己的心得。从以前看题目的毫无头绪到现在的隐约抓住了一些规律性的东西。本篇是关于个人对leetcode上面典型DFS递归和深搜题目的总结整理，其中解题模式大同小异。本文会随着刷题的过程逐渐更新。对于本篇文章的主题，如果要抽象出来一个公共思想，应该是如下的样子：
def DFS(solution_Set, buildingAnswer, step)
if Avaliable(buildingAnswer) : # 如果当前构造的解是可用的解，则添加到最终解之中
solution_Set.add(buildingAnswer)
return
for bs in BuildingSpace: # 遍历构造空间，是当前构造解可添加处理操作的空间
if feasible(bs): # 如果当前遍历的操作对于当前阶段是可行的，则对当前构造解施加操作
Process(buildingAnswer, fs)
DFS(solution_Set, buildingAnswer, step + 1) # 在当前的处理上进入下一种处理，进一步搜索解
Restore(buildingAnswer, fs) # 从下一个状态搜索中返回，无论下一层是否是什么状态。 恢复本阶段的状态，搜索本阶段另外可施加的状态。
以下的题目都是属于一种类型的，只要无脑搜索配合适当的剪枝就可以了。
给定一个字符串，生成其中字符的所有的排列
public ArrayList<String> Permutation(String str) {
ArrayList<String> ret = new ArrayList<>();
Set<String> hel= new HashSet<>();
StringBuilder sb = new StringBuilder(str);
f(hel, sb, 0);
ret = new ArrayList<>(hel);
Collections.sort(ret);
return ret;
}
private void f(Set<String> hel, StringBuilder sb, int step){
if(step == sb.length()-1){
hel.add(sb.toString());
return;
}
for(int i = step; i < sb.length(); i++){
swap(sb,step,i);
f(hel, sb, step+1);
swap(sb,step, i);
//while(i+1<sb.length() && sb.charAt(i+1) == sb.charAt(i))i++;
}
}
private void swap(StringBuilder sb, int a, int b){
char tc = sb.charAt(a);
sb.setCharAt(a, sb.charAt(b));
sb.setCharAt(b, tc);
}
解析：该题注意，可能存在重复字符而且需要按照字典序输出。这时就要感谢Java方便的集合库了。唯一感觉代码中不好的地方就是使用了这个Set，肯定有方法避免重复字符串的生成。其中f函数是典型的深度优先遍历树的从根到叶子的框架式代码。
解法类似的题目有
46 Permutations -- 记得这题是某一年百度的笔试面试题。
22. Generate Parentheses
分析思路： 对于括号来说，有左括号和右括号（废话）。对于DFS搜索来说，如果不加限制的搜索，就会生成（2^N）的结果。但是题目中要求的是可用的括号组合，即"(())"是正确的,")())"是错误的。因此，只要在dfs递归处加上if限制就行了，起到剪枝作用。套用上面的DFS框架就可以快速的写出代码。
public List<String> generateParenthesis(int n) {
List<String> ret = new ArrayList<>();
StringBuilder sb = new StringBuilder();
dfs(ret,sb, 0,0, n);
return ret;
}
private void dfs(List<String> ret, StringBuilder sb, int ln, int rn, int n){
if(ln + rn == 2*n){
ret.add(new String(sb));
return;
}
if(ln < n){
sb.append("(");
dfs(ret, sb, ln+1, rn, n);
sb.deleteCharAt(sb.length()-1);
}
if(rn < ln){
sb.append(")");
dfs(ret, sb, ln, rn+1, n);
sb.deleteCharAt(sb.length()-1);
}
}
105. Construct Binary Tree from Preorder and Inorder Traversal
这是一个给定中序、先序，生成树的题目。
分析思路： 题目很简单，即和手动计算的思路一样。首先从先序序列中找到第一个，根据先序遍历的性质，它就是第一个根，然后拿着这个根到中序序列中能把中序序列划分成两个子序列，然后再递归的到先序中找下一个就是第二个根，然后再去中序中找。
public class Solution {
private int findpos(int [] a, int k){
for(int i = 0; i < a.length; i++){
if(a[i] == k)return i;
}
return -1;//wrong
}
TreeNode f(int[] preorder, int [] inorder, int l, int r){
TreeNode root = new TreeNode(preorder[rootind]);
int k = findpos(inorder, preorder[rootind]);
rootind++;
if(k != l) {
root.left = f(preorder, inorder,l, k-1);
}
if(k != r) {
root.right = f(preorder, inorder,k+1, r);
}
return root;
}
int rootind;
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder.length == 0) return null;
Integer rootind = 0;
return f(preorder,inorder, 0, preorder.length-1);
}
}