回溯与递归

发表于 | 分类于 ， |
字数统计: 1.9k | 阅读时长 ≈ 8

前言

最近在leetcode刷题，对于平常不是很清楚的一些数据结构和算法重新回顾和巩固一遍

目的

了解回溯和递归的区别，另外弄清楚回溯的特点和应用场景

正文

回溯和递归的区别和联系

1
2
递归:递归是一种算法结构,函数调用本身,最直接的递归应用就是计算连续数的阶乘，计算规律：n!=(n-1)!*n，还有汉诺塔的实现
回溯:在按某种搜索策略搜索的过程中，当到达某一状态时，继续向前搜索已经确定不会得到正确答案的情况下，可以返回上一搜索状态，沿着新的可能性继续搜索。其求解过程的实质是一个先序遍历一棵“状态树”的过程

两者之间的联系:回溯多用递归实现

回溯的特点

1
2
3
搜索策略:符合递归算法，问题解决可以化为子问题，算法类似，规模减小;
控制策略:当遇到失败的搜索状态，需要返回上一状态，沿另外的路径搜索;
数据结构:一般用数组保存搜索过程中的状态、路径。

选择回溯的前提

1
2
3
选择：对于每个特定的解，肯定是由一步步构建而来的，而每一步怎么构建，肯定都是有限个选择，要怎么选择，这个要知道；同时，在编程时候要定下，优先或合法的每一步选择的顺序，一般是通过多个if或者for循环来排列
条件：对于每个特定的解的某一步，他必然要符合某个解要求符合的条件，如果不符合条件，就要回溯，其实回溯也就是递归调用的返回
结束：当到达一个特定结束条件时候，就认为这个一步步构建的解是符合要求的解了。把解存下来或者打印出来。对于这一步来说，有时候也可以另外写一个issolution函数来进行判断。注意，当到达第三步后，有时候还需要构建一个数据结构，把符合要求的解存起来，便于当得到所有解后，把解空间输出来。这个数据结构必须是全局的，作为参数之一传递给递归函数

回溯参数的设计

1
2
3
4
必须要有一个临时变量(可以就直接传递一个字面量或者常量进去)传递不完整的解，因为每一步选择后，暂时还没构成完整的解，这个时候这个选择的不完整解，也要想办法传递给递归函数。也就是，把每次递归的不同情况传递给递归调用的函数。
可以有一个全局变量，用来存储完整的每个解，一般是个集合容器（也不一定要有这样一个变量，因为每次符合结束条件，不完整解就是完整解了，直接打印即可）。
最重要的一点，一定要在参数设计中，可以得到结束条件。一个选择是可以传递一个量n，也许是数组的长度，也许是数量，等等。
要保证递归函数返回后，状态可以恢复到递归前，以此达到真正回溯。

扩展

#784 LetterCasePermutation 
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
/**
 * creambing.com Inc.
 * Copyright (c) 2016-2017 All Rights Reserved.
 */


package com.creambing.leetcode.backtracking;

import java.util.LinkedList;
import java.util.List;

/**
 * Class Name:LetterCasePermutation784
 * Description:字母大小写全排列
 *
 * @author Bing
 * @create 2019-01-07  20:52
 * @version v1.0
 */
public class LetterCasePermutation784 {

    public List<String> letterCasePermutation(String S) {
        //全局的结果集合，作为回溯入参，保存完整结果
        List<String> result = new LinkedList<>();
        //开始回溯，这里选用字符数组，方便遍历以及替换字符，同时还可以连接成完整结果
        backtracking(S.toCharArray(), 0, result);
        return result;
    }

    private void backtracking(char[] s, int pos, List<String> result) {
        result.add(new String(s));
        for (int j = pos; j < s.length; j++) {
            char ch = s[j];
            if (Character.isAlphabetic(ch)) {
                s[j] = flip(ch);
                backtracking(s, j+1, result);
                s[j]= ch;
            }
        }
    }

    private char flip(char ch){
        return Character.isUpperCase(ch)? Character.toLowerCase(ch):Character.toUpperCase(ch);
    }

    public static void main(String[] args) {
        String s ="ab14c";
        new LetterCasePermutation784().letterCasePermutation(s).forEach(System.out::println);
    }
}

思路根据上面的对于回溯的理解设计参数，我们从最简单的情景来设计程序，假设串是a,那么结果就是a,A,那么这个最简单的逻辑是什么了？先把当前串写入集合中，把第i个字母大小转换(数字不管)就是下面这段,要注意的是:要保证递归函数返回后，状态可以恢复到递归前，以此达到真正回溯,因此注释的那段很重要，要加上，否则回溯会有问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class LetterCasePermutation784 {
    
    private void backtracking(char[] s, int pos, List<String> result) {
            result.add(new String(s));
            for (int j = pos; j < s.length; j++) {
                char ch = s[j];
                if (Character.isAlphabetic(ch)) {
                    s[j] = flip(ch);
                    backtracking(s, j+1, result);
                    //s[j]= ch;
                }
            }
        }
}

运行结果截图

运行流程分析

Runtime: 10 ms, faster than 45.47% of Java online submissions for Letter Case Permutation.

#401 BinaryWatch(二进制手表) 
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
/**
 * creambing.com Inc.
 * Copyright (c) 2016-2017 All Rights Reserved.
 */


package com.creambing.leetcode.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * Class Name:BinaryWatch401
 * Description:二进制手表
 *
 * @author Bing
 * @version v1.0
 * @create 2019-01-08  19:00
 */
public class BinaryWatch401 {

    public List<String> readBinaryWatch(int num) {
        int[] hoursc = {1, 2, 4, 8};
        int[] minutec = {1, 2, 4, 8, 16, 32};
        List<String> result = new ArrayList<>();
        //我们想给了n个灯亮，那么我们正常就是先在hour中选，然后在minute中选，差不多想到下面这种逻辑
        List<Integer> hourList = new ArrayList<>();
        List<Integer> minuteList = new ArrayList<>();
        for (int i = 0; i < num; i++) {
            //这里面关于最后一个回溯参数先前没有考虑，getHour中i=0开始遍历的，这里设置参数的原因是选过了就不能再选了
            getHour(i, hourList, 0, hoursc, 0);
            getMinu(num - i, minuteList, 0, minutec, 0);
            for (int hour : hourList) {
                for (int minu : minuteList) {
                    result.add(hour+":"+(minu<10?"0"+minu:minu));
                }
            }
            //这里一定要清空
            hourList.clear();
            minuteList.clear();
        }
        return result;
    }

    private void getHour(int n, List<Integer> hourList, int hour, int[] hoursc, int index) {
        //这段可以不加，但是为了效率，加上
        if (n < 0) {
            return;
        }
        if (n == 0 && hour < 12) {
            hourList.add(hour);
        }
        for (int i = index; i < hoursc.length; i++) {
            getHour(n - 1, hourList, hour + hoursc[i], hoursc, i + 1);
        }
    }

    private void getMinu(int n, List<Integer> minuList, int minu, int[] minuc, int index) {
        if (n < 0) {
            return;
        }
        if (n == 0 && minu < 60) {
            minuList.add(minu);
        }
        for (int i = index; i < minuc.length; i++) {
            getMinu(n - 1, minuList, minu + minuc[i], minuc, i + 1);
        }
    }
}

这里拿到题目之后，感觉可以用回溯发，开始设计回溯参数
1.最开始的时候没有设计最后一个参数，for循环中i=0而不是index,这样导致选了之后在选，重复了，这里我们没有恢复状态，因为我们也没有改变状态，我们只是遍历取合适的值
2.另外一个小问题是组合的时候需要清空列表
Runtime: 3 ms, faster than 56.44% of Java online submissions for Binary Watch.

其他需要回溯方法解决的leetcode题目:https://leetcode.com/tag/backtracking/

参考资料

1.https://www.jianshu.com/p/4c5ccac18fac 递归2-回溯与递归 偏偏注定要落脚丶
2.https://blog.csdn.net/u014772862/article/details/51789015 回溯和递归区别 繁拾简忆
3.https://blog.csdn.net/sinat_27908213/article/details/80599460 回溯算法超通俗易懂详尽分析和例题 littlelufisher

Cream Bing wechat
subscribe to my blog by scanning my public wechat account