追根溯源——回溯算法

本文阅读 20 分钟
首页 代码,Java 正文

最近几天在leetcode上刷到排列组合这一类的问题多了起来.

.基本的解决思路就是“回溯算法”,乍一看感觉非常高大上,其实也就是披着多叉树遍历外套的暴力破解法,做多了就会发现这就像循环遍历数组一样,套路固定,故准备总结在此,以供交流探讨。

 

2020年9月15日10:04:30

第4次更次博客,今天的leetcode题目是解数独,用回溯法解的非常漂亮,忍不住想分享出来。

 

2020年9月18日09:42:44

第5次更新,今天的leetcode题目虽然是求排列组合的全排列,但是涉及到去重,还有一个涉及到去重的问题是 组合总和II,基本思路都是先进行排序,然后再做一系列操作。

 

 

 

举个例子:输出一串数字[1,2,3]的全排列[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]。

这个问题交给人类来解决的话肯定是先固定第一位为 1,然后第二位可以是 2,那么第三位只能是 3;然后可以把第二位变成 3,第三位就只能是 2 了;然后就只能变化第一位,变成 2,然后再穷举后两位,以此类推......

就像下面这样的一个树形结构:

img

当我们停留在每一个 节点上时,都需要做一个决策,例如停留在图中红色节点上时,有[1, 3]两个数字可以做选择,如果选择了1之后再选择数字3(最后一个数字只有一个选项),则已经找到了一个不重复的数字,这一次的选择就结束了,我们会退回红色的节点继续向右子树搜索,以此类推......直到找到左右的结果。

 

这其实就是回溯算法,中学的时候就已经不自觉地掌握了。我们可以抽象一点,把整个算法的解决模板给概括出来,即:

解决一个回溯问题,实际上就是一个决策树的遍历过程,确定了以下三个条件,问题就迎刃而解了:

  1. 路径:已经做出的选择
  2. 选择列表:当前可以做的选择
  3. 结束条件(递归出口):到达决策的底层,没有选择可做的条件

伪代码如下:

List<T> result = new ArrayList<>();
private void backtrack(路径, 选择列表){
    if(满足结束条件){
        result.add(路径);
        return;
    }
    
    for(选择 : 选择列表){
        做选择;
        backtrack(路径, 选择列表);
        撤销选择;
    }

}

上面蓝色文字“决策”对应的就是代码中的“做选择”,“结束”对应“满足结束条件”,“退回”对应“撤销选择”

 

其核心就是 for 循环里面的递归,在递归调用之前「做选择」,在递归调用之后「撤销选择」,特别简单。

 

多说无益,上例子。

 

2.1 leetcode 77 组合

img

评论区里面的图画的已经非常直观了,我这里直接引用一下

img

根据我上面给的三个条件,将其对应在本题中如下:

  1. 路径:就是图中红色方块部分,当然树干上面“取X”也是路径
  2. 选择列表:就是图中蓝色方块部分
  3. 结束条件:路径中包含k个数字时。

我们定义的函数其实就像是一个指针,将这棵树的所有节点都走一遍之后整个程序就执行完毕了,所得的结果就是正确结果。如何将这棵树所有的节点都走一遍?其实就是前序遍历,中序遍历,后序遍历:

private traverse(TreeNode root){

    for(TreeNode child : root.children){
        traverse(child);
    }

}

我们做选择以及撤销选择的动作正是在前序和后序的时间点做出的,即做了一个选择之后到下一个节点,将做的选择撤销以后回到上一个节点!

img

所以回溯算法的核心框架:

for(选择 : 选择列表){
        // 做选择
        将被选的项从候选表中删除;
        路径.add(选择);

        backtrack(路径, 选择列表);
        
        // 撤销选择
        路径.remove(选择);
        重新将被选的项加入候选表;
    }

我们只要在递归之前做出选择,在递归之后撤销刚才的选择,就能正确得到每个节点的选择列表和路径。

本题解决方案如下:

class Solution {

    private List<List<Integer>> result = new ArrayList<>();

