算法|7.从暴力递归到动态规划0

1.汉诺塔

题意：打印n层汉诺塔从最左边移动到最右边的全部过程

解题思路：

• 把字母抛掉，变成左中右三个盘子
• 多个盘子能一下到吗？不能，把上边的拿走，最下边的才能放到指位置(leftToRight)
• 上边的怎么拿，leftToMid。那它具体怎么拿，midToLeft…如此，需要6个子过程
• 他们之间互相调用，能够满足

核心代码：

public static void hanio(int n){leftToRight(n);
}
private static void leftToRight(int n) {if(n==1){System.out.println("Move 1 from left to right");return ;}leftToMid(n-1);System.out.println("Move "+n+" from left to right");midToRight(n-1);
}private static void midToRight(int n) {if(n==1){System.out.println("Move 1 from mid to right");return ;}midToLeft(n-1);System.out.println("Move "+(n)+" from mid to right");leftToRight(n-1);
}
private static void leftToMid(int n) {if(n==1){System.out.println("Move 1 from left to mid");return ;}leftToRight(n-1);System.out.println("Move "+(n)+" from left to mid");rightToMid(n-1);
}private static void rightToMid(int n) {if(n==1){System.out.println("Move 1 from right to mid");return ;}rightToLeft(n-1);System.out.println("Move "+(n)+" from right to mid");leftToMid(n-1);
}private static void rightToLeft(int n) {if(n==1){System.out.println("Move 1 from right to left");return ;}rightToMid(n-1);System.out.println("Move "+(n)+" from right to left");midToLeft(n-1);
}private static void midToLeft(int n) {if(n==1){System.out.println("Move 1 from mid to left");return ;}midToRight(n-1);System.out.println("Move "+(n)+" from mid to left");rightToLeft(n-1);
}

测试代码：

public static void main(String[] args) {hanio(3);
}

测试结果：

2.斐波那契

题意：求斐波那契数列第n项数

**解题思路：**略（之前写过）

核心代码：

private static int fib(int n) {if(n==1||n==2){return 1;}return fib(n-1)+fib(n-2);
}

测试代码及测试结果：

3.打印全排列（去重+不去重）

题意：1.打印一个字符串的全部排列 2.打印一个字符串的全部排列，要求不要出现重复的排列

解题思路：

• 当前位置和其他位置交换
• 清除/恢复现场
• 当前位置为index~N-1
• 其他位置index+1到N-1
• 产生的结果个数为n!个
• 这里也是，如果字符串为空，也产生结果，不过产生的结果是空串
• 注意：这里没有再用路径，而是使用的自己，所以加入结果集的时候是String.valueOf(str)
• 去重的思路有两种：过滤式、剪枝式，过滤即使用去重的集合，这里的剪枝策略则是使用visit数组（因为是字符串，所以大小定为256），判断这个元素在这个位置有没有出现过，若出现过则直接跳下一个

核心代码：

/*** 设置更为合适的参数*这里老师讲的版本没有再传中间参数，而是自己玩自己，相邻的交换，之后再恢复现场* @param test* @return*/
private static List<String> permutation(String test) {char[] str=test.toCharArray();String path="";List<String > list=new ArrayList<>();process1(str,0,list);return list;
}private static void process1(char[] str, int index, List<String> list) {if(index==str.length){list.add(String.valueOf(str));return ;}for (int i = index; i < str.length; i++) {swap(str,index,i);process1(str,index+1,list);swap(str,index,i);}
}private static void swap(char[] str, int a, int b) {char tmp=str[a];str[a]=str[b];str[b]=tmp;
}/*** 剪枝的方式去重，提前终止，效率更高* @param test* @return*/
private static List<String> noRepeatpermutation1(String test) {char[] str=test.toCharArray();String path="";List<String > list=new ArrayList<>();process2(str,0,list);return list;
}private static void process2(char[] str, int index, List<String> list) {if(index==str.length){list.add(String.valueOf(str));return ;}boolean[] visit=new boolean[256];for (int i = index; i < str.length; i++) {if(!visit[str[i]]){swap(str,index,i);process2(str,index+1,list);swap(str,index,i);visit[str[i]]=true;}}
}/*** 过滤方式去重* @param test* @return*/
private static HashSet<String> noRepeatpermutation2(String test) {char[] str=test.toCharArray();String path="";HashSet<String> set=new HashSet<>();process3(str,0,set);return set;
}private static void process3(char[] str, int index, HashSet<String> set) {if(index==str.length){set.add(String.valueOf(str));return ;}for (int i = index; i < str.length; i++) {swap(str,index,i);process3(str,index+1,set);swap(str,index,i);}
}

