回溯

发表于 | 更新于: | 分类于 |

95题 不同的二叉搜索树 回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * @author 86153
 * @data 2021/7/23 12:42
 */
public class Question95 {
    public List<TreeNode> generateTrees(int n){
        return getAns(1,n);
    }

    public List<TreeNode> getAns(int start,int  end){
        ArrayList<TreeNode> ans = new ArrayList<>();
        // 该情况说明节点无左子树或者右子树
        if(start>end){
            ans.add(null);
            return ans;
        }
        if(start==end){
            TreeNode treeNode = new TreeNode(start);
            ans.add(treeNode);
            return ans;
        }

        //第一个for：所有的元素做根节点的情况（包括已经进入递归后，也可能根节点有多种情况)
        for(int i=start;i<=end;i++){
            // 递归得到所有的拼接情况
            List<TreeNode> leftTreeNodes = getAns(start,i-1);
            List<TreeNode> rightTreeNodes = getAns(i + 1, end);
            // 遍历得到所有的节点
            for (TreeNode leftTreeNode : leftTreeNodes) {
                for (TreeNode rightTreeNode : rightTreeNodes) {
                    TreeNode root = new TreeNode(i);
                    root.left=leftTreeNode;
                    root.right=rightTreeNode;
                    ans.add(root);
                }
            }
        }
        return ans;
    }
}

DFS+哈希表存父节点+回溯法+递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * @author 86153
 * @data 2021/7/28 19:44
 */
public class Question863 {
    public List<Integer> ans=new ArrayList<>();
    public HashMap<Integer,TreeNode> parents=new HashMap<>();
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        generateMap(root,null);
        recursion(target,null,0,k);
        return ans;
    }
    // 生成 key:二叉树节点值 -- value: 该节点值的父节点TreeNode

    public void generateMap(TreeNode root,TreeNode from){
        if(root==null){
            return;
        }
        parents.put(root.val,from);
        generateMap(root.left,root);
        generateMap(root.right,root);
    }
    // 回溯节点from
    public void recursion(TreeNode node,TreeNode from,int depth,int k){
        // 递归结束条件
        if(node==null){
            return ;
        }
        // 如果深度为K,则结果集添加该值
        if(depth==k){
            ans.add(node.val);
        }
        // 如果目前节点的左节点不是来自递归调用的节点，则往左节点递归
        if(node.left!=from){
            recursion(node.left,node,depth+1,k);
        }
        // 如果目前节点的右节点不是来自递归调用的节点，则往右节点递归
        if(node.right!=from){
            recursion(node.right,node,depth+1,k);
        }
        // 如果目前节点的父节点不是来自递归调用的节点，则向父节点递归
        if(parents.get(node.val)!=from){
            recursion(parents.get(node.val),node,depth+1,k);
        }
    }
}

Question79 单词搜索 dfs+状态重置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 用二维数组存储方向
    static final int[][] directions={{-1,0},{0,1},{1,0},{0,-1}};
    // 标记数组
    static boolean[][] visited;
    public static boolean exist(char[][] board, String word) {
        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++){
                // 只要返回值为false, 则状态重置 depth重置为0
                if(dfs(board,word,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }
    public static boolean dfs(char[][] board,String word,int i,int j,int depth){
        if(depth==word.length()-1){
            return board[i][j]==word.charAt(depth);
        }
        if(board[i][j]==word.charAt(depth)){
            visited[i][j]=true;
            for (int[] direction : directions) {
                int changeX=direction[0]+i;
                int changeY=direction[1]+j;
                if(condition(board,changeX,changeY) && !visited[changeX][changeY]){
                    if(dfs(board,word,changeX,changeY,depth+1)){
                        return true;
                    }
                }
            }
            //四个方向遍历完成之后 标记重置
            visited[i][j]=false;
        }
        return false;
    }
    public static boolean condition(char[][] board,int i,int j){
        return i>=0 && i<board.length && j>=0 && j<board[0].length;
    }

Qustion130 被围绕的区域 dfs

DFS广度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
static final int[][] directions={{-1,0},{0,1},{1,0},{0,-1}};
    public static void solve(char[][] board){
        int m=board[0].length;
        int n=board.length;
        //前两个for循环用来查找边界为O的元素  并以边界为O的点扩散查找与之间接或者直接相邻的元素
        for(int i=0;i<m;i++){
            dfs(board,0,i);
            dfs(board,n-1,i);
        }
        for(int j=1;j<n-1;j++){
            dfs(board,j,0);
            dfs(board,j,m-1);
        }

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i][j]=='A'){
                    board[i][j]='O';
                }else if(board[i][j]=='O'){
                    board[i][j]='X';
                }
            }
        }
    }

    public static void dfs(char[][] board,int i,int j){
        if(condition(board,i,j)){
            return;
        }
        board[i][j]='A';
        for (int[] direction : directions) {
            int changeX=direction[0]+i;
            int changeY=direction[1]+j;
            dfs(board,changeX,changeY);
        }
    }

    public static boolean condition(char[][] board,int i,int j){
        return i<0 || i>=board[0].length || j<0 || j>=board.length || board[i][j]!='O';
    }

BFS深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
static int[][] directions={{-1,0},{0,1},{1,0},{0,-1}};
    public void solve(char[][] board){
        int m=board.length;
        // 列数
        int n=board[0].length;
        Queue<int[]> queue=new LinkedList<>();

        // 前两个for循环遍历边界的O元素 将其坐标加入队列
        for(int i=0;i<m;i++){
            if(board[i][0]=='O'){
                board[i][0]='A';
                queue.offer(new int[]{i,0});
            }
            if(board[i][n-1]=='O'){
                board[i][n-1]='A';
                queue.offer(new int[]{i,n-1});
            }
        }


        for(int j=1;j<n-1;j++){
            if(board[0][j]=='O'){
                board[0][j]='A';
                queue.offer(new int[]{0,j});
            }
            if(board[m-1][j]=='O'){
                board[m-1][j]='A';
                queue.offer(new int[]{m-1,j});
            }
        }

        // 队列抛出元素 每抛出一个元素  先广度搜索其四周的元素是否为O  如果是  将O先加入队列当中
        // 此处注意区分广度和深度的区别
        while(!queue.isEmpty()){
            int[] point = queue.poll();
            int x=point[0];
            int y=point[1];
            for (int[] direction : directions) {
                int changeX=direction[0]+x;
                int changeY=direction[1]+y;
                if(condition(board,changeX,changeY)){
                    continue;
                }
                board[changeX][changeY]='A';
                queue.offer(new int[]{changeX,changeY});
            }
        }
        // 循环遍历  将A-》O  O->X
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i][j]=='A'){
                    board[i][j]='O';
                }else if(board[i][j]=='O'){
                    board[i][j]='X';
                }
            }
        }
    }
    public boolean condition(char[][] board,int x,int y){
        return x<0 || x>=board.length || y<0 || y>=board[0].length || board[x][y]!='O';
    }

Question695 岛屿的最大面积

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
static int[][] directions={{-1,0},{0,1},{1,0},{0,-1}};
public int maxAreaOfIsland(int[][] grid) {
    int maxNum=0;
    int num=0;  
    Queue<int[]> queue=new LinkedList<>();
    //行
    int m=grid.length;
    int n=grid[0].length;
    
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(grid[i][j]==1){
                queue.offer(new int[]{i,j});
                grid[i][j]=0;
                while(!queue.isEmpty()){
                    int[] poll = queue.poll();
                    num++;
                    int x=poll[0];
                    int y=poll[1];
                    for (int[] direction : directions) {
                        int changeX=direction[0]+x;
                        int changeY=direction[1]+y;
                        if(condition(grid,changeX,changeY)){
                            if(grid[changeX][changeY]==1){
                                queue.offer(new int[]{changeX,changeY});
                                grid[changeX][changeY]=0;
                            }
                        }
                    }
                }
            }
            maxNum=Math.max(num,maxNum);
            num=0;
        }
    }
    return maxNum;
}
public boolean condition(int[][] grid,int i,int j){
    return i>=0 && i<grid.length && j>=0 && j<grid[0].length;
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
static final int[][] directions={{-1,0},{0,1},{1,0},{0,-1}};
static int maxNum=0;
public static int maxAreaOfIsland(int[][] grid) {
    //行
    int m=grid.length;
    int n=grid[0].length;
    int num=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(grid[i][j]==1){
                num = dfs(grid, i, j, num);
                //搜索完毕之后  最大值
                maxNum= Math.max(num, maxNum);
                num=0;
            }
        }
    }
    return maxNum;
}
public static int dfs(int[][] grid,int i,int j,int num){
    if(grid[i][j]==0){
        return num;
    }
    num++;
    grid[i][j]=0;
    for (int[] direction : directions) {
        int changeX=direction[0]+i;
        int changeY=direction[1]+j;
        if(condition(grid,changeX,changeY))
            num=dfs(grid,changeX,changeY,num);
    }
    return num;
}
public static boolean condition(int[][] grid,int x,int y){
    return x>=0 && x<grid.length && y>=0 && y<grid[0].length;
}