    // 用一个栈来记录每一个组合
    private void findCombinations(int n, int k, int begin, Stack<Integer> pre){
        if(pre.size() == k){
            result.add(new ArrayList<>(pre));
            return;
        }

        for(int i = begin; i <= n; i ++){
            pre.push(i);
            findCombinations(n, k, i + 1, pre); // 从下一个数字开始取
            // 当前数字的情况已经全部取完,弹出栈顶元素
            pre.pop();
        }
    }

    public List<List<Integer>> combine(int n, int k) {
        if (n <= 0 || k <= 0 || n < k) {
            return result;
        }
        findCombinations(n, k, 1, new Stack<>());
        return result;
    }
}

这一部分就是递归出口(可以结合题意理解,我们只要找到k个数字就好)

img

每一个数字 i 就是要做的选择

img

返回用一个List来存储(当然其他的数据结构都可以~)

img

 撤销选择操作,其实就是做选择的逆动作

 img

2.2 leetcode 216 组合总和III

 

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。

示例 1:

输入: k = 3, n = 7

输出: [[1,2,4]]

 

 

 

这种找出总和为某数字的问题,套路也很固定,只需在回溯函数里多添加一个遍历target用于记录求和的目标是多少即可。

class Solution {

    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer> temp = new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        dfs(k, n, 1);
        return result;
    }

    private void dfs(int k, int sum, int start){
        if(k == 0 && sum == 0){ // 符合条件
            result.add(new ArrayList<>(temp));  // 注意深拷贝和浅拷贝!!必须是new一个新数组
            return;
        }
        if(k == 0 || sum < 0) return;   // 不符合条件

        for(int i = start; i <= 9; i ++){
            temp.add(i);
            dfs(k - 1, sum - i, i + 1);
            temp.remove(temp.size() - 1);   // 回溯
        }
        return;
    }

}

2.3 leetcode 60 组合总和III

给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。

 

按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:

     "123"

     "132"

     "213"

     "231"

     "312"

     "321"

给定 n 和 k,返回第 k 个排列。

img

leetcode上面的一个题解很优秀,这里引用一下。 

img

 

public String getPermutation(int n, int k) {
        int[] nums = new int[n];//生成nums数组
        for (int i = 0; i < n; i++){
            nums[i] = i + 1;
        }  
        boolean[] used = new boolean[n];//记录当前的索引的数是否被使用过
        return dfs(nums, new ArrayList<String>(), used, 0, n, k);
    }

    /**
     * @param nums      源数组
     * @param levelList 每一层的选择
     * @param used      数组的元素是否被使用过
     * @param depth     深度,也就是当前使用的元素的索引
     * @param n         上限值
     * @param k         第k个
     * @return 第k个排列
     */
    private String dfs(int[] nums, List<String> levelList, boolean[] used, int depth, int n, int k) {
        if (depth == n) {//触发出口条件,开始收集结果集
            StringBuilder res = new StringBuilder();
            for (String s : levelList){
                res.append(s);
            }
            return res.toString();
        }
        int cur = factorial(n - depth - 1);//当前的depth也就是索引,有多少排列数
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;//当前元素被使用过,做剪枝
            if (cur < k) {//当前的排列组合数小于k,说明就算这一层排完了,也到不了第k个,剪枝
                k -= cur;
                continue;
            }
            levelList.add(nums[i] + "");//list收的是string类型
            used[i] = true;//当前元素被使用过标记
            return dfs(nums, levelList, used, depth + 1, n, k);
        }
        return null;
    }


    //返回n的阶乘,如3!=3*2*1=6
    private int factorial(int n) {
        int res = 1;
        while (n > 0) {
            res *= n--;
        }
        return res;
    }

2.4 全排列II

给定一个可包含重复数字的序列,返回所有不重复的全排列。

img

涉及到去重的问题,一般思路都是将候选数组进行排序,然后再做一系列操作。这里我们选择对原数组排序,保证相同的数字都相邻,然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」,即如下的判断条件:

if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
    continue;
}

详细代码如下:

class Solution {

    private boolean[] used;
    private List<List<Integer>> result;

    public List<List<Integer>> permuteUnique(int[] nums) {
        used = new boolean[nums.length];
        result = new ArrayList<>();
        Arrays.sort(nums);

        backtrack(nums, new ArrayList<>(), 0);
        return result;
    }

    private void backtrack(int[] nums, List<Integer> path, int index){
        if(index >= nums.length){
            result.add(new ArrayList<Integer>(path));
            return;
        }

        for(int i = 0; i < nums.length; i ++){
            if(used[i]){
                continue;
            }
            // 只使用重复数字的第一个
            // !used[i - 1] 说明当前重复数字左边还有未使用过的
            if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){
                continue;
            }

            path.add(nums[i]);
            used[i] = true;
            backtrack(nums, path, index + 1);
            // 回溯
            used[i] = false;
            path.remove(path.size() - 1);

        }

    }
}

 

 当然排列组合问题当然不仅限于全排列问题,还有可能让我们从候选项中选出一些元素出来,就是所谓的求子序列。

leetcode 1079 活字印刷

你有一套活字字模 tiles,其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。

 

同样是明确三个条件:

  1. 路径:同上题,先前已经选择的字母组成的字符串。
  2. 选择列表:剩下可供选择的字母,即 title 中除了被用掉的字母之外的所有字母
  3. 结束条件:由于每一个结果的长度不是固定的,而且我们只需要统计个数,所以在生成"AA"的途中我们必然会经过"A",这是计数器也要进行累加。

这个题目算是比较特殊的,只用统计最后子序列的个数,所以在递归调用时不需要再传入路径和选择列表,不过在分析问题的时候还是要明确这两个概念,这样才不至于代码出错。

 

参考代码:

class Solution {

    int result = 0;

    public int numTilePossibilities(String tiles) {
        char[] counter = new char[26];
        for(int i = 0; i < tiles.length(); i ++){
            counter[tiles.charAt(i) - 'A'] ++;
        }
        backtrack(counter);
        return result;
    }

    private void backtrack(char[] counter){
        for(int i = 0; i < 26; i ++){
            // 剪枝,即排除无效选择
            if(counter[i] == 0) continue;
            // 进行一次具体选择,本题就是 i 计数器减 1
            counter[i] --;
            // 一次有效枚举,总的计数器加 1
            result ++;
            // 继续回溯:递归 + 选择(尽可能剪枝) + 回退之前的现场恢复
            backtrack(counter);
            // 回退之前,也就是进入另一分支之前,恢复当前分支的改动
            counter[i] ++;
        }
    
    }
}

由于并不需要输出最后得结果,所以只用将每个字母出现的频率统计出来就好(所幸英文字母的数量是可数的)。

img

一个选择就是选了一个字母,相应的频率减一就ok。

img

撤销选择就是将刚刚选择的字母重新放回候选列表中,即相应的字母频率加一。

img

 

上面的问题其实是讨巧的,英文单词个数只有26个,并且只用输出序列的个数就可以了。如果将字母换做数字,那么就还是要老老实实地按照回溯的流程去做。

leetcode 面试题 08.04 幂集

幂集。编写一种方法,返回某集合的所有子集。集合中不包含重复的元素。

说明:解集不能包含重复的子集。

img

分析的三个条件和上题类似,只不过是将字母变作数字。

由于是子序列,所以我们在从 0 到 length - 1 遍历候选数组时有一些数字是可以不选的,因此就会在递归调用时产生分叉,只需多考虑一种情况即可。

class Solution {

    List<List<Integer>> result = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0);
        return result;
    }

    private void dfs(int[] nums, int index){
        if(index >= nums.length){
            result.add(new ArrayList<>(temp));  // 注意浅拷贝
            return;
        }

        // 不选择当前数字
        dfs(nums, index + 1);

        // 选择当前数字
        temp.add(nums[index]);
        dfs(nums, index + 1);
        
        // 回溯
        temp.remove(temp.size() - 1);
    }
}

当遍历数组的索引值超出数组范围时就是返回条件:

img

有两种情况需要考虑:选择当前数字 / 不选当前数字 :

如果选择了当前数字的话就需要在结果集temp中进行添加

img

撤销选择操作就是将刚刚选择的数字从路径中删除即可: 

img

 

