算法训练——剑指offer(回溯算法)

摘要

回溯算法是深度优先遍历的一种特殊的形式。同时也可以称为是键值算法。本博文将给出一般的回溯算法的解析模板和实例代码供大家参考和学习。

一、回溯算法原理与解题方法

dfs(){
 
    // 第一步，检查下标
 
    // 第二步：检查是否被访问过，或者是否满足当前匹配条件
 
    // 第三步：检查是否满足返回结果条件
 
    // 第四步：都没有返回，说明应该进行下一步递归

        // 标记已经访问过了

        dfs(下一次)

    // 第五步骤：回溯
        撤销访问标记
        撤销刚刚的操作
    
} 

public void main() {
    dfs(0, 0);
}

package DFS;

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

/**
 * @Classname 全排列46
 * @Description TODO
 * @Date 2023/3/6 21:01
 * @Created by xjl
 */
public class 全排列46 {

    public List permute(int[] nums) {
        List lists=new ArrayList();
        if (nums.length==0){
            return lists;
        }
        List list=new ArrayList();
        boolean[] visit=new boolean[nums.length];
        dfs(nums,0,visit,list,lists);
        return lists;
    }

    private void dfs(int[] nums, int index, boolean[] visit, List list, List lists) {
        if (index==nums.length){
            lists.add(new ArrayList(list));
            return;
        }
        for (int i=0;i 0 && nums[i] == nums[i - 1] && !visit[i - 1])) {
                continue;
            }
            list.add(nums[i]);
            visit[i] = true;
            dfs(nums, lists, idx + 1, list,visit);
            // 回溯算法
            visit[i] = false;
            list.remove(idx);
        }
    }
}

二、回溯算法练习题目 2.1 矩阵的路径问题

package 回溯算法;

import org.junit.Test;

/**
 * @Classname JZ12矩阵中的路径
 * @Description TODO
 * @Date 2022/2/6 8:22
 * @Created by xjl
 */
public class JZ12矩阵中的路径 {
//    public static int[][] dir = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}}; // 四个方向
//    public static boolean[][] visited = null; // visited[x][y]表示是否访问过matrix[x][y]
//    public static char[] path = null; // 路径
//    public static int count = 0; // 路径长度
//
//    public boolean hasPath(char[][] matrix, String word) {
//        visited = new boolean[matrix.length][matrix[0].length];
//        path = new char[word.length()];
//        // 从每个点开始DFS
//        for (int i = 0; i < matrix.length; i++) {
//            for (int j = 0; j < matrix[i].length; j++) {
//                if (dfs(matrix, i, j, word)) {
//                    return true;
//                }
//            }
//        }
//        return false;
//    }
//
//    private boolean dfs(char[][] matrix, int x, int y, String word) {
//        // 边界值判断
//        if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || visited[x][y] || count > word.length() || matrix[x][y] != word.charAt(count)) {
//            return false;
//        }
//        // 记录路径
//        visited[x][y] = true;
//        path[count++] = matrix[x][y];
//        // 路径长度相符, 直接返回true(前面的if里已经比较过字符了)
//        if (count == word.length()) {
//            return true;
//        }
//        // 继续递归寻找
//        for (int i = 0; i < dir.length; i++) {
//            if (dfs(matrix, x + dir[i][0], y + dir[i][1], word)) {
//                return true;
//            }
//        }
//        // 复原
//        count--;
//        visited[x][y] = false;
//        return false;
//    }

    // 表示方向
    public int[] dx = {0, -1, 0, 1};
    public int[] dy = {-1, 0, 1, 0};
    // 表示是否访问过了
    public boolean[][] vis;
    //表示的路径
    StringBuilder sb = new StringBuilder();
    // 表示的路径的长度
    int count1 = 0;
    // 表示长和宽
    int row;
    int len;

