Java实现回溯算法进阶（搜索）

从Java实现回溯算法入门（排列+组合+子集）练习了使用回溯算法的基础使用。

使用回溯算法实现搜索才是回溯算法+DFS的使用。

文章目录

- - 1.搜索问题

1.搜索问题

79.单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

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

示例一：
在这里插入图片描述

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例二：
在这里插入图片描述

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

示例三：
在这里插入图片描述

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

思路：

回溯算法+状态重置
使用布尔变量marked判断是否找到字符

代码实现：

class Solution {
    int rows, cols; // 定义行和列
    char[][] board;
    char[] word;
    boolean[][] marked; // 用来存储是否搜索到字母
    int[][] next = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; //用来搜索上下左右，顺序不重要

    public boolean exist(char[][] board, String word) {
        this.rows = board.length;
        this.cols = board[0].length;
        this.board = board;
        this.word = word.toCharArray();
        this.marked = new boolean[rows][cols];
        for(int row = 0; row < rows; row++){
            for(int col = 0; col < cols; col++){
                if(search(0, row, col)){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean search(int pos, int row, int col){ //pos为word的位置，row和col为行列
        // 先写明特殊情况
        if(row < 0 || row >= rows || col < 0 || col >= cols || marked[row][col]){
            return false;
        }
        if(board[row][col] != word[pos]){  //找不到这个字母
            return false;
        }
        if(pos == word.length-1){ //搜索到最后一位
            return true;
        }
        marked[row][col] = true;
        for(int[] ne : next){  // 上下左右搜索
            if(search(pos+1, row+ne[0], col+ne[1])){
                return true;
            }
        }
        marked[row][col] = false;
        return false;
    }
}

另一种写法：

class Solution {
    private boolean find = false;  // 返回最终结果
    public boolean exist(char[][] board, String word) {
        if (board == null) return false;
        int m = board.length, n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(i, j, board, word, visited, 0);
            }
        }
        return find;
    }
    private void dfs(int i, int j, char[][] board, String word, boolean[][] visited, int pos) {
        // visited表示当前格子是否被搜索过
        // pos记录目标单词的字符索引，只有棋盘字符和pos指向字符一致时，才继续搜索
        // 终止条件即为pos = word.length() - 1
        int m = board.length, n = board[0].length;
        // 超出边界，已访问过，已找到, 棋盘字符与目标字符不一致
        if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || find || board[i][j] != word.charAt(pos))
            return;
        // 终止条件
        if (pos == word.length() - 1) {
            find = true;
            return ;
        }
        visited[i][j] = true;  // 修改当前状态
        dfs(i + 1, j, board, word, visited, pos + 1);
        dfs(i - 1, j, board, word, visited, pos + 1);
        dfs(i, j + 1, board, word, visited, pos + 1);
        dfs(i, j - 1, board, word, visited, pos + 1);
        visited[i][j] = false; // 撤销修改
    }
}

212.单词搜索Ⅱ

这道题力扣设为困难，可以在Ⅰ的基础上进行解题，只是复杂度有点高。

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。

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

示例一：
在这里插入图片描述

输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
输出：["eat","oath"]

示例二：

在这里插入图片描述

输入：board = [["a","b"],["c","d"]], words = ["abcb"]
输出：[]

解题思想：

在第一题的基础上搜索单词，仍然是DFS回溯，需要加一层循环，遍历String数组中的每一个单词，这就导致了复杂度的变大。

这里使用了HashSet去重，然后需要将HashSet转化为list:

List<String> list = new ArrayList<String>(res);  // 将hashset转为list

代码实现：

class Solution {
    int rows, cols; // 定义行和列
    char[][] board;
    char[] word;
    boolean[][] marked; // 用来存储是否搜索到字母
    int[][] next = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; //用来搜索上下左右，顺序不重要
    