测试代码：

public static void main(String[] args) {String test="acc";List<String> ans1=permutation(test);List<String> ans2=noRepeatpermutation1(test);HashSet<String> ans3=noRepeatpermutation2(test);System.out.println("未去重");for (String str:ans1) {System.out.println(str);}System.out.println("================");System.out.println("剪枝版去重");for (String str:ans2) {System.out.println(str);}System.out.println("过滤版去重");for(String str:ans3){System.out.println(str);}
}

测试结果：

4.打印全部子序列（去重+不去重）

题意：1.打印一个字符串的全部子序列 2.打印一个字符串的全部子序列，要求不要出现重复字面值的子序列

解题思路：

• 数组为空也产生，结果不过是空集
• 在数组指针走到头了，收集结果
• path跟着一块玩

核心代码：

private static List<String> subs(String test) {char[] str=test.toCharArray();//空的话也产生，不过是一个空串String path="";List<String> ans=new ArrayList<>();process1(str,0,ans,path);return ans;
}
private static void process1(char[] str, int index, List<String> list, String path) {if(index==str.length){list.add(path);return ;}process1(str,index+1,list,path+str[index]);process1(str,index+1,list,path);
}/*** 去重版本* @param test* @return*/
private static HashSet<String> subsNoRepeat(String test) {char[] str=test.toCharArray();//空的话也产生，不过是一个空串String path="";HashSet<String> set=new HashSet<>();process2(str,0,set,path);return set;
}private static void process2(char[] str, int index, HashSet<String> set, String path) {if(index==str.length){set.add(path);return ;}process2(str,index+1,set,path+str[index]);process2(str,index+1,set,path);}

测试代码:

public static void main(String[] args) {String test="acc";List<String> ans1=subs(test);HashSet<String> ans2= subsNoRepeat(test);for(String str:ans1){System.out.println(str);}System.out.println("===============");for(String str:ans2){System.out.println(str);}
}

测试结果：

5.使用递归逆序栈

题意：给定一个栈，请逆序这个栈，不能申请额外的数据结构，只能使用递归函数

解题思路：

• 栈底的元素不断移除——成为返回值交给系统栈（子过程的栈）
• 子函数功能：移除栈底元素，上边的元素盖下来，返回移除的 栈顶元素

核心代码：

private static void reverse(Stack<Integer> stack) {if(stack.isEmpty()){return ;}int tmp=f(stack);reverse(stack);stack.push(tmp);
}
//f函数的功能是栈底元素移除掉
//上边的元素盖下来，返回移除的栈顶元素
private static int f(Stack<Integer> stack) {int ans=stack.pop();if(stack.isEmpty()){return ans;}else{int last=f(stack);stack.push(ans);return last;}
}

测试代码:

public static void main(String[] args) {Stack<Integer> stack=new Stack<>();stack.push(1);stack.push(2);stack.push(3);stack.push(4);stack.push(5);reverse(stack);while(!stack.isEmpty()){System.out.println(stack.pop());}
}

测试结果：

递归总结

例题总结：

• 汉诺塔：六个子过程，打印内容为“Move ”+n +“from xx to xxx”

• 斐波那契：无话可说，1||2||n-1||n-2

• 打印全部子序列：非去重：str,index,list,path,到头了加入，要与不要；去重：使用HashSet过滤，只是换了一种收集容器

• 打印全排列：

  总体思路，自己玩自己的（当前位置和可能成为当前位置的元素进行交换n!种可能）先交换，去下个位置，再回复现场（for循环）

  非去重：str,index，list

  去重：剪枝：拜访数组，256,判断当前字符在这个位置出现过没，出现过就要，没出现过就不要；过滤：换了个收集容器HashSet

• 使用递归逆序栈（不申请额外数据结构）：f的功能拿栈底元素:if,ans,else last,push(ans),