    public boolean hasPath2(char[][] matrix, String word) {
        row = matrix.length;
        if (row == 0) {
            return false;
        }
        len = matrix[0].length;
        vis = new boolean[row][len];

        for (int x = 0; x < row; x++) {
            for (int y = 0; y < len; y++) {
                if (dfs1(matrix, x, y, vis, sb, word)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs1(char[][] matrix, int x, int y, boolean[][] vis, StringBuilder sb, String word) {
        if (x >= row || x < 0 || y >= len || y < 0 || vis[x][y] || count1 > word.length() || matrix[x][y] != word.charAt(count1)) {
            return false;
        }
        vis[x][y] = true;
        sb.append(matrix[x][y]);
        count1++;
        if (count1 == word.length()) {
            return true;
        }
        for (int i = 0; i < 4; i++) {
            int newx=x+dx[i];
            int newy=y+dy[i];
            if (dfs1(matrix, newx, newy, vis, sb, word)) {
                return true;
            }
        }
        vis[x][y] = false;
        count1--;
        sb.deleteCharAt(sb.length() - 1);
        return false;
    }

    @Test
    public void test() {
        char[][] matrix={{'a','b'},{'c','d'}};
        hasPath2(matrix,"abcd");
    }
}

2.2 机器人的运动范围问题

package 回溯算法;

/**
 * @Classname JZ13机器人的运动范围
 * 

 * 有的题目是的四个方向 上下左右一起
 * 

 * 有的是题目是两个方向 向下和向右边
 * 

 * 

 * 有的是需要回溯
 * 

 * 有的是不需要回溯
 * @Description
 * @Date 2022/2/6 9:52
 * @Created by xjl
 */
public class JZ13机器人的运动范围 {

    // 表示方向
    public int[] dx = {0, -1, 0, 1};
    public int[] dy = {-1, 0, 1, 0};
    int count = 0;

    public int movingCount2(int threshold, int rows, int cols) {
        boolean[][] vis = new boolean[rows][cols];
        dfs1(threshold, 0, 0, rows, cols, vis);
        return count;
    }

    private void dfs1(int threshold, int x, int y, int rows, int cols, boolean[][] vis) {
        if (x < 0 || y < 0 || x >= rows || y >= cols || !vis[x][y]) {
            return;
        }
        if (helper(x, y)  0) {
            sum += x % 10;
            x /= 10;
        }
        while (y > 0) {
            sum += y % 10;
            y /= 10;
        }
        return sum;
    }
}

2.3 二叉树的所有的路径

package 回溯算法;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashSet;

/**
 * @Classname JZ38所有的路径
 * @Description TODO
 * @Date 2022/2/6 9:37
 * @Created by xjl
 */
public class JZ38所有的路径 {

    public ArrayList Permutation2(String str) {
        ArrayList list = new ArrayList();
        if (str.length() == 0) {
            return list;
        }
        boolean[] vis = new boolean[str.length()];
        StringBuilder sb = new StringBuilder();
        dfs1(str, 0, sb, list, vis);
        //去重复
        ArrayList ans = new ArrayList(new HashSet(list));
        return ans;
    }

    private void dfs1(String str, int index, StringBuilder sb, ArrayList list, boolean[] vis) {
        if (index == str.length()) {
            list.add(sb.toString());
            return;
        }
        for (int i = 0; i < str.length(); i++) {
            if (!vis[i]) {
                vis[i] = true;
                sb.append(str.charAt(i));
                dfs1(str, index + 1, sb, list, vis);
                sb.deleteCharAt(sb.length() - 1);
                vis[i] = false;
            }
        }
    }

    @Test
    public void test() {
        ArrayList list = Permutation2("aab");
        for (String s : list) {
            System.out.print(s + " ");
        }
    }
}

2.4 全排列问题

 46. 全排列

package DFS;

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

/**
 * @Classname 全排列46
 * @Description TODO
 * @Date 2023/3/6 21:01
 * @Created by xjl
 */
public class 全排列46 {

    public List permute(int[] nums) {
        List lists=new ArrayList();
        if (nums.length==0){
            return lists;
        }
        List list=new ArrayList();
        boolean[] visit=new boolean[nums.length];
        dfs(nums,0,visit,list,lists);
        return lists;
    }

    private void dfs(int[] nums, int index, boolean[] visit, List list, List lists) {
        if (index==nums.length){
            lists.add(new ArrayList(list));
            return;
        }
        for (int i=0;i 0 && nums[i] == nums[i - 1] && !visit[i - 1])) {
                continue;
            }
            list.add(nums[i]);
            visit[i] = true;
            dfs(nums, lists, idx + 1, list,visit);
            // 回溯算法
            visit[i] = false;
            list.remove(idx);
        }
    }
}

784. 字母大小写全排列

剑指 Offer II 084. 含有重复元素集合的全排列 

package DFS;

import org.junit.Test;

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

/**
 * @Classname 全排列47
 * @Description TODO
 * @Date 2023/3/6 21:15
 * @Created by xjl
 */
public class 全排列47 {

    @Test
    public void test(){
        List lists = listuteUnique(new int[]{1, 2, 2, 3});
        for (List list:lists){
            for (int i:list){
                System.out.println(i);
            }
        }
    }

    public List listuteUnique(int[] nums) {
        List lists = new ArrayList();
        List list = new ArrayList();
        boolean [] visit = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums, lists, 0, list,visit);
        return lists;
    }
    public void dfs(int[] nums, List lists, int idx, List list,boolean[] visit) {
        if (idx == nums.length) {
            lists.add(new ArrayList(list));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (visit[i] || (i > 0 && nums[i] == nums[i - 1] && !visit[i - 1])) {
                continue;
            }
            list.add(nums[i]);
            visit[i] = true;
            dfs(nums, lists, idx + 1, list,visit);
            // 回溯算法
            visit[i] = false;
            list.remove(idx);
        }
    }
}

剑指 Offer II 083. 没有重复元素集合的全排列

package DFS;

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

/**
 * @Classname 全排列46
 * @Description TODO
 * @Date 2023/3/6 21:01
 * @Created by xjl
 */
public class 全排列46 {

    public List permute(int[] nums) {
        List lists=new ArrayList();
        if (nums.length==0){
            return lists;
        }
        List list=new ArrayList();
        boolean[] visit=new boolean[nums.length];
        dfs(nums,0,visit,list,lists);
        return lists;
    }

    private void dfs(int[] nums, int index, boolean[] visit, List list, List lists) {
        if (index==nums.length){
            lists.add(new ArrayList(list));
            return;
        }
        for (int i=0;i