栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

[LeetCode]-回溯

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

[LeetCode]-回溯

前言

关于回溯算法的学习文章:回溯算法详解,labuladong的算法小抄

回溯其实就是对多叉树的遍历

78.子集

本题的递归决策树为:

那么对这棵树的遍历策略就是,每遍历一个节点,将当前节点表示的子集加入res集合,然后遍历儿子,儿子节点只能是在原数组中下标大于当前节点所对应元素的元素,否则会造成子集的重复性,比如对于2这个节点,向下只能选3而不能选1,因为1节点后续会选到2,那么会出现子集[1,2],如果在2这个节点之后选了1,那么会出现[2,1],违反了集合的元素不可重复性

class Solution {
    private List> res;
    //tmp记录每一步得到的子集
    private LinkedList tmp;
    public List> subsets(int[] nums) {
        res = new LinkedList<>();
        tmp = new LinkedList<>();
        backTrack(nums,0);
        return res;
    }
    //start表示下一步要遍历到的元素下标,用来防止出现重复的子集
    //比如[2,3],在选2的时候,可用考虑下一步选一下3看看是否有解
    //但在选3的时候,就不能考虑要不要往前去选个2,否则会出现选到最后的子集跟之前在选2的时候选出来的某个结果是重复的
    public void backTrack(int[] nums,int start){
        res.add(new ArrayList<>(tmp));
        for(int i = start;i < nums.length;i++){
            tmp.add(nums[i]);
            backTrack(nums,i + 1);
            tmp.removeLast();
        }
    }
}
90.子集Ⅱ

在78题的基础上,如果一个节点有多条值相同的树枝相邻,则只遍历第一条,剩下的都剪掉,不要去遍历

class Solution {
    private List> res;
    private LinkedList tmp;
    public List> subsetsWithDup(int[] nums) {
        res = new LinkedList<>();
        tmp = new LinkedList<>();
        //先排序方便后续判断是否有重复元素
        Arrays.sort(nums);
        backTrack(nums,0);
        return res;
    }
    public void backTrack(int[] nums,int start){
        res.add(new ArrayList<>(tmp));
        for(int i = start;i < nums.length;i++){
        	//判断是否重复
            if(i > start && nums[i] == nums[i - 1]){
                continue;
            }
            tmp.add(nums[i]);
            backTrack(nums,i + 1);
            tmp.removeLast();
        }
    }
}
39. 组合总和(每日一题)

与上面子集不同的地方在于,当前元素选了后面可以再选,也就是说每个值都可以有一条选自己的分支

class Solution {
    List> res;
    //记录当前的组合
    LinkedList track;
    //记录当前组合的和
    int trackSum;
    public List> combinationSum(int[] candidates, int target) {
        res = new LinkedList<>();
        track = new LinkedList<>();
        trackSum = 0;
        backtrack(candidates, 0, target);
        return res;
    }
    //start表示可以从start开始 (包含start) 产生分支
    void backtrack(int[] nums, int start, int target) {
        if (trackSum == target) {
            res.add(new LinkedList<>(track));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if(trackSum + nums[i] > target) continue; //剪枝,如果加上了会超过target那就不往这条分支上去。这个语句加不加差了1ms
            trackSum += nums[i];
            track.add(nums[i]);
            //传的start是 i 而不是 i + 1,因为可以再选自己
            backtrack(nums, i, target);
            trackSum -= nums[i];
            track.removeLast();
        }
    }
}
37. 解数独(每日一题)

从左到右从上到下填写每一个格子中的数字,枚举1到9看当前格子能不能填,如果能填就继续往后填写下一个格子,回溯之后继续看还有没有可以填的数字,直到1到9都枚举完了

class Solution {
    private boolean[][] row;
    private boolean[][] column;
    private boolean[][][] bucket;
    public void solveSudoku(char[][] board) {
        row = new boolean[9][10];  //row 数组记录每一行中每个数字是否已存在,共9行
        column = new boolean[9][10]; //cloumn 数组记录每一列中每个数字是否已存在,共9列
        //bucket数组记录每一个 3 * 3 的格子中每个数字是否已存在,共9个格子,分为三行三列
        //这样原来的大格子中每个小格(i,j)通过(i / 3,j / 3)即可映射到其所在的3 * 3格子中
        //例如原来大格子中(5,4),对应的3 * 3格子即为(1,1)
        bucket = new boolean[3][3][10];
        int m = board.length;
        int n = board[0].length;
        int c;
        for(int i = 0;i < m;i++){    //初始化标记数组
            for(int j = 0;j < n;j++){
                if(board[i][j] != '.'){
                    c =  board[i][j] - '0';
                    row[i][c] = true;
                    column[j][c] = true;
                    bucket[i / 3][j / 3][c] = true;
                }
            }
        }
        backtrack(board,0,0);
    }
    
