代碼隨想錄圖論 第一天 | 797.所有可能的路徑 200. 島嶼數(shù)量

一、797.所有可能的路徑

題目鏈接：https://leetcode.cn/problems/all-paths-from-source-to-target/
思路：求從0到n-1的所有路徑，終止條件是當(dāng)前節(jié)點(diǎn)為n-1。本題圖的結(jié)構(gòu)是group[][]，group[x]表示x節(jié)點(diǎn)所能到達(dá)的所有節(jié)點(diǎn)的集合，深度優(yōu)先做本題會(huì)一路向下搜索，到頭后回溯。

class Solution {
    List<List<Integer>> arrayLists = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        list.add(0);
        dfs(graph, 0);
    
        return arrayLists;
    }

    void dfs(int[][] graph, int cur) {
        if (cur == graph.length-1) {
            arrayLists.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < graph[cur].length; i++) {
            list.add(graph[cur][i]);
            dfs(graph, graph[cur][i]);
            list.remove(list.size()-1);
        }
    }
}

200. 島嶼數(shù)量

題目鏈接：https://leetcode.cn/problems/number-of-islands/

深搜：當(dāng)前節(jié)點(diǎn)為1時(shí)島嶼數(shù)加1，然后把當(dāng)前節(jié)點(diǎn)設(shè)置為0，并從當(dāng)前節(jié)點(diǎn)開始進(jìn)行上下左右四個(gè)方向的深度搜索，只要沒越界，不是0，那就是相連的就都設(shè)置為0，直到遞歸結(jié)束，然后外層遍歷開始尋找下一個(gè)為1的島嶼。

class Solution {
   public int numIslands(char[][] grid) {
        int num = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    num++;
                    dfs(grid, i, j);
                }
            }
        }
        return num;
    }

    void dfs(char[][] grid, int x, int y) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == '0'){
            return;
        }
        grid[x][y] = '0';
        // 按照上下左右四個(gè)方向深度優(yōu)先遍歷
        dfs(grid, x-1, y);
        dfs(grid, x+1, y);
        dfs(grid, x, y-1);
        dfs(grid, x, y+1);
    }
}

廣搜：廣度優(yōu)先需要額外有一個(gè)標(biāo)記數(shù)組和隊(duì)列，如果當(dāng)前節(jié)點(diǎn)未遍歷過，且為1，進(jìn)行廣度優(yōu)先搜索，入隊(duì)，出隊(duì)，每個(gè)出隊(duì)節(jié)點(diǎn)只搜索4個(gè)位置，即當(dāng)前節(jié)點(diǎn)是上下左右，只要沒超范圍而且是1就可以入隊(duì)，入隊(duì)后要進(jìn)行標(biāo)記，直到該次廣搜結(jié)束，島嶼數(shù)量加1.文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-714444.html

class Solution {
   // 上下左右
    int[][] move = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    boolean[][] visited;
    public int numIslands(char[][] grid) {
        int num = 0;
        visited = new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    bfs(grid, i, j);
                    num++;
                }
            }
        }
        return num;
    }

    void bfs(char[][] grid, int x, int y) {
        Deque<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int m = cur[0], n = cur[1];
            for (int i = 0; i < move.length; i++) {
                int nextX = m + move[i][0];
                int nextY = n + move[i][1];
                if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue;
                if (!visited[nextX][nextY] && grid[nextX][nextY] == '1'){
                    queue.offer(new int[]{nextX, nextY});
                    visited[nextX][nextY] = true;
                }
            }
        }
    }
}

到了這里，關(guān)于代碼隨想錄圖論 第一天 | 797.所有可能的路徑 200. 島嶼數(shù)量的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！