leetcode 679 24点游戏

一共有 4 个数和 3 个运算操作,因此可能性非常有限。一共有多少种可能性呢?

 

首先从 4 个数字中有序地选出 2 个数字,共有 4×3=12 种选法,并选择加、减、乘、除 4 种运算操作之一,用得到的结果取代选出的 2 个数字,剩下 3 个数字。

 

实现时,有一些细节需要注意。

 

  • 除法运算为实数除法,因此结果为浮点数,列表中存储的数字也都是浮点数。在判断结果是否等于 24 时应考虑精度误差,这道题中,误差小于 10^{-6}可以认为是相等。

 

  • 进行除法运算时,除数不能为 0,如果遇到除数为 0 的情况,则这种可能性可以直接排除。由于列表中存储的数字是浮点数,因此判断除数是否为 0 时应考虑精度误差,这道题中,当一个数字的绝对值小于 10^{-6}时,可以认为该数字等于 0。

img

一共有 4 个数和 3 个运算操作,因此可能性非常有限。

 

首先从 4 个数字中有序地选出 2 个数字,共有 4×3=12 种选法,并选择加、减、乘、除 4 种运算操作之一,用得到的结果取代选出的 2 个数字,剩下 3 个数字。

 

实现时,有一些细节需要注意。

 

  • 除法运算为实数除法,因此结果为浮点数,列表中存储的数字也都是浮点数。在判断结果是否等于 24 时应考虑精度误差,这道题中,误差小于 10^{-6}可以认为是相等。

 

  • 进行除法运算时,除数不能为 0,如果遇到除数为 0 的情况,则这种可能性可以直接排除。由于列表中存储的数字是浮点数,因此判断除数是否为 0 时应考虑精度误差,这道题中,当一个数字的绝对值小于 10^{-6}时,可以认为该数字等于 0。

 

class Solution {
    static final int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;

    public boolean judgePoint24(int[] nums) {
        List<Double> list = new ArrayList<Double>();
        for (int num : nums) {
            list.add((double) num);
        }
        return backtrack(list);
    }

    public boolean backtrack(List<Double> list) {
        if (list.size() == 0) {
            return false;
        }

        if (list.size() == 1) { 
            return Math.abs(list.get(0) - 24) < 1e-6;
        }

        int size = list.size();
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (i != j) {   // 选出来i,j这两个位置的数字做四则运算
                    List<Double> list2 = new ArrayList<Double>();
                    for (int k = 0; k < size; k++) {
                        if (k != i && k != j) { // 剩下的数字保持不变
                            list2.add(list.get(k));
                        }
                    }

                    for (int k = 0; k < 4; k++) {
                        if (k == ADD) { // 加法
                            list2.add(list.get(i) + list.get(j));
                        } else if (k == MULTIPLY) { // 乘法
                            list2.add(list.get(i) * list.get(j));
                        } else if (k == SUBTRACT) { // 减法
                            list2.add(list.get(i) - list.get(j));
                        } else if (k == DIVIDE) {   // 除法
                            if (Math.abs(list.get(j)) < 1e-6) { // 分母不能为0
                                continue;
                            } else {
                                list2.add(list.get(i) / list.get(j));
                            }
                        }
                        if (backtrack(list2)) {
                            return true;
                        }
                        // 回溯
                        list2.remove(list2.size() - 1);
                    }
                }
            }
        }
        return false;
    }
}

决策树的每一层表示棋盘的每一行,每个节点可以做的选择是在该行任意位置放置一个皇后。

路径:board,其中小于row的那些行都已经选好了放皇后的位置        选择列表:第row行的每一个位置        返回条件:row超出borad范围

 