    public List<String> findWords(char[][] board, String[] words) {
        this.rows = board.length;
        this.cols = board[0].length;
        this.board = board;
        this.marked = new boolean[rows][cols];
        HashSet<String> res = new HashSet<String>();  //使用hashset去重
        for(int row = 0; row < rows; row++){
            for(int col = 0; col < cols; col++){
                for(int i = 0; i < words.length; i++){
                    this.word = words[i].toCharArray();
                    dfs(res, 0, row, col);
                }
            }
        }
        List<String> list = new ArrayList<String>(res);  // 将hashset转为list
        return list;
    }

    public void dfs(HashSet<String> res, int pos, int row, int col){
        if(row < 0 || row >= rows || col < 0 || col >= cols || marked[row][col]){
            return;
        }
        if(board[row][col] != word[pos]){
            return;
        }
        if(pos == word.length-1){
            String s = String.valueOf(word);  // char字符数组转String
            res.add(s);
            return;
        }
        marked[row][col] = true; // 判断字符是否搜索过
        for(int[] ne : next){  // 上下左右搜索,左去过就不能再右回来
            dfs(res, pos+1, row+ne[0], col+ne[1]);
        }
        marked[row][col] = false;
    }
}

按上一题的另一种写法则超时：

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        int m = board.length, n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        HashSet<String> res = new HashSet<String>();  //使用hashset去重
        char[] word;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < words.length; k++) {
                    word = words[k].toCharArray();
                    dfs(i, j, 0, board, word, visited, res);
                }
            }
        }
        List<String> list = new ArrayList<String>(res);  // 将hashset转为list
        return list;
    }
    private void dfs (int i, int j, int pos, char[][] board, char[] word, boolean[][] visited, HashSet<String> res) {
        int m = board.length, n = board[0].length;
        if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || board[i][j] != word[pos]) {
            return ;
        }
        if (pos == word.length - 1) {
            String s = String.valueOf(word);
            res.add(s);
            return ;
        }
        visited[i][j] = true;
        dfs(i + 1, j, pos + 1, board, word, visited, res);
        dfs(i - 1, j, pos + 1, board, word, visited, res);
        dfs(i, j + 1, pos + 1, board, word, visited, res);
        dfs(i, j - 1, pos + 1, board, word, visited, res);
        visited[i][j] = false;
    }
}

130.被围绕的区域

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

示例一：
在这里插入图片描述

输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

示例二：

输入：board = [["X"]]
输出：[["X"]]

思路：
首先对边界上每一个’O’做深度优先搜索，将与其相连的所有’O’改为’A’。然后遍历矩阵，将矩阵中所有’O’改为’X’,将矩阵中所有’A’变为’O’

代码实现：

class Solution {
    public void solve(char[][] board) {
        if(board == null || board.length==0) return;
        int row = board.length;
        int col = board[0].length;
        // 遍历四条边界，将与其相连的所有O改为A
        for(int i =0; i < row; i++){ //遍历第一列和最后一列
            dfs(board, i, 0);
            dfs(board, i, col-1);
        }
        for(int j =0; j < col; j++){ //遍历第一行和最后一行
            dfs(board, 0, j);
            dfs(board, row-1, j);
        }
        // 遍历整个board，将O改为X，将A改为O
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(board[i][j] == 'O') board[i][j] = 'X';
                if(board[i][j] == 'A') board[i][j] = 'O';
            }
        }
        return;
    }
    public void dfs(char[][] board, int i, int j){
        if(i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j]!='O') return;
        board[i][j] = 'A';
        dfs(board, i-1, j);
        dfs(board, i+1, j);
        dfs(board, i, j-1);
        dfs(board, i, j+1);
        return;
    }
}

200.岛屿的数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例一：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例二：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

解题思路：

遍历整个网格，如果位置为1，以其为起点深度优先搜索，搜索的过程中，每个搜索到的1都会标记成0，最后岛屿的数量就是深度优先搜索的次数。

代码实现：

