回溯算法

2023-12-10数据结构与算法6 分钟121 次阅读
AI 摘要salmon-ai

本文详细解析了回溯算法的核心思想与适用场景:它本质上是带有状态重置的深度优先搜索,

简介

回溯算法是对树形或者图形结构执行一次深度优先遍历,实际上类似枚举的搜索尝试过程,在遍历的过程中寻找问题的解。

深度优先遍历有个特点:当发现已不满足求解条件时,就返回,尝试别的路径。此时对象类型变量就需要重置成为和之前一样,称为「状态重置」。

许多复杂的,规模较大的问题都可以使用回溯法,有「通用解题方法」的美称。实际上,回溯算法就是暴力搜索算法,它是早期的人工智能里使用的算法,借助计算机强大的计算能力帮助我们找到问题的解。

力扣相关算法题:https://leetcode.cn/tag/backtracking/problemset/

例题

电话号码的字母组合

题目:17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
px-telephone-keypad2svg.png

示例 1:

输入: digits = "23"
输出: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2:

输入: digits = ""
输出: []

示例 3:

输入: digits = "2"
输出: ["a","b","c"]

提示:

  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。

解法:回溯算法用于寻找所有的可行解,如果发现一个解不可行,则会舍弃不可行的解。在这道题中,由于每个数字对应的每个字母都可能进入字母组合,因此不存在不可行的解,直接穷举所有的解即可。

该字符串初始为空。每次取电话号码的一位数字,从哈希表中获得该数字对应的所有可能的字母,并将其中的一个字母插入到已有的字母排列后面,然后继续处理电话号码的后一位数字,直到处理完电话号码中的所有数字,即得到一个完整的字母排列。然后进行回退操作,遍历其余的字母排列。

java 复制代码
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 17. 电话号码的字母组合
 * https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
 *
 * @author Salmon
 * @since 2023-12-10
 */
public class M_17 {
    public static void main(String[] args) {
        List<String> strings = letterCombinations("23");
        for (String string : strings) {
            System.out.printf("%s ", string);
        }
    }

    static Map<Character, String> keyMap = new HashMap<Character, String>() {{
        put('1', " ");
        put('2', "abc");
        put('3', "def");
        put('4', "ghi");
        put('5', "jkl");
        put('6', "mno");
        put('7', "pqrs");
        put('8', "tuv");
        put('9', "wxyz");
    }};

    public static List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits.length() == 0) {
            return res;
        }
        backtrack(res, digits, 0, new StringBuffer());
        return res;
    }

    /**
     * 回溯法
     *
     * @param res    结果集
     * @param digits 待处理字符串
     * @param index  当前下标
     * @param sb     用户缓存当前已经匹配组合的字符串
     */
    private static void backtrack(List<String> res, String digits, int index, StringBuffer sb) {
        if (index == digits.length()) {
            res.add(sb.toString());
            return;
        }
        // 当前号码
        char digit = digits.charAt(index);
        // 获取当前号码对应的字母
        String letters = keyMap.get(digit);
        int lettersCount = letters.length();
        // 遍历当前每个字母
        for (int i = 0; i < lettersCount; i++) {
            // 先将当前字母拼接上去,然后使用回溯法进行匹配,直到 index 到 输入的最后一个数字的下标位置
            sb.append(letters.charAt(i));
            backtrack(res, digits, index + 1, sb);
            // 匹配完成后,则把 sb 缓存清空,接着匹配下一个字母开头的字符串
            sb.deleteCharAt(index);
        }
    }
}
image.png

括号生成

题目:22. 括号生成

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

示例 1:

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

示例 2:

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

提示:

  • 1 <= n <= 8

解法

java 复制代码
import java.util.ArrayList;
import java.util.List;

/**
 * 22. 括号生成
 * https://leetcode.cn/problems/generate-parentheses/
 *
 * @author Salmon
 * @since 2023-12-10
 */
public class M_22 {
    public static void main(String[] args) {
        List<String> strings = generateParenthesis(3);
        for (String string : strings) {
            System.out.println(string);
        }
    }

    public static List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if (n == 0) {
            return res;
        }
        dfs(new StringBuffer(), n, n, res);
        return res;
    }

    /**
     * 深度优先遍历
     *
     * @param curStr 当前递归得到的结果
     * @param left   左括号还有几个可以使用
     * @param right  右括号还有几个可以使用
     * @param res    结果集
     */
    private static void dfs(StringBuffer curStr, int left, int right, List<String> res) {
        if (left == 0 && right == 0) {
            res.add(curStr.toString());
            return;
        }
        // 如果左右可使用的括号数量不匹配,剪枝(左括号可以使用的个数严格大于右括号可以使用的个数,才剪枝,注意这个细节)
        if (left > right) {
            return;
        }
        if (left > 0) {
            curStr.append("(");
            int length = curStr.length();
            dfs(curStr, left - 1, right, res);
            // 回溯,回到还没 添加 ( 之前
            curStr.setLength(length - 1);
        }
        if (right > 0) {
            curStr.append(")");
            int length = curStr.length();
            dfs(curStr, left, right - 1, res);
            // 回溯,回到还没 添加 ) 之前
            curStr.setLength(length - 1);
        }
    }
}
image.png