class Solution {
    private List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        List<String> board = new ArrayList<>();
        for(int i = 0; i < n; i ++){
            String temp = "";
            for(int j = 0; j < n ; j ++){
                temp += '.';
            }
            board.add(temp);
        }
        backtrack(board, 0);
        return res;
    }
    // 路径:board,其中小于row的那些行都已经选好了放皇后的位置
    // 选择列表:第row行的每一个位置
    // 返回条件:row超出borad范围
    private void backtrack(List<String> board, int row){
        if(row == board.size()){
            res.add(new ArrayList<>(board));
            return;
        }
        int n = board.get(row).length();
        for(int col = 0; col < n; col ++){
            if(!valid(board, row, col)){
                continue;
            }
            char[] str = board.get(row).toCharArray();
            // 做选择      
            str[col] = 'Q';
            board.set(row, new String(str));
            // 回溯
            backtrack(board, row + 1);
            // 撤销选择
            str[col] = '.';
            board.set(row, new String(str));
        }
    }
    // 是否可以在该位置放置
    private boolean valid(List<String> board, int row, int col){
        int n = board.get(row).length();
        // 检查列
        for(int i = 0; i < n; i ++){
            if(board.get(i).charAt(col) == 'Q'){
                return false;
            }
        }
        // 检查右上方
        for(int i = row - 1, j = col + 1; i >= 0 && j < n; i --, j ++){
            if(board.get(i).charAt(j) == 'Q'){
                return false;
            }
        }
        // 检查左上方
        for(int i = row - 1, j = col - 1; i >=0 && j >= 0; i --, j --){
            if(board.get(i).charAt(j) == 'Q'){
                return false;
            }
        }
        return true;
    }
}

 

7.1 leetcode 39 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

所有数字(包括 target)都是正整数。

解集不能包含重复的组合。 

 

img

定义递归函数 backtrack(int[] candidates, inttarget, List<Integer> path, int startIndex) 表示当前在 candidates 数组的第 startIndex 位,还剩 target要组合,已经组合的列表为 path。

递归的终止条件为 target <= 0 或者 candidates 数组被全部用完。那么在当前的函数中,每次我们可以选择跳过不用第 startIndex 个数,即执行 backtrack(candidates, target, path, startIndex + 1)。也可以选择使用第 startIndex个数,即执行 dfs(candidates, target - candidates[startIndex ], combine, startIndex ).

注意到每个数字可以被无限制重复选取,因此搜索的下标仍为 startIndex 。

 

class Solution {

    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> path = new ArrayList<>();
        backtrack(candidates, target, path, 0);
        return result;
    }

    private void backtrack(int[] candidates, int target, List<Integer> path, int startIndex){
        if(startIndex == candidates.length){
            return;
        }

        if(target == 0){
            result.add(new ArrayList<Integer>(path));
            return;
        }

        // 不选当前数字
        backtrack(candidates, target, path, startIndex + 1);

        // 选当前数字
        if(target >= candidates[startIndex]){
            path.add(candidates[startIndex]);
            // 每个数字可以被无限制重复选取,因此搜索的下标仍为 startIndex
            backtrack(candidates, target - candidates[startIndex], path, startIndex);
            // 回溯
            path.remove(path.size() - 1);
        }
    }
}

7.2 组合总和II

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

 

img

和上面的题目框架是类似的,只不过上题要求数字可以无限次使用,本题要求数字只能被用一次,所以需要去重操作,一个简单的去重思路是将数组进行从小到大排序,当后面一个数字等于前面一个数字时直接continue。其余框架不变。

 

class Solution {

    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<Integer> path = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(candidates, target, path, 0);  
        return result;
    }

    private void backtrack(int[] candidates, int target, List<Integer> path, int startIndex){

        if(target == 0){
            result.add(new ArrayList<Integer>(path));
            return;
        }

        for(int i = startIndex; i < candidates.length; i ++){
            if(candidates[i] > target){
                break;
            }
            // 保证不重复
            if(i > startIndex && candidates[i] == candidates[i-1]){
                continue;
            }

            path.add(candidates[i]);
            backtrack(candidates, target - candidates[i], path, i + 1);

            path.remove(path.size() - 1);
        }
    }
}

leetcode 79 单次搜索

给定一个二维网格和一个单词,找出该单词是否存在于网格中。

 

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

img

设函数check(i,j,k) 判断以网格的 (i, j) 位置出发,能否搜索到单词 word[k..]

 

 

路径:当前匹配到的位置k

返回条件:k移动到word尾或者i,j超出二维数组边界