    boolean backtrack(char[][] board, int i, int j) {  //搜索顺序为从左到右,从上到下
    	//i跟j的合法性不在要调用backtrack前判断,而是调用了再来判断是否合法,减去很多步骤
        if (j == 9) return backtrack(board, i + 1, 0);   //如果j到9了,说明要往下一行去设置
        if (i == 9) return true;    //如果i到9了,说明已经得到一个可行解了
        if (board[i][j] != '.') return backtrack(board, i, j + 1);  //原本不是空格的不需要我们设置
        for (char ch = '1'; ch <= '9'; ch++) {  //'1'到'9'枚举可能设的值
            int c = ch - '0';
            //如果(i,j)所在行或列或3 * 3小格中已经有了ch就不能选
            if (row[i][c] || column[j][c] || bucket[i / 3][j / 3][c]) continue;
            board[i][j] = ch;  //可以填ch。选了之后更新标记
            row[i][c] = true;
            column[j][c] = true;
            bucket[i / 3][j / 3][c] = true;
            if (backtrack(board, i, j + 1)) return true;  //继续搜索找到一个可行解,立即结束
            //回退
            board[i][j] = '.';
            row[i][c] = false;
            column[j][c] = false;
            bucket[i / 3][j / 3][c] = false;
        }
        return false;
    }
}
51. N 皇后

从上到下放置在每一行 i 中放置一个皇后 (以行为单位每次放置一个皇后,保证每一行只会有一个皇后),访问每一行时,枚举每一列 j,看当前这个格子 [i,j] 能否放置皇后,能放的条件是当前这一列 n 个格子,以及这个格子所在的从右上角到左下角的这条斜线上的所有格子,以及这个格子所在的从左上角到右下角的这条斜线上的所有格子,都没有放过皇后,只有同时满足这三个条件,才能在这个格子上放置皇后。
找到某一列可以放置的话就更新记录当前列,当前两条斜线已经有放置皇后了,然后继续放置下一行的皇后,回溯后继续往后继续枚举还有没有其它列也能放置皇后,每一列都不能的话就直接返回
那么如何标记每一列,每条从左上角到右下角的斜线以及每条从右上角到左下角的斜线上是否放置了元素?
列的很简单,直接用一个长度 n 的布尔数组标记第 i 列 (从 0 开始) 上是不是已经有皇后了
斜线的我们以 n = 4 为例,如下:

可以看出来,从右上角到左下角以及从左上角到右下角的斜线都是 7 条,也就是 2n - 1 条。对于从右上到左下 (指线的平行方向) 的线 (图中红色) 按顺序分别是第0,1,…,6 条,从左上到右下的线 (图中蓝色) 也按顺序是第0,1,…,6 条,设每个格子的坐标为 (level,i) ,都是从0开始。那么可以发现,(level,i) 格子所在的从右上到左下的线,是第 level + i 条,所在的从左上到右下的线,是第 level - i + n - 1 条。所以就可以用两个长度为 2n - 1 的布尔数组,分别表示每条从右上到左下以及从左上到右下的线上是否已放置了皇后。其他细节详见代码:

