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

算法|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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

测试代码：

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

测试结果：

2.斐波那契

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

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

核心代码：

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

测试代码及测试结果：

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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

测试代码：

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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

测试结果：

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);

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

测试代码:

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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

测试结果：

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

测试代码:

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());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

测试结果：

递归总结

例题总结：

• 汉诺塔：六个子过程，打印内容为“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),