回溯算法DFS && BFS算法
echo发表于 2023-07-27 15:55:25
回溯算法框架
解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：
- 路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
List<List<Integer>> res = new ArrayList<>();
public void dfs(路径，选择列表) {
if满足条件：
res.add(路径)
return;
for (选择 in 选择路径) {
做选择
dfs(路径，选择列表)
撤销选择
}
}
其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单。
我们只要在递归之前做出选择，在递归之后撤销刚才的选择，就能正确得到每个节点的选择列表和路径。
全排列
List<List<Integer>> res = new LinkedList<>();
/* 主函数，输入一组不重复的数字，返回它们的全排列 */
List<List<Integer>> permute(int[] nums) {
// 记录「路径」
LinkedList<Integer> track = new LinkedList<>();
backtrack(nums, track);
return res;
}
// 路径：记录在 track 中
// 选择列表：nums 中不存在于 track 的那些元素
// 结束条件：nums 中的元素全都在 track 中出现
void backtrack(int[] nums, LinkedList<Integer> track) {
// 触发结束条件
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i++) {
// 排除不合法的选择
if (track.contains(nums[i]))
continue;
// 做选择
track.add(nums[i]);
// 进入下一层决策树
backtrack(nums, track);
// 取消选择
track.removeLast();
}
}
通过全排列问题详解了回溯算法的底层原理。当然，这个算法解决全排列不是很高效，因为对链表使用contains方法需要 O(N) 的时间复杂度。有更好的方法通过交换元素达到目的，
全排列去重
public static void permutation(char[] chars , int index , List<String> res) {
if (index == chars.length - 1) {
String string = new String(chars);
res.add(string);
}else {
for (int i = index; i < chars.length; i++) {
//去重
if (isSwap(chars, index, i)) {
swap(chars, index, i);
permutation(chars, index+1, res);
//回溯,恢复到初始状态
swap(chars, index, i);
}
}
}
}
public static boolean isSwap(char[] chars, int begin, int end) {
for (int i = begin; i < end; i++) {
if (chars[i] == chars[end]) {
return false;
}
}
return true;
}
public static void swap(char[] chars, int i, int j) {
char temp = chars[j];
chars[j] = chars[i];
chars[i] = temp;
}
37. 解数独
public static void solveSudoku(char[][] board) {
//用于记录行上的某个数是否存在
boolean[][] row = new boolean[9][9];
//用于记录列上的某个数是否存在
boolean[][] col = new boolean[9][9];
//用于记录九宫格上的某个数是否存在
boolean[][] block = new boolean[9][9];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
int num = board[i][j] - '1';
row[i][num] = true;
col[j][num] = true;
//第几个九宫格 // blockIndex = i / 3 * 3 + j / 3，取整
int blockindex = i/3*3 + j/3;
block[blockindex][num] = true;
}
}
}
dfs(board,row, col, block, 0, 0);
}
//路径：已经填过的位置
//选择列表：三个boolean[][]
//结束条件：遍历一遍
public static boolean dfs(char[][] board,boolean[][] row, boolean[][] col, boolean[][] block, int i,int j) {
//判断，是否是空格 && i，j，是否越界
while (board[i][j] != '.') {
if (++j >= 9) {
//要换到下一行
i++;
j = 0;
}
//结束
if (i >= 9) {
return true;
}
}
for (int num = 0; num < 9; num++) {
//判断该数字是否已经存在
if (!row[i][num] && !col[j][num] && !block[i/3*3+j/3][num]) {
board[i][j] = (char) (num + '1');
row[i][num] = true;
col[j][num] = true;
block[i/3*3+j/3][num] = true;
if (dfs(board, row, col, block, i, j)) {
return true;
}
//回溯
board[i][j] = '.';
row[i][num] = false;
col[j][num] = false;
block[i/3*3+j/3][num] = false;
}
}
return false;
}
51. N 皇后
static List<List<String>> res = new LinkedList<>();
/**
* 在同一行上，同一列上，同一条斜线上不能有两个
*/
public static List<List<String>> solveNQueens(int n) {
//初始化一个棋盘
char[][] chars = new char[n][n];
for (int i = 0; i < chars.length; i++) {
for (int j = 0; j < chars.length; j++) {
chars[i][j] = '.';
}
}
dfs(chars, 0);
return res;
}
//路径：填过的棋盘
//选择列表：剩余的空位置棋盘
//结束条件：遍历一遍棋盘
public static void dfs(char[][] chars, int row) {
if (row == chars.length) {
List<String> list = print(chars);
res.add(new ArrayList<>(list));
return;
}
int len = chars.length;
for (int i = 0; i < len; i++) {
//检查是否重复
if (isValid(chars, row, i)) {
chars[row][i] = 'Q';
dfs(chars, row+1);
chars[row][i] = '.';
}
}
}
/**
* 注意：这里只判断了上部分的。
* @param chars
* @param row
* @param col
* @return
*/
public static boolean isValid(char[][] chars, int row, int col) {
//检查这一列上是否重复
int len = chars.length;
for (int j = 0; j < len; j++) {
if (chars[j][col] == 'Q') {
return false;
}
}
//判断左上方
for (int i = row-1,j = col-1; i>=0&&j>=0;i--,j--) {
if (chars[i][j] == 'Q') {
return false;
}
}
//判断右上方
for (int i = row-1,j=col+1; i>=0&&j<len;i--,j++) {
if (chars[i][j] == 'Q') {
return false;
}
}
return true;
}
public static List<String> print(char[][] chars) {
List<String> list = new ArrayList<>();
for (int i = 0; i < chars.length; i++) {
list.add(new String(chars[i]));
}
return list;
}
78. 子集
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
LinkedList<Integer> list = new LinkedList<>();
dfs(0, nums, list);
return res;
}
//路径：
public void dfs(int index, int[] nums, LinkedList<Integer> list) {
res.add(new ArrayList<>(list));
for (int i = index; i < nums.length; i++) {
list.addLast(nums[i]);
dfs(i+1, nums, list);
list.removeLast();
}
}
77. 组合
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
int[] nums = new int[n];
for (int i = 0; i < nums.length; i++) {
nums[i] = i+1;
}
List<Integer> list = new ArrayList<>();
dfs(nums, k,0, list);
return res;
}
public void dfs(int[] nums,int k,int start, List<Integer> list) {
if (list.size() == k) {
res.add(new ArrayList<>(list));
return;
}
for (int i = start; i < nums.length; i++) {
list.add(nums[i]);
dfs(nums, k, start+1, list);
list.remove(list.size()-1);
}
}
子集问题可以利用数学归纳思想，假设已知一个规模较小的问题的结果，思考如何推导出原问题的结果。也可以用回溯算法，要用 start参数排除已选择的数字。
组合问题利用的是回溯思想，结果可以表示成树结构，我们只要套用回溯算法模板即可，关键点在于要用一个 start 排除已经选择过的数字。
排列问题是回溯思想，也可以表示成树结构套用算法模板，不同之处在于使用 contains 方法排除已经选择的数字，
22. 括号生成
我的代码：先全排列，然后用栈判断是否是合法的括号。麻烦
class Solution {
List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
char[] chars = new char[n*2];
for (int i = 0; i < chars.length; i++) {
if (i % 2 == 0) {
chars[i] = '(';
}else {
chars[i] = ')';
}
}
//List<Character> list = new ArrayList<>();
dfs(chars, 0);
return res;
}
public void dfs(char[] chars,int index) {
if (chars.length == index) {
Stack<Character> stack = new Stack<>();
String str = "";
for (Character c : chars) {
str += c+"";
if (c == '(') {
stack.push(c);
}else {
if (stack.empty()) {
return;
}else {
stack.pop();
}
}
}
res.add(str);
return;
}
for (int i = index; i < chars.length; i++) {
if (isSwap(chars, index, i)) {
swap(chars, index, i);
dfs(chars, index+1);
swap(chars, index, i);
}
}
}
public boolean isSwap(char[] chars, int start,int end) {
for (int i = start; i <end; i++) {
if (chars[end] == chars[i]) {
return false;
}
}
return true;
}
public void swap(char[] chars, int i, int j) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
}
第二种解法：
List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
Stack<Character> stack = new Stack<>();
dfs(n, n, stack);
return res;
}
public void dfs(int left, int right, Stack<Character> stack) {
if (right < left) {
return;
}
if (left < 0 || right <0) {
return;
}
if (left == 0 && right == 0) {
String str = "";
for (Character character : stack) {
str+=character;
}
res.add(str);
return;
}
stack.push('(');
dfs(left-1, right, stack);
stack.pop();
stack.push(')');
dfs(left, right-1, stack);
stack.pop();
}
130. 被围绕的区域
先把边界与边界相连的区域，O换成-，然后遍历二维数组，把O->X ,- 换回O；
class Solution {
public void solve(char[][] board) {
//上边界
for (int i = 0; i < board[0].length; i++) {
dfs(board, 0, i);
}
//下边界
for (int i = 0; i < board[0].length; i++) {
dfs(board, board.length-1, i);
}
//左边界
for (int i = 0; i < board.length; i++) {
dfs(board, i, 0);
}
//右边界
for (int i = 0; i < board.length; i++) {
dfs(board, i, board[i].length-1);
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
if (board[i][j] == '-') {
board[i][j] = 'O';
}
}
}
}
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')
{
board[i][j]='-';
dfs(board,i+1,j);
dfs(board,i-1,j);
dfs(board,i,j+1);
dfs(board,i,j-1);
}
}
}
剑指 Offer 12. 矩阵中的路径
- dfs + 回溯；
- 使用二维布尔数组记录之前的位置是否已经被访问过，如果已经被访问过的话，则在 dfs 的过程中，直接 return false 即可。也就是说，此路已经不通了；
- 如果当前遍历到的字符不等于 boardi 位置上的字符，那么说明此路也是不通的，因此返回 false；
- 至于递归结束的条件：如果指针 start 能够来到 word 的最后一个字符，那么说明能够在矩阵 board 中找到一条路径，此时返回 true；
- 在遍历到当前 boardi 的时候，首先应将该位置的 visitedi 设置为 true，表明访问过；
- 然后，递归地去 boardi 的上下左右四个方向去找，剩下的路径；
- 在 dfs 的过程当中，如果某条路已经不通了，那么那么需要回溯，也就是将 visitedi 位置的布尔值重新赋值为 fasle；
- 最后，返回 ans 即可。
class Solution {
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || board[0].length == 0) {
return false;
}
char[] chars = word.toCharArray();
boolean[][] visited = new boolean[board.length][board[0].length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
// 从 (0, 0) 点开始进行 dfs 操作，不断地去找，
// 如果以 (0, 0) 点没有对应的路径的话，那么就从 (0, 1) 点开始去找
if (dfs(board, chars, visited, i, j, 0)) {
return true;
}
}
}
return false;
}
private boolean dfs(char[][] board, char[] chars, boolean[][] visited, int i, int j, int start) {
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length
|| chars[start] != board[i][j] || visited[i][j]) {
return false;
}
if (start == chars.length - 1) {
return true;
}
visited[i][j] = true;
boolean ans = false;
ans = dfs(board, chars, visited, i + 1, j, start + 1)
|| dfs(board, chars, visited, i - 1, j, start + 1)
|| dfs(board, chars, visited, i, j + 1, start + 1)
|| dfs(board, chars, visited, i, j - 1, start + 1);
visited[i][j] = false;
return ans;
}
}
BFS算法框架
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
Queue<Node> q; // 核心数据结构
Set<Node> visited; // 避免走回头路
q.offer(start); // 将起点加入队列
visited.add(start);
int step = 0; // 记录扩散的步数
while (q not empty) {
int sz = q.size();
/* 将当前队列中的所有节点向四周扩散 */
for (int i = 0; i < sz; i++) {
Node cur = q.poll();
/* 划重点：这里判断是否到达终点 */
if (cur is target)
return step;
/* 将 cur 的相邻节点加入队列 */
for (Node x : cur.adj())
if (x not in visited) {
q.offer(x);
visited.add(x);
}
}
/* 划重点：更新步数在这里 */
step++;
}
}
111. 二叉树的最小深度
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
//Set<TreeNode> set = new HashSet<>();
queue.offer(root);
//set.add(root);
int step = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left == null && node.right == null) {
return step;
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
step++;
}
return step;
}
752. 打开转盘锁
deadends：中的数字是不可以进行转动的。
class Solution {
public int openLock(String[] deadends, String target) {
Set<String> deSet = new HashSet<>();
for (String string : deadends) {
deSet.add(string);
}
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
//记录，排除重复的值
visited.add("0000");
queue.offer("0000");
int step = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String pollString = queue.poll();
//被锁的，不可以在这个基础上转动
if (deSet.contains(pollString)) {
continue;
}
//出口
if (pollString.equals(target)) {
return step;
}
for (int j = 0; j < 4; j++) {
String s1 = plusOne(pollString, j);
if (!visited.contains(s1)) {
queue.offer(s1);
visited.add(s1);
}
String s2 = minusOne(pollString, j);
if (!visited.contains(s2)) {
queue.offer(s2);
visited.add(s2);
}
}
}
step++;
}
return -1;
}
public String plusOne(String cur, int pos) {
char[] c = cur.toCharArray();
if (c[pos] == '9') {
c[pos] = '0';
}else {
c[pos] +=1;
}
return new String(c);
}
public String minusOne(String cur, int pos) {
char[] c = cur.toCharArray();
if (c[pos] == '0') {
c[pos] = '9';
}else {
c[pos] -=1;
}
return new String(c);
}
}
双向BFS解法：
对q1进行扩散，扩散的结果保存到temp，然后q1 = q2,q2= temp,下一轮就相当于对q2进行扩散，双向。就是轮换着进行扩散。
public int openLock(String[] deadends, String target) {
Set<String> q1 = new HashSet<>();
Set<String> q2 = new HashSet<>();
Set<String> valid = new HashSet<>();
for (String string : deadends) {
valid.add(string);
}
if (valid.contains("0000")) {
return -1;
}
// 初始化
q1.add("0000");
q2.add(target);
int step = 0;
while (!q1.isEmpty() && !q2.isEmpty()) {
// 记录扩散结果
Set<String> temp = new HashSet<>();
//对q1进行扩散，扩散的结果保存到temp，然后q1 = q2,q2= temp,下一轮就相当于对q2进行扩散，双向。
for (String str : q1) {
if (q2.contains(str)) {
return step;
}
valid.add(str);
for (int i = 0; i < 4; i++) {
String butString = setRotateBut(str, i);
if (!valid.contains(butString)) {
temp.add(butString);
}
String topString = setRotateTop(str, i);
if (!valid.contains(topString)) {
temp.add(topString);
}
}
}
step ++;
q1 = q2;
q2 = temp;
}
return -1;
}
//0-1-9-0旋转
public static String setRotateTop(String str, int j) {
char[] chars= str.toCharArray();
if (chars[j] == '9') {
chars[j] = '0';
}else {
chars[j] = (char)(chars[j] +1);
}
return new String(chars);
}
//0-9-8-0
public static String setRotateBut(String str, int j) {
char[] chars= str.toCharArray();
if (chars[j] == '0') {
chars[j] = '9';
}else {
chars[j] = (char)(chars[j] -1);
}
return new String(chars);
}
773. 滑动谜题
我的代码，双向BFS，用字符串进行操作。时间复杂度高。
public static int slidingPuzzle(int[][] board) {
Set<String> q1 = new HashSet<>();
Set<String> q2 = new HashSet<>();
Set<String> valid = new HashSet<>();
q1.add(serializationRe(board));
q2.add("123450");
int step = 0;
while (!q1.isEmpty() && !q2.isEmpty()) {
Set<String> temp = new HashSet<>();
for (String str : q1) {
if (q2.contains(str)) {
return step;
}
valid.add(str);
String[] arrStrings = serialization(str);
for (int i = 0; i < arrStrings.length; i++) {
if (arrStrings[i] != null && !valid.contains(arrStrings[i])) {
temp.add(arrStrings[i]);
}
}
}
step++;
q1 = q2;
q2 = temp;
}
return -1;
}
public static String[] serialization(String str){
int[][] arr = new int[2][3];
int n = 0;
int m = 0;
for (int i = 0; i < str.length(); i++) {
if (i<3) {
if (str.charAt(i) == '0') {
m = i;
}
arr[0][i] = str.charAt(i) - '0';
}else {
if (str.charAt(i) == '0') {
n = 1;
m = i-3;
}
arr[1][i-3] = str.charAt(i) - '0';
}
}
String[] strings = new String[3];
int index = 0;
if (m-1>=0) {
swap(arr[n], m-1, m);
strings[index++] = serializationRe(arr);
swap(arr[n], m-1, m);
}
if (m+1<3) {
swap(arr[n], m+1, m);
strings[index++] = serializationRe(arr);
swap(arr[n], m+1, m);
}
if (n == 0) {
int temp = arr[n][m];
arr[n][m] = arr[n+1][m];
arr[n+1][m] = temp;
strings[index] = serializationRe(arr);
}else {
int temp = arr[n][m];
arr[n][m] = arr[n-1][m];
arr[n-1][m] = temp;
strings[index] = serializationRe(arr);
}
return strings;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static String serializationRe(int[][] board){
String string = "";
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
string+=board[i][j];
}
}
return string;
}
优化：也是转为字符串处理，但是记录一下每个位置为0时可以做交换的位置，省去了去找位置的步骤，用字符串可以交换，避免多次转换。
class Solution {
public:
int slidingPuzzle(vector<vector<int>>& board) {
int m = 2, n = 3;
string start = "";
string target = "123450";
// 将 2x3 的数组转化成字符串
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
start.push_back(board[i][j] + '0');
}
}
// 记录一维字符串的相邻索引
vector<vector<int>> neighbor = {
{ 1, 3 },
{ 0, 4, 2 },
{ 1, 5 },
{ 0, 4 },
{ 3, 1, 5 },
{ 4, 2 }
};
/******* BFS 算法框架开始 *******/
queue<string> q;
unordered_set<string> visited;
q.push(start);
visited.insert(start);
int step = 0;
while (!q.empty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
string cur = q.front(); q.pop();
// 判断是否达到目标局面
if (target == cur) {
return step;
}
// 找到数字 0 的索引
int idx = 0;
for (; cur[idx] != '0'; idx++);
// 将数字 0 和相邻的数字交换位置
for (int adj : neighbor[idx]) {
string new_board = cur;
swap(new_board[adj], new_board[idx]);
// 防止走回头路
if (!visited.count(new_board)) {
q.push(new_board);
visited.insert(new_board);
}
}
}
step++;
}
return -1;
/******* BFS 算法框架结束 *******/
}
};
蓝桥杯国赛javaB组---B扩散
答案：20312088
public static void test() {
boolean[][] bss = new boolean[10000][10000];
bss[3000][3000] = true;
bss[5020][3011] = true;
bss[3011][3014] = true;
bss[5000][5000] = true;
Queue<String> queue = new LinkedList<>();
queue.add("3000,3000");
queue.add("5020,3011");
queue.add("3011,3014");
queue.add("5000,5000");
for (int i = 0; i < 2020; i++) {
int size = queue.size();
for (int j = 0; j < size; j++) {
String str = queue.poll();
String[] arr = str.split(",");
int x = Integer.parseInt(arr[0]);
int y = Integer.parseInt(arr[1]);
if (!bss[x-1][y]) {
bss[x-1][y] = true;
queue.add((x-1)+","+y);
}
if (!bss[x+1][y]) {
bss[x+1][y] = true;
queue.add((x+1)+","+y);
}
if (!bss[x][y-1]) {
bss[x][y-1] = true;
queue.add(x+","+(y-1));
}
if (!bss[x][y+1]) {
bss[x][y+1] = true;
queue.add(x+","+(y+1));
}
}
}
long count = 0;
for (int i = 0; i < bss.length; i++) {
for (int j = 0; j < bss[i].length; j++) {
if (bss[i][j]) {
count++;
}
}
}
System.out.println(count);
}
蓝桥杯国赛javaB组---E玩具蛇
public static void test() {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
bbs[i][j] = true;
dfs(i, j, 1);
bbs[i][j] = false;
}
}
System.out.println(s);
}
static int s = 0;
static boolean[][] bbs = new boolean[4][4];
public static void dfs(int i, int j,int count) {
System.out.println(count);
if (count==16) {
s++;
return;
}
if (i+1<4 && !bbs[i+1][j]) {
bbs[i+1][j] = true;
dfs(i+1, j,count+1);
bbs[i+1][j] = false;
}
if (j+1<4&& !bbs[i][j+1]) {
bbs[i][j+1] = true;
dfs(i, j+1,count+1);
bbs[i][j+1] = false;
}
if (i-1>=0&& !bbs[i-1][j]) {
bbs[i-1][j] = true;
dfs(i-1, j,count+1);
bbs[i-1][j] = false;
}
if (j-1>=0&& !bbs[i][j-1]) {
bbs[i][j-1] = true;
dfs(i, j-1,count+1);
bbs[i][j-1] = false;
}
}彩蛋
来源：知乎 www.zhihu.com
作者：echo
【知乎日报】千万用户的选择，做朋友圈里的新鲜事分享大牛。 点击下载