专栏首页Java小白成长之路回溯:系列经典题目

回溯:系列经典题目

前言

对于回溯算法,一开始接触感觉还是挺难的,随着刷到的题目的数量增多,慢慢也可以总结出来相应的套路出来。大家一起来看看下面的伪代码

public 返回值 backtrace(起始条件){
    if(满足条件){
        返回值;
    }
    for(所有可以的选择){
    	做出选择a;
        backtrace(更新条件);
        撤销选择a;
	}
}

当我们翻看我们所做过的所有回溯算法的相关题目时,其实可以发现使用的套路,都离不开上面的模板。

其实我们换一个思路来理解回溯算法,回溯说到底也就是一种穷举算法,尝试每一种可能,如果当前这种尝试计算到头都不符合最后的结果,那么我们就依次向后退步,再次尝试新的方案,并没有什么特别神秘的地方。

可是发现这个套路的同学应该也有很多,但是每次遇到回溯算法,依旧很难实现相关代码。其实主要原因在于我们有时候难以选取结束条件,还有就是不清楚我们到底有多少种选择。这才是大多数回溯算法困扰我们的地方。

下面我们一起来看3道比较经典的回溯算法题目,来找找感觉吧~

一、解数独

★LeetCode37 --- 解数独【困难】 ”

题目描述

如图所示:数独要求我们行、列以及九宫格内都不允许出现相同的数字,这样就可以构成一个数独了!

1.1 解题思路

题目会首先给我们一个不完整的9x9的数独,然后我们需要根据已有的信息,向里面添加数据,构成一个完整的数独。那么我们现在就按照上面的模板来完善这道题。

  • 可以做出的选择:每个格子只能选择字符1--9,而且只能对未填充的空格进行填写,所以我们首先可以确定自己的选择空间。
  • 结束条件:在填写数独的每一个方格时,我们选择从左上角开始,从左到右,一行一行进行填写,直到最后一个方格,所以当我们填写到最后一个方格时,就可以代表之前填写的方格都是成功的,至此也就结束了我们整个解数独的过程。
  • 每次更新的条件:通过结束条件我们可以看出,结束条件是依赖于填写的方格的位置的。由此我们可以推断出,每次的更新条件,也就是我们每次进行填写的方格的位置。

下面我们来实现一下我们的思路。

1.2 代码实现

    public void solveSudoku(char[][] board) {
        if(board == null || board.length != 9 || board[0].length != 9 ) return;//非法数独判断
        back(board , 0 , 0);//进入回溯
    }
    private boolean back(char[][] board , int row , int col){
        if(col == 9) return back(board , row+1 , 0);//处理边界情况,此时已经到达了最右边一列,进入下一行的迭代
        if(row == 9) return true;//此时已经遍历完了board[8][8],即已经全部遍历完了
        if(board[row][col] != '.') return back(board , row , col+1);//当前字符不是空字符
   
        for(char ch = '1' ; ch <= '9' ; ch++){
            if(isValid(board , row , col , ch)){//查看当前字符如果放在此处是否合法
                board[row][col] = ch;//如果合法,则此字符放置在此处
                if(back(board,row,col+1)) return true;//进入递归,查看当前解是否为最终解
                board[row][col] = '.';//如果不为最终解,则进行回溯
            }
        }
        return false;
    }
    private boolean isValid(char[][] board , int row , int col , char ch){
        for(int i = 0 ; i < 9 ; i++){
            if(board[row][i] == ch) return false;//对当前行进行遍历,查看是否有重复元素
            if(board[i][col] == ch) return false;//对当前列进行遍历,查看是否有重复元素
            if(board[(row/3)*3 + i/3][(col/3)*3 + i%3] == ch) return false;//对当前方格进行遍历,查看是否有重复元素
        }
        return true;
    }

二、N皇后

★leetcode51---N皇后【困难】 ”

题目描述

2.1 解题思路

首先拿到这道题目,小白是有点懵逼的,不清楚什么是“皇后”之间的攻击,经过一番查阅之后,可以将皇后之间的攻击类比为下面这种情况:

N皇后攻击示意图

也就是说,一个“皇后”会以她自己为中心,进行散射性攻击,所有处于“皇后”对角线,行和列的位置都会被“攻击”,并且这种攻击是一直延续的,并不会受距离的限制。

说到这里,是不是也很类似于上面的解数独的题目。

我们依旧可以按照上面的套路来完成这道题,不过这道题和上一个有一个区别在于,每一个空格只有两种状态,选择或者不选择放置“皇后”。

此处我们按照行来进行遍历,对于“N皇后”问题,每一行都会放置一个“皇后”。所以我们在查询的时候,只需要判断当前位置的上半部分即可,下半部分为空,当前行也是只有一个“皇后”的。在每次的更新条件时,可以仅仅更新下一次回溯时“皇后”所在的行数即可。

2.2 代码实现

    List<List<String>> res = new LinkedList<>();
    public List<List<String>> solveNQueens(int n) {
        if(n <= 0) return res;
        char[][] board = new char[n][n];
        for(int i = 0 ; i < n ; i++){
            Arrays.fill(board[i],'.');
        }
        back(board , n , 0 );
        return res;
    }
    private void back(char[][] board , int n , int row ){
        if(row == n){//完成了一种解法,皇后的数量等于n
            LinkedList<String> path = new LinkedList<>();
            for(int i = 0 ; i < n ; i++){
                StringBuilder sb = new StringBuilder();
                for(int j = 0 ; j < n ; j++){
                    sb.append(board[i][j]);
                }
                path.add(sb.toString());
            }
            res.add(path);
            return ;
        }
        for(int j = 0 ; j < n ; j++){
            if(isValid(board , n , row , j)){//当前位置可以放置皇后
                board[row][j] = 'Q';//做出选择
                back(board , n , row+1);
                board[row][j] = '.';//撤销选择
            }
        }
    }
    private boolean isValid(char[][] board , int n , int row , int col ){
        for(int i = 0 ; i < row ; i++){//判断当前列是否已经有皇后
            if(board[i][col] == 'Q') return false;
        }
        for(int left = col-1 , up = row-1 ; left >= 0 && up >= 0 ;left-- , up-- ){//判断左上
            if(board[up][left] == 'Q') return false;
        }
        for(int right = col + 1 , up = row - 1 ; right < n  && up >= 0 ; right++ , up--){//判断右上
            if(board[up][right] == 'Q') return false;
        }
        return true;
    }

三、组合

★leetcode77----组合【中等】 ”

题目描述

3.1 解题思路

对于此题,我们依旧使用回溯算法来进行实现。我们需要从1---n中,选取k个数字,来完成组合,我们按照顺序来依次选择不同的数字进行组合。

  • 每次的选择:我们每次选择的时候,应该将已经使用过的数据排除在外,每次的选择都是在剩余的数字中挑选。
  • 结束条件:我们使用一个链表path来保存每一次的选择数字,当链表的长度为k的时候,我们就完成了一次选择,所以结束条件应该以path的长度来判断。
  • 每次的更新条件:为了避免重复选择,我们在每次更新条件时,应该限制可选数字的范围,避免重复选择,由于我们是按照顺序来选择每一次的数据,所以,在每次更新条件的时候,应该将下一次可选的第一个数字传输进去。

由此我们再次结束回溯的三个步骤,开始代码实现。

3.2 代码实现

    List<List<Integer>> output = new LinkedList<>();//最后的结果
    List<Integer> path = new LinkedList<>();//保存每一次的组合
    public List<List<Integer>> combine(int n, int k) {
        if(n < k || n <= 0 || k <= 0) return output;
        backtrace(n , k , 1);
        return output;
    }
    private void backtrace(int n , int k , int start){
        if(path.size() == k){//当前组合是满足条件的
            output.add(new LinkedList(path));
            return;
        }
        for(int i = start ; i <= n ; i++){
            path.add(i);//做出选择
            backtrace(n , k , i+1);
            path.remove(path.size() - 1);//撤销选择
        }
    }

本文分享自微信公众号 - Java小白成长之路(Java_xiaobai),作者:鹏程万里

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 刷题第5篇:被包围的区域

    各位同学好!本周的刷题结果又来了!本周刷的一些题目里面,觉得下面这道题目比较有点意思吧!有时候我们容易陷入一个思想的误区里面,稍微使用一下逆向思维,可能会带来不...

    鹏-程-万-里
  • 剑指offer第11题:机器人运动范围

    此方法我们可以直接按照题目中的要求,将所有的方格全都访问一遍,由于所有的格子需要满足一个条件,连续性和单元格的坐标和小于n即可。

    鹏-程-万-里
  • 剑指offer第10题:矩阵中的路径

    根据题目要求,需要我们从一个已知矩阵中找到一个可以挨个形成给定字符串的路径。如果有这条路径的话,我们需要返回true,如果没有的话,我们返回false,并且相同...

    鹏-程-万-里
  • 【Leetcode】【python】Arranging Coins

    你有n枚硬币,想要组成一个阶梯形状,其中第k行放置k枚硬币。 给定n,计算可以形成的满阶梯的最大行数。 n是非负整数,并且在32位带符号整数范围之内。

    后端技术漫谈
  • LeetCode第28/35题

    Return the index of the first occurrence of needle in haystack, or -1 if needle ...

    用户3112896
  • 力扣79——单词搜索

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

    健程之道
  • hdu1021

    @坤的
  • 【leetcode算法-搜索插入位置】

    给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

    用户5640963
  • Android实现类似QQ对话框的@他人的整体解决方案

    在我们公司的新版APP中社区板块有个在回复回帖中有个@他们的功能,基本需求和QQ群组对话框里@群或组里任何一个成员类似。而数据传输方面,选择了直接传输富文本格式...

    1025645
  • P1268 树的重量 思维

    用户2965768

扫码关注云+社区

领取腾讯云代金券