图论-算法题

797. 所有可能的路径

题目:

���你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

示例 1：

输入：graph = [[1,2],[3],[3],[]]输出：[[0,1,3],[0,2,3]]解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

示例 2：

输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

答案

class Solution {    List res;    List list;    public List allPathsSourceTarget(int[][] graph) {        res = new ArrayList();        list = new LinkedList();        list.add(0);        deal(graph,0);        return res;    }    //回溯:深度优先遍历    void deal(int[][] graph,int node){        if(node==graph.length-1){            res.add(new ArrayList(list));        }        for(int num : graph[node]){            list.add(num);            deal(graph,num);            list.removeLast();        }    }}

200. 岛屿数量

题目

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [  ["1","1","1","1","0"],  ["1","1","0","1","0"],  ["1","1","0","0","0"],  ["0","0","0","0","0"]]输出：1

示例 2：

输入：grid = [  ["1","1","0","0","0"],  ["1","1","0","0","0"],  ["0","0","1","0","0"],  ["0","0","0","1","1"]]输出：3

答案

class Solution {    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};    int m,n;    public int numIslands(char[][] grid) {        m = grid.length;        n = grid[0].length;        int res = 0;        for(int i=0;i            for(int j=0;j                if(grid[i][j]=='1'){                    res++;                    deal(grid,i,j);//将遍历过的陆地—水                }            }        }        return res;    }    void deal(char[][] grid,int i,int j){        if(i            return;        }        grid[i][j] = '0';        for(int[] dir : dirs){            deal(grid,i+dir[0],j+dir[1]);        }    }}    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};    int m,n;    int count;    public int maxAreaOfIsland(int[][] grid) {        m = grid.length;        n = grid[0].length;        int res = 0;        for(int i=0;i            for(int j=0;j                if(grid[i][j]==1){                    count = 0;                    deal(grid,i,j);                    res = Math.max(res,count);                }            }        }        return res;    }    void deal(int[][] grid,int i,int j){        if(i            return;        }        grid[i][j] = 0;        count++;        for(int[] dir : dirs){            deal(grid,i+dir[0],j+dir[1]);        }    }}    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};    int m,n;    public int numEnclaves(int[][] grid) {        m = grid.length;        n = grid[0].length;        for(int i=0;i            deal(grid,i,0);            deal(grid,i,n-1);        }        for(int j=0;j            deal(grid,0,j);            deal(grid,m-1,j);        }        int res = 0;        for(int i=1;i            for(int j=1;j                if(grid[i][j]==1){                    res++;                }            }        }        return res;    }    void deal(int[][] grid,int i,int j){        if(i            return;        }        grid[i][j] = 0;        for(int[] dir : dirs){            deal(grid,i+dir[0],j+dir[1]);        }    }}    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};    int m,n;    public void solve(char[][] board) {        m = board.length;        n = board[0].length;        for(int i=0;i            deal(board,i,0);            deal(board,i,n-1);        }        for(int j=0;j            deal(board,0,j);            deal(board,m-1,j);        }        for(int i=0;i            for(int j=0;j                if(board[i][j]=='A'){                    board[i][j] = 'O';                }else if(board[i][j]=='O'){                    board[i][j] ='X';                }            }        }    }    void deal(char[][] board,int i,int j){        if(i            return;        }        board[i][j] = 'A';        for(int[] dir : dirs){            deal(board,i+dir[0],j+dir[1]);        }    }}    public boolean canVisitAllRooms(List        boolean[] visited = new boolean[rooms.size()];        Queue            int curr = queue.poll();            for(int index : rooms.get(curr)){                if(!visited[index]){                    visited[index] = true;                    queue.offer(index);                }            }        }        for(boolean flag : visited){            if(!flag){                return false;            }        }        return true;    }}    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};    int m,n;    public int islandPerimeter(int[][] grid) {        m = grid.length;        n = grid[0].length;        int res = 0;        for(int i=0;i            for(int j=0;j                if(grid[i][j]==1){                    for(int[] dir : dirs){                        int p = i + dir[0];                        int q = j + dir[1];                        if(p                            res++;                        }                    }                }            }        }        return res;    }}