class Solution {
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; ++i) {
            for (int j = 0; j < board[i].length; ++j) {
                if (board[i][j] == word.charAt(0)) {
                    if (backtrack(board, word, i, j, 0)) return true;
                }
            }
        }
        return false;
    }

    private boolean backtrack(char[][] board, String word, int i, int j, int k){
        if (k == word.length()) {
            return true;
        }
        if (i < 0 || j < 0 || i >= board.length || j >= board[i].length) {
            return false;
        }
        
        if (word.charAt(k) != board[i][j]) {
            return false;
        }

        // 匹配当前位置
        char t = board[i][j];
        board[i][j] = '0';
        
        boolean res = backtrack(board, word, i + 1, j, k + 1) || 
        backtrack(board, word, i - 1, j, k + 1) || 
        backtrack(board, word, i, j + 1, k + 1) || 
        backtrack(board, word, i, j - 1, k + 1);
        // 回溯
        board[i][j] = t;
        return res;
    }
}

 

求解数独的思路就是对每一个格子所有可能的数字1-9进行穷举,基于此,我们可以写出代码框架:

public void solveSudoku(char[][] board) {
    backtrack(board, 0, 0);
}

// 从左上角(r,c)开始回溯求解数组
public void backtrack(char[][] board, int r, int c){
    int m = 9;
    int n = 9;
    // 对棋盘的每个位置进行穷举
    for (int i = r; i < m; i++) {
        for (int j = c; j < n; j++) {
            for (char ch = '1'; ch <= '9'; ch ++) {
                // 做选择
                board[i][j] = ch;
                // 继续穷举下一个
                backtrack(board, i, j + 1);
                // 撤销选择
                board[i][j] = '.';
            }
        }
    }
}

如果 j 到最后一列了我们应该从下一行开始继续,如果 i 到最后一行了我们就等于穷举完了所有情况,返回即可。为了减少复杂度,我们可以让backtrack函数返回值为boolean,如果找到一个可行解就返回 true,这样就可以阻止后续的递归。

class Solution {
    public void solveSudoku(char[][] board) {
        backtrack(board, 0, 0);
    }

    // 从左上角(r,c)开始回溯求解数组
    public boolean backtrack(char[][] board, int r, int c){
        int m = 9;
        int n = 9;
        if(c == n){
            // 到最后一列则从下一行开始
            return backtrack(board, r + 1, 0);
        }
        if(r == m){
            return true;
        }
        // 对每个位置穷举
        for(int i = r; i < m; i ++){
            for(int j = c; j < n; j ++){
                // 此处已经有数字
                if(board[i][j] != '.'){
                    return backtrack(board, i , j + 1);
                }

                for(char ch = '1'; ch <= '9'; ch ++){
                    if(!isValid(board, i, j, ch)){
                        continue;
                    }
                    board[i][j] = ch;
                    if(backtrack(board, i, j + 1)){
                        return true;
                    }
                    board[i][j] = '.';
                }
                // 穷举完仍没找到
                return false;
            }
        }
        return false;
    }

    public boolean isValid(char[][] board, int r, int c, char ch){
        for(int i = 0; i < 9; i ++){
            // 判断行是否有重复数字
            if(board[r][i] == ch){
                return false;
            }
            // 判断列是否有重复数字
            if(board[i][c] == ch){
                return false;
            }
            // 判断3×3区域内是否有重复数字
            if(board[(r/3)*3 + i/3][(c/3)*3 + i%3] == ch){
                return false;
            }
        }
        return true;
    }
}

 

回溯算法就是个多叉树的遍历问题,关键就是在前序遍历和后序遍历的位置做一些操作。

写回溯函数时,需要维护走过的路径和当前可以做的选择列表,当满足结束条件时,将路径记入结果集。

 

 

本文为互联网自动采集或经作者授权后发布,本文观点不代表立场,若侵权下架请联系我们删帖处理!文章出自:https://wangjiawei.blog.csdn.net/article/details/107957030
-- 展开阅读全文 --
安全面试之XSS(跨站脚本攻击)
« 上一篇 07-24

发表评论

成为第一个评论的人

热门文章

标签TAG

最近回复