class Solution {
    public int numIslands(char[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        int nums = 0;
        if(grid == null || row == 0) return 0;
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){  // 循环遍历整个网格，遇到’1‘，nums++;
                if(grid[i][j] == '1'){
                    nums++;
                    dfs(grid, i , j);  // 以该点为起点，深度优先搜索，遇到1就改为0
                }
            }
        }
        return nums;
    }
    public void dfs(char[][] grid, int i, int j){
        int row = grid.length;
        int col = grid[0].length;
        if(i < 0 || j < 0 || i >= row || j >= col || grid[i][j]=='0'){
            return;
        }
        grid[i][j] = '0';
        dfs(grid, i-1, j);
        dfs(grid, i+1, j);
        dfs(grid, i, j-1);
        dfs(grid, i, j+1);
    }
}

22.括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

有效括号组合需满足：左括号必须以正确的顺序闭合。

示例一：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例二：

输入：n = 1
输出：["()"]

思路：

DFS+剪枝
剪枝：先左括号后右括号

代码实现：

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        dfs(res, "", n, n);
        return res;
    }
    public void dfs(List<String> res, String ans, int i, int j){
        if(i == 0 && j == 0){  // 左右括号都不剩余了，递归终止
            res.add(ans);
            return;
        }
        if(i > 0){ // 如果左括号还剩余的话，可以拼接左括号
            dfs(res, ans+"(", i-1, j);
        }
        if(j > i){ // 如果右括号剩余多于左括号剩余的话，可以拼接右括号
            dfs(res, ans+")", i, j-1);
        }
    }
}

113. 路径总和Ⅱ

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。

叶子节点是指没有子节点的节点。

示例一：
在这里插入图片描述

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例二：
在这里插入图片描述

输入：root = [1,2,3], targetSum = 5
输出：[]

示例 3：

输入：root = [1,2], targetSum = 0
输出：[]

思路：

DFS+回溯，判断当为叶子节点且和为targetSum加入到LinkedList中，二叉树类的问题使用LinkedList存储，然后dfs左子树和右子树

枚举每一条从根节点到叶子节点的路径。当我们遍历到叶子节点，且此时路径和恰为目标和时，我们就找到了一条满足条件的路径

// 与二叉树相关的构建LinkedList
List<List<Integer>> res = new LinkedList<>();
Deque<Integer> path = new LinkedList<>();

代码实现：

class Solution {
    // 与二叉树相关的构建LinkedList
    List<List<Integer>> res = new LinkedList<>();
    Deque<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return res;
    }
    public void dfs(TreeNode root, int targetSum){
        if(root == null){
            return;
        }
        path.offerLast(root.val); //Java LinkedList offerLast()将指定的元素插入LinkedList的末尾
        targetSum -= root.val;
        if(root.left == null && root.right == null && targetSum == 0){
            // 叶子结点，且等于targetSum
            res.add(new LinkedList<>(path));
        }
        dfs(root.left, targetSum);
        dfs(root.right, targetSum);
        path.pollLast(); // 回溯
    }
}

剑指 Offer 13. 机器人的运动范围

在这里插入图片描述
思路：

常规深度优先搜索算法，超出边界或者不满足条件或者已经使用过，则直接return。

然后修改visited数组，上下左右回溯。

class Solution {
    public int movingCount(int m, int n, int k) {
        // 深度优先搜索
        boolean[][] visited = new boolean[m][n];
        int res = dfs(0, 0, m, n, k, visited);
        return res;
    }
    private int dfs(int i, int j, int m, int n, int k, boolean[][] visited) {
        if (i < 0 || i >= m || j < 0 || j >= n || (i / 10 + i % 10 + j / 10 + j % 10) > k || visited[i][j]) {
            return 0;
        }
        visited[i][j] = true;
        return dfs(i + 1, j, m, n, k, visited) + dfs(i - 1, j, m, n, k, visited) +
               dfs(i, j + 1, m, n, k, visited) + dfs(i, j - 1, m, n, k, visited) + 1;
    }
}