单词搜索

题目:79. 单词搜索

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

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

示例 1:
1.img

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

示例 2:
2.img

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

示例 3:
3.img

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

提示:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board 和 word 仅由大小写英文字母组成

解法

java 复制代码
/**
 * 79. 单词搜索
 * https://leetcode.cn/problems/word-search/
 *
 * @author Salmon
 * @since 2023-12-10
 */
public class M_79 {
    public static void main(String[] args) {
        char[][] board = {new char[]{'A', 'B', 'C', 'E'}, new char[]{'S', 'F', 'C', 'S'}, new char[]{'A', 'D', 'E', 'E'}};
        String word = "ABCCED";
        System.out.println(exist(board, word));
    }

    public static boolean exist(char[][] board, String word) {
        // 获取网格的宽高
        int height = board.length, width = board[0].length;
        // 标记每个格子是否访问过
        boolean[][] visited = new boolean[height][width];
        // 从第一个格子逐一判断是否能构成单词
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                boolean flag = check(board, visited, i, j, word, 0);
                if (flag) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 校验
     *
     * @param board   网格数组
     * @param visited 已经拜访过的格子
     * @param i       当前待校验的格子在哪一行
     * @param j       当前待校验的格子在哪一列
     * @param s       单词
     * @param k       判断当前单词中的哪个字符
     * @return 是否匹配
     */
    private static boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
        // 如果当前格子与当前待匹配的字符不匹配
        if (board[i][j] != s.charAt(k)) {
            return false;
        }
        // 如果当前匹配到最后一个串,说明匹配结束
        if (k == s.length() - 1) {
            return true;
        }
        // 标记该网格已经访问过,防止接下来递归重新访问该网格
        visited[i][j] = true;

        // 定义一个方向数组,让每个格子分别往上下左右走走
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        boolean result = false;

        for (int[] dir : directions) {
            // 接下来要访问的格子
            int ni = i + dir[0], nj = j + dir[1];
            // 防止下标越界
            if (ni >= 0 && ni < board.length && nj >= 0 && nj < board[0].length) {
                // 判断该格子是否被访问过
                if (!visited[ni][nj]) {
                    boolean flag = check(board, visited, ni, nj, s, k + 1);
                    if (flag) {
                        result = true;
                        break;
                    }
                }
            }
        }
        // 回溯,重新标记网格未访问,让其它路经可进过
        visited[i][j] = false;
        return result;
    }
}

N皇后

题目:51. N皇后

按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1:
image.png

输入:n = 4
输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释:如上图所示,4 皇后问题存在两个不同的解法。

示例 2:

输入:n = 1
输出:[["Q"]]

提示:

  • 1 <= n <= 9

解法

java 复制代码
import java.util.*;

/**
 * 51.N皇后
 * https://leetcode.cn/problems/n-queens/description/
 *
 * @author Salmon
 * @since 2024-02-26
 */
public class D_51 {

    List<List<String>> res = new ArrayList<>();
    int n;
    boolean[][] board; // 棋盘(记录哪里放棋
    HashSet<Integer> col, pie, na;

    public static void main(String[] args) {
        D_51 d51 = new D_51();
        System.out.println(d51.solveNQueens(4));
    }

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        this.board = new boolean[n][n];
        this.col = new HashSet<>();
        this.pie = new HashSet<>();
        this.na = new HashSet<>();
        dfs(0);
        return res;
    }


    // 深度访问,由于n皇后问题是每一行,每一列,同一斜线上,都不能有皇后,故每一行只能有一个皇后
    // 而将皇后放在哪一列,与对是否在斜线的判断,则在每一层进入的时候进行判断
    public void dfs(int i) { // level 层,行
        if (i == n) {
            // 到最后一行,生成结果
            generate_result();
            return;
        }
        for (int j = 0; j < n; j++) {
            if (col.contains(j) || pie.contains(i + j) || na.contains(i - j)) {
                continue;
            }
            board[i][j] = true; // 标记当前访问过,当前位置放皇后
            col.add(j); // 当前列访问了,则下一次就不能再访问了
            pie.add(i + j); // 下一个是i+1,j+1,两者相加的值是个常量,而这条斜线上点的横纵坐标和都等于该值
            na.add(i - j);//  下一个是 i-1,j-1 两者的和或差也可以代表某个点是否在这条斜线上,由于上边取的和,这里就取差

            dfs(i + 1); // 进入下一层

            col.remove(j);
            pie.remove(i + j);
            na.remove(i - j);
            board[i][j] = false; // 走完了,重新标记未访问过

        }
    }

    /**
     * 生成结果
     */
    private void generate_result() {
        List<String> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                if (board[i][j]) {
                    sb.append("Q");
                } else {
                    sb.append(".");
                }
            }
            list.add(sb.toString());
        }
        res.add(list);
    }

}
image.png
觉得有用就点个赞,不用登录也能读

评论

0 条
登录 之后才能评论
—
还没有评论,来说第一句