Skip to content

Latest commit

 

History

History
329 lines (271 loc) · 6.55 KB

5_深度优先.md

File metadata and controls

329 lines (271 loc) · 6.55 KB
Raw

深度优先

1、岛屿数量

岛屿数量

// 思路：典型的 flood-fill 算法
private int m,n;

private boolean[][] visited;

private boolean inArea(int x,int y){
    return (x>=0 && x<m) && (y>=0 && y<n);
}

private int[][] d={
    {-1,0},
    {0,1},
    {1,0},
    {0,-1}
};

private void dfs(char[][] grid,int startx,int starty){
    visited[startx][starty]=true;
    for(int i=0;i<4;i++){
        int newX=startx+d[i][0];
        int newY=starty+d[i][1];
        if(inArea(newX,newY) &&
           (!visited[newX][newY] && grid[newX][newY]=='1')){
            dfs(grid,newX,newY);
        }
    }
}

public int numIslands(char[][] grid) {
    m=grid.length;
    if(m==0){
        return 0;
    }
    n=grid[0].length;
    visited=new boolean[m][n];
    int res=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(grid[i][j]=='1' && !visited[i][j]){
                res++;
                dfs(grid,i,j);
            }
        }
    }
    return res;
}

2、岛屿的最大面积

岛屿的最大面积

private int m,n;

private boolean[][] visited;

private int[][] d={
    {-1,0},
    {0,1},
    {1,0},
    {0,-1}
};

private boolean inArea(int x,int y){
    return (x>=0 && x<m) && (y>=0 && y<n);
}

private int dfs(int[][] grid,int startx,int starty){
    visited[startx][starty]=true;
    int area=1;
    for(int i=0;i<4;i++){
        int newX=startx+d[i][0];
        int newY=starty+d[i][1];
        if(inArea(newX,newY) &&
           (!visited[newX][newY] && grid[newX][newY]==1)){
            area+=dfs(grid,newX,newY);
        }
    }
    return area;
}

public int maxAreaOfIsland(int[][] grid) {
    m=grid.length;
    if(m==0){
        return 0;
    }
    n=grid[0].length;
    visited=new boolean[m][n];
    int res=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(grid[i][j]==1 && !visited[i][j]){
                res=Math.max(res,dfs(grid,i,j));
            }
        }
    }
    return res;
}

3、机器人的运动范围

机器人的运动范围

//思路：
//flood-fill 算法
private int m;
private int n;

private boolean[][] visited;

private int[][] d={
    {0,1}, //向右
    {-1,0},//向上
    {0,-1},//向左
    {1,0} //向下
};

private boolean inArea(int x,int y){
    return (x>=0 && x<m) && (y>=0 && y<n);
}

//获取一个数各个位上的数字相加
private int getNum(int num){
    int sum = 0;
    while(num>0){
        sum += num %10;
        num/=10;
    }
    return sum;
}

private boolean valid(int threshlod ,int x,int y){
    return (getNum(x)+getNum(y))<=threshlod;
}

private int walk(int threshold,int startx,int starty){
    visited[startx][starty]=true;
    int walks = 0;
    if(valid(threshold,startx,starty)){
        walks=1;
    }
    for(int i=0;i<4;i++){
        int newX = startx+d[i][0];
        int newY = starty+d[i][1];
        if(inArea(newX,newY)){
            if(!visited[newX][newY] && valid(threshold,newX,newY)){
                walks += walk(threshold,newX,newY);
            }
        }
    }
    return walks;
}

public int movingCount(int threshold, int rows, int cols) {
    if(threshold<0){ //threshold<0，则机器人就不能走了
        return 0;
    }
    m = rows;
    if(m==0){
        return 0;
    }
    n= cols;
    visited = new boolean[m][n];
    return walk(threshold,0,0);
}

4、被围绕的区域

被围绕的区域

private int m,n;

private boolean[][] visited;

private int[][] d={
    {-1,0},
    {0,1},
    {1,0},
    {0,-1}
};

private boolean inArea(int x,int y){
    return (x>=0 && x<m) && (y>=0 && y<n);
}

private void dfs(char[][] board,int startx,int starty){
    visited[startx][starty]=true;
    for(int i=0;i<4;i++){
        int newX=startx+d[i][0];
        int newY=starty+d[i][1];
        if(inArea(newX,newY)){
            if(!visited[newX][newY] && board[newX][newY]=='O'){
                dfs(board,newX,newY);
            }
        }
    }
}

public void solve(char[][] board) {
    m=board.length;
    if(m==0){
        return;
    }
    n=board[0].length;
    visited=new boolean[m][n];

    //从边边界进行标记
    for(int j=0;j<n;j++){
        if(!visited[0][j] && board[0][j]=='O'){
            dfs(board,0,j);
        }
        if(!visited[m-1][j] && board[m-1][j]=='O'){
            dfs(board,m-1,j);
        }
    }

    for(int i=0;i<m;i++){
        if(!visited[i][0] && board[i][0]=='O'){
            dfs(board,i,0);
        }
        if(!visited[i][n-1] && board[i][n-1]=='O'){
            dfs(board,i,n-1);
        }
    }

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

5、太平洋大西洋水流问题

太平洋大西洋水流问题

private int m,n;
private boolean[][] pacific;
private boolean[][] atlantic;

private int[][] d={
    {-1,0},
    {0,1},
    {1,0},
    {0,-1}
};

private boolean inArea(int x,int y){
    return (x>=0 && x<m) && (y>=0 && y<n);
}

private void dfs(int[][] matrix,int startx,int starty,boolean[][] visited){
    visited[startx][starty]=true;
    for(int i=0;i<4;i++){
        int newX=startx+d[i][0];
        int newY=starty+d[i][1];
        if(inArea(newX,newY)){
            if(!visited[newX][newY] && matrix[newX][newY]>=matrix[startx][starty]){
                dfs(matrix,newX,newY,visited);
            }
        }
    }
}

public List<List<Integer>> pacificAtlantic(int[][] matrix) {
    List<List<Integer>> res=new ArrayList<>();
    m=matrix.length;
    if(m==0){
        return res;
    }
    n=matrix[0].length;
    pacific=new boolean[m][n];
    atlantic=new boolean[m][n];

    for(int j=0;j<n;j++){
        if(!pacific[0][j]){
            dfs(matrix,0,j,pacific);
        }
        if(!atlantic[m-1][j]){
            dfs(matrix,m-1,j,atlantic);
        }
    }

    for(int i=0;i<m;i++){
        if(!pacific[i][0]){
            dfs(matrix,i,0,pacific);
        }
        if(!atlantic[i][n-1]){
            dfs(matrix,i,n-1,atlantic);
        }
    }

    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(pacific[i][j] && atlantic[i][j]){
                res.add(Arrays.asList(i,j));
            }
        }
    }
    return res;
}