一:DFS基础

(1)概述

DFS(深度优先搜索):一种用于遍历或搜索树或图的算法。它从起始节点开始,沿着一个路径一直向下探索,直到到达末端节点,然后再回溯并继续探索其他路径。DFS倾向于探索尽可能深的节点,直到达到末端,然后再回溯。DFS通常使用递归来实现,但也可以使用栈来模拟递归的过程

在这里插入图片描述

(2)模板

public static void dfs() {
	if(当前状态 == 目标状态)
		// 逻辑处理
		return;
	for(寻找新状态) {
		if(状态合法) {
			dfs(新状态)
		}
	}
}

(3)典型题目

题目一:牛客:红与黑

在这里插入图片描述

在这里插入图片描述

import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
	
	static int ans = 0;
	
	public static void dfs(char[][] arr, int i, int j, int m, int n) {
		ans++;
		arr[i][j] = '#';
		
		// 两个方向的移动量
		int[] dx = {1, -1, 0, 0};
		int[] dy = {0, 0, 1, -1};
		for(int k = 0;k < 4; k++) {
			int move_x = i + dx[k];
			int move_y = j + dy[k];
			if (move_x < 0 || move_x >=m || move_y < 0 || move_y >= n || arr[move_x][move_y] != '.')
				continue;
			dfs(arr, move_x, move_y, m, n);
		}
		
		
		
		
	}
	
	
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        int n = scan.nextInt();
        int start_i = 0;
        int start_j = 0;
        char[][] arr = new char[m][n];
        
        for(int i = 0; i < m; i++) {
        	String str = scan.next();
        	char[] str_arr = str.toCharArray();
        	for (int j = 0; j < n; j++) {
        		arr[i][j] = str_arr[j];
        		if (arr[i][j] == '@') {
        			start_i = i;
        			start_j = j;
        		}
        	}
        
    	}
        
     
        dfs(arr, start_i, start_j, m, n);
        System.out.println(ans);
        

    }
}

二:回溯算法

(1)概述

回溯算法:回溯算法是一种解决问题的算法范式,通常用于解决在搜索问题的解空间时需要考虑多种可能性的情况。这种算法的核心思想是逐步构建解决方案,并在发现当前解决方案不可行时回溯到之前的状态,并尝试其他可能的路径

对于全排列这种问题,用回溯算法解决时,就会生成一颗决策树。遍历整个决策树时,你只需要思考三个问题:

  • 路径:你已经做出的选择(当前选择的数字)
  • 选择列表:也就是你当前可以做的选择(还能选哪几个数字)
  • 结束条件:到达决策树底层,无法再做选择的条件

在这里插入图片描述

(2)模板

下面是模板框架

  • result:通常设为一个全局变量,用于返回结果
  • 选择:做出的一定是合理的选择(根据题意)
  • 撤销选择:也就是恢复状态
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

(3)典型题目

题目一:力扣46:全排列

在这里插入图片描述

res返回全部排列,record记录一个排列

class Solution {
    // 返回结果
    List<List<Integer>> res = new ArrayList<>();

    // 回溯
    public void back(int[] nums, List<Integer> record) {
        // 如果数选择完毕了,那么就增加一个排列
        if (record.size() == nums.length) {
            res.add(new ArrayList<>(record));
            return;
        }


        for(int i = 0; i < nums.length; i++) {
            // 寻找nums[i]在record中是否存在
            // 如果存在直接下一个
            if(record.contains(nums[i])){
                continue;
            }
            // 做出选择
            record.add(nums[i]);
            back(nums,record);
            // 撤销选择
            record.remove(record.size()-1);

        }
    }

    public List<List<Integer>> permute(int[] nums) {
        // 用于记录已经选择数
        List<Integer> record = new ArrayList<>();
        back(nums, record);

        return res;
    }
}

题目二:蓝桥云客3824:开心

在这里插入图片描述

在这里插入图片描述

首先,在 back 方法中,通过递归遍历 arr 数组,依次将每个字符添加到 StringBuilder 对象 str 中。当 str 的长度达到 arr 的长度时,表示已经选择完了所有的字符。此时,如果 k 的值为 0,说明已经选择了 k 个数,可以计算它们的和。这时,我们将 str 转换为字符串,并使用 split("\\+") 方法将其分割成多个子字符串,每个子字符串代表一个数。然后,将每个子字符串转换为长整型并求和,得到结果 res。然后,我们使用 Math.maxMath.min 方法更新全局变量 maxmin,分别记录最大值和最小值。

package environment;

import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
	
	static long max = Long.MIN_VALUE;
	static long min = Long.MAX_VALUE;
	
	
	public static void back(int current, char[] arr, int k, StringBuilder str) {
		if (current == arr.length) {
			if (k == 0) {
				String[] s = str.toString().split("\\+");
				long res = 0;
				for(String x : s) {
					res += Long.valueOf(x);
				}
				
				max = Math.max(max, res);
				min = Math.min(min, res);
			}
			
			return;
		}
		
		str.append(arr[current]);
		back(current+1, arr, k, str);
		str.deleteCharAt(str.length()-1);
		
		if (k > 0 && current < arr.length-1) {
			str.append(arr[current]);
			str.append('+');
			back(current+1, arr, k-1, str);
			str.deleteCharAt(str.length()-1);
			str.deleteCharAt(str.length()-1);
			
		}
		
	}
	
	public static void main(String[] args) throws IOException {
		Scanner scan = new Scanner(System.in);
		char[] arr = scan.next().toCharArray();
		int k = scan.nextInt();
		StringBuilder str = new StringBuilder();
		
		back(0, arr, k, str);
		
		System.out.println(max-min);
	
    }
}

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部