class Solution {
    private List> res;   //记录要返回的答案
    private char[][] board;           //标记整个n * n 棋盘的放置情况
    private boolean[] column;         //记录每一列中是否已有放置了皇后
    private boolean[] slashRightLeft; //记录 从右上角到左下角 各条斜线上是否已有放置了皇后
    private boolean[] slashLeftRight; //记录 从左上角到右下角 各条斜线上是否已有放置了皇后
    private int n;                    //皇后个数 n
    public void backTrack(int level){ //回溯函数,表示在第 level 行中放置一个皇后 (从0开始)
        if(level >= n){  //如果level到n了,说明棋盘上已经得到一个可行解了,将这个可行解加入到 res中
            List s = new LinkedList<>();
            for(int i = 0;i < n;i++){
                s.add(new String(board[i]));
            }
            res.add(s);
            return;
        }
        for(int i = 0;i < n;i++){  //枚举这一行的每一列看是否符合条件可以放置元素
            int rightLeft = level + i; //该格子对应的从右上到左下的斜线
            int leftRight = level - i + n - 1;  该格子对应的从左上到右下的斜线
            if(!column[i] && !slashRightLeft[rightLeft] && !slashLeftRight[leftRight]){
                board[level][i] = 'Q';
                column[i] = slashRightLeft[rightLeft] = slashLeftRight[leftRight] = true;
                backTrack(level + 1);
                //回退
                board[level][i] = '.';
                column[i] = slashRightLeft[rightLeft] = slashLeftRight[leftRight] = false;
            }
        }
    }
    public List> solveNQueens(int n) {
        res = new LinkedList<>();
        if(n == 1){ //n 为 1 的特例直接处理
            List s = new LinkedList<>();
            s.add("Q");
            res.add(s);
            return res;
        }
        this.n = n;
        board = new char[n][n];
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                board[i][j] = '.';
            }
        }
        column = new boolean[n];
        Arrays.fill(column,false);
        slashRightLeft = new boolean[2 * n - 1];
        Arrays.fill(slashRightLeft,false);
        slashLeftRight = new boolean[2 * n - 1];
        Arrays.fill(slashLeftRight,false);
        backTrack(0); //从第 0 行开始
        return res;
    }
}

52题 N皇后 II 是只需要返回可行解的个数,所以可以在这个代码的基础上将维护res改为维护可行解的个数即可

93. 复原 IP 地址

回溯函数 backTrack(int index,int offset) 表示从原字符串中 offset 位置开始 (包括 offset) 选数来凑出 IP 地址中第 index 个数 (index 从 0 开始)

class Solution {
    int[] numIndex = new int[4]; //存放那四个数
    private char[] chars;
    int sLength;
    List res = new LinkedList<>();
    public void backTrack(int index,int offset){
        if(index == 4){ //边界,当index增长到4,说明已经凑出了四个数,但是 offset 不等于字符串长度的话,说明后面还有数字没有被选,所以回溯
            if(offset == sLength) res.add(numIndex[0] + "." + numIndex[1] + "." + numIndex[2] + "." + numIndex[3]);
            return;
        }
        if(offset >= sLength) return;  //offset超出字符串范围
        if(chars[offset] == '0'){ //剪枝,如果第一位为 0 ,那么这一个数只能取 0
            numIndex[index] = 0;
            backTrack(index + 1,offset + 1);
            return;
        }
        int num = 0;
        //从offset 开始一个数一个数选
        for(int i = offset;i < sLength && i < offset + 3;i++){
            num = num * 10 + chars[i] - '0';
            if(num > 255) break;
            numIndex[index] = num;
            backTrack(index + 1,i + 1);
        }
    }
    public List restoreIpAddresses(String s) {
        sLength = s.length();
        if(sLength < 4 || sLength > 12) return res; // 剪枝,每个数最多只能为三位,所以整个串最多12位
        chars = s.toCharArray();
        backTrack(0,0);
        return res;
    }
}
46. 全排列

用一个 isVisited 布尔数组标记数组中的数是否已经被放入序列中,每次都遍历这个数组,将未被使用过的数加入序列,然后回退时删除这个数,继续使用下一个未被使用过的数

class Solution {
    List> res; //记录每一个全排列
    Deque tmp;      //记录当前得到的序列
    boolean[] isVisited;     //标记数组中的数在生成本次序列时已被访问过或未被访问过
    int len;                 //nums数组的长度
    public void backTrack(int[] nums){
    	//当isVisted数组中元素都为 true,即生成本次序列时所有数都已被使用过
    	//就说明当前得到的序列已经是一个全排列了,添加到res中。这也是回溯的边界。end就表示当前得到的是否是一个全排列
        boolean end = true;
        for(int i = 0;i < len;i++){
            if(!isVisited[i]){
                end = false;
                tmp.add(nums[i]);
                isVisited[i] = true;
                backTrack(nums);
                //回退
                tmp.remove();
                isVisited[i] = false;
            }
        }
        if(end){
            res.add(new ArrayList<>(tmp));
        }
    }
    public List> permute(int[] nums) {
        res = new LinkedList<>();
        len = nums.length;
        tmp = new LinkedList<>();
        isVisited = new boolean[len];
        backTrack(nums);
        return res;
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/956813.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号