[数据结构与算法]力扣day16

130.被围绕的区域

DFS，比较好写

    int m=0;
    int n=0;
    public void solve(char[][] board) {
        m=board.length;
        n=board[0].length;
        //1.查找边界是否相连O，是则从边界往上下左右进行dfs，相连的O标记为#
        for(int i=0;i<m;i++){
            dfs(board,i,0);
            dfs(board,i,n-1);
        }
        for(int i=0;i<n;i++){
            dfs(board,0,i);
            dfs(board,m-1,i);
        }
        //2.修改与边界不相连的O为X，与边界相连的#修改为O
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i][j]=='O'){
                    board[i][j]='X';
                }
                if(board[i][j]=='#'){
                    board[i][j]='O';
                }
            }
        }

    }

    public void dfs(char[][] board,int x,int y){
        //查找x行y列的上下左右是否相连'O'
        //检查x，y是否在范围内，是否越界
        if(x<0||x>=m||y<0||y>=n){
            return;
        }
        //判断当前节点是否是O
        if(board[x][y]!='O'){
            return;
        }else{
            //与当前O相连的上下左右进行dfs 递归处理
            board[x][y]='#';
            dfs(board,x-1,y);
            dfs(board,x+1,y);
            dfs(board,x,y-1);
            dfs(board,x,y+1);
        }
    }

797. 所有可能的路径

    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        DFS(0, graph, new LinkedList<>());
        return ans;
    }

    private void DFS(int cur, int[][] graph, LinkedList<Integer> list) {
        if (cur == graph.length - 1) {
            list.add(cur);
            ans.add(new ArrayList<>(list));
            return;
        }
        list.add(cur);
        for(int i=0;i<graph[cur].length;i++){
            DFS(graph[cur][i],graph,list);
            list.removeLast();
        }
    }

62. 不同路径

使用动态规划

    class Solution {
        public int uniquePaths(int m, int n) {
            int[][] dp = new int[m][n];
            //第一行都赋予 1
            for(int i = 0; i < m; ++i) {
                dp[i][0] = 1;
            }
            //第一列都赋予 1
            for(int j = 0; j < n; ++j) {
                dp[0][j] = 1;
            }
            //两个for循环推导，对于(i,j)来说，只能由上方或者左方转移过来
            for(int i = 1; i < m; ++i) {
                for(int j = 1; j < n; ++j) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
            return dp[m - 1][n - 1];
        }
    }

题解

63.不同路径 II

        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            int n = obstacleGrid.length;
            int m = obstacleGrid[0].length;
            int[][] dp = new int[n][m];
            //(0,0)这个格子可能有障碍物
            dp[0][0] = (obstacleGrid[0][0] == 1) ? 0 : 1;
            //处理第一列
            for(int i = 1; i < n; ++i) {
                if(obstacleGrid[i][0] == 1 || dp[i - 1][0] == 0) {
                    dp[i][0] = 0;
                } else {
                    dp[i][0] = 1;
                }
            }
            //处理第一行
            for(int j = 1; j < m; ++j) {
                if(obstacleGrid[0][j] == 1 || dp[0][j - 1] == 0) {
                    dp[0][j] = 0;
                } else {
                    dp[0][j] = 1;
                }
            }
            for(int i = 1; i < n; ++i) {
                for(int j = 1; j < m; ++j) {
                    //如果当前格子是障碍物
                    if(obstacleGrid[i][j] == 1) {
                        dp[i][j] = 0;
                        //路径总数来自于上方(dp[i-1][j])和左方(dp[i][j-1])
                    } else {
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                    }
                }
            }
            return dp[n - 1][m - 1];
        }

64.最小路径和

动态规划

    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        //第一列只能从上面走下来
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        //第一行只能从左边走过来
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                //递推公式，取从上面走下来和从左边走过来的最小值+当前坐标的值
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }