[Leetcode] BFSDFS类java题解记录

130. 被围绕的区域

class Solution {

    public int rows,cols;

    public void solve(char[][] board) {

        rows = board.length;
        cols = board[0].length;
        for(int i = 0;i=rows || j<0 || j>=cols || board[i][j]=='X' || board[i][j]=='Z'){
            return;
        }
        board[i][j]='Z';
        dfs(board, i-1, j);
        dfs(board, i+1, j);
        dfs(board, i, j-1);
        dfs(board, i, j+1);
    }
}

BFS写法： 

class Solution {
    //BFS迭代写法
    public void solve1(char[][] board) {
        int rows = board.length;
        if (rows < 1)
            return;
        int cols = board[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                boolean isEdge = i == 0 || j == 0 || i == rows - 1 || j == cols - 1;
                if (isEdge && board[i][j] == 'O') {
                    bfs(board, i, j);
                }
            }
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == 'Z') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    private void bfs(char[][] board, int i, int j) {
        Queue queue = new LinkedList();
        queue.offer(new int[]{i, j});
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0];
            int c = cur[1];
            if (r >= 0 && r < board.length && c >= 0 && c < board[0].length && board[r][c] == 'O') {
                board[r][c] = 'Z';
                queue.offer(new int[]{r - 1, c});
                queue.offer(new int[]{r + 1, c});
                queue.offer(new int[]{r, c - 1});
                queue.offer(new int[]{r, c + 1});
            }
        }
    }
}

200. 岛屿数量

class Solution {

    public int rows,cols;
    public int numIslands(char[][] grid) {
        rows = grid.length;
        cols = grid[0].length;
        int res = 0;
        for(int i = 0;i=rows || j<0 || j>=cols || grid[i][j]=='0'){
            return;
        }
        grid[i][j]='0';
        dfs(grid,i-1,j);
        dfs(grid,i+1,j);
        dfs(grid,i,j-1);
        dfs(grid,i,j+1);
    }
}

79. 单词搜索

class Solution {
    public final int[][] dirs = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
    public int rows, cols;

    public boolean exist(char[][] board, String word) {
        rows = board.length;
        cols = board[0].length;
        boolean[][] visited = new boolean[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (dfs(board, i, j, 0, visited, word)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, int i, int j, int k, boolean[][] visited, String word) {
        if (word.charAt(k) != board[i][j]) {
            return false;
        }
        if (word.charAt(k) == board[i][j] && k == word.length() - 1) {
            return true;
        }
        visited[i][j] = true;
        for (int[] dir : dirs) {
            int i1 = i + dir[0];
            int j1 = j + dir[1];
            if (i1 >= 0 && i1 < rows && j1 >= 0 && j1 < cols && !visited[i1][j1]) {
                if (dfs(board, i1, j1, k + 1, visited, word)) {
                    return true;
                }
            }
        }
        visited[i][j] = false;
        return false;
    }
}

547. 省份数量

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int len = isConnected.length;
        boolean[] isVisit = new boolean[len];
        LinkedList que = new LinkedList<>();
        int circle = 0;
        for (int i = 0; i < len; i++) {
            if (isVisit[i]) {
                continue;
            }
            que.addLast(i);
            isVisit[i] = true;
            while (!que.isEmpty()) {
                int j = que.removeLast();
                for (int k = 0; k < len; k++) {
                    if (isConnected[j][k] == 1 && !isVisit[k]) {
                        isVisit[k] = true;
                        que.addLast(k);
                    }
                }
            }
            circle++;
        }
        return circle;
    }
}

463. 岛屿的周长

class Solution {
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    public int islandPerimeter(int[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        int rows = grid.length;
        int cols = grid[0].length;
        int result = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] != 1) {
                    continue;
                }
                for (int z = 0; z < 4; z++) {
                    int x1 = i + dx[z];
                    int y1 = j + dy[z];
                    if (x1 < 0 || x1 >= rows || y1 < 0 || y1 >= cols || grid[x1][y1] == 0) {
                        result += 1;
                    }
                }
            }
        }
        return result;
    }
}

329. 矩阵中的最长递增路径

class Solution {
    public int rows, cols;
    public int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int longestIncreasingPath(int[][] matrix) {
        rows = matrix.length;
        cols = matrix[0].length;
        int maxlen = 0;
        int[][] path = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int len = dfs(matrix, i, j, path);
                maxlen = Math.max(len, maxlen);
            }
        }
        return maxlen;
    }

    private int dfs(int[][] matrix, int i, int j, int[][] path) {
        if (path[i][j] > 0) {
            return path[i][j];
        }
        int maxlen = 1;
        for (int[] dir : dirs) {
            int i1 = i + dir[0];
            int j1 = j + dir[1];
            if (i1 >= 0 && i1 < rows && j1 >= 0 && j1 < cols && matrix[i1][j1] > matrix[i][j]) {
                int len = 1 + dfs(matrix, i1, j1, path);
                maxlen = Math.max(len, maxlen);
            }
        }
        path[i][j] = maxlen;
        return maxlen;
    }
}

207. 课程表

210. 课程表 II

public class CanFinish {

    // 207. 课程表
    public boolean canFinish(int numCourses, int[][] prerequisites) {

        int[] cnt = new int[numCourses];
        for (int[] pair : prerequisites) {
            cnt[pair[0]]++;
        }
        LinkedList que = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (cnt[i] == 0) {
                que.addLast(i);
            }
        }
        int cntSize = que.size();
        while (!que.isEmpty()) {
            Integer x = que.removeFirst();
            for (int[] pair : prerequisites) {
                if (pair[1] == x) {
                    cnt[pair[0]]--;
                    if (cnt[pair[0]] == 0) {
                        que.addLast(pair[0]);
                        cntSize++;
                    }
                }
            }
        }
        return numCourses == cntSize;
    }

    // 210. 课程表 II
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] cnt = new int[numCourses];
        for (int[] pair : prerequisites) {
            cnt[pair[0]]++;
        }
        LinkedList que = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (cnt[i] == 0) {
                que.addLast(i);
            }
        }
        int cntSize = que.size();
        int[] result = new int[numCourses];
        int index = 0;
        while (!que.isEmpty()) {
            Integer x = que.removeFirst();
            result[index++] = x;
            for (int[] pair : prerequisites) {
                if (pair[1] == x) {
                    cnt[pair[0]]--;
                    if (cnt[pair[0]] == 0) {
                        que.addLast(pair[0]);
                        cntSize++;
                    }
                }
            }
        }
        if (numCourses != cntSize) {
            return new int[]{};
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] prerequisites = new int[][]{{1, 0}};
        CanFinish solution = new CanFinish();
        System.out.println(solution.canFinish(2, prerequisites));
    }
}

365. 水壶问题

class Solution {
    public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        if (targetCapacity > jug1Capacity + jug2Capacity) {
            return false;
        }
        Deque stack = new LinkedList();
        stack.push(new int[]{0, 0});
        Set isContain = new HashSet<>();
        while (!stack.isEmpty()) {
            int[] remain = stack.peek();
            stack.pop();
            int remainX = remain[0];
            int remainY = remain[1];
            if (isContain.contains(getHashValue(remainX, remainY))) {
                continue;
            }
            isContain.add(getHashValue(remainX, remainY));
            if (remainX == targetCapacity || remainY == targetCapacity || remainX + remainY == targetCapacity) {
                return true;
            }

            stack.push(new int[]{remainX, jug2Capacity});

            stack.push(new int[]{jug1Capacity, remainY});

            stack.push(new int[]{0, remainY});

            stack.push(new int[]{remainX, 0});

            stack.push(new int[]{remainX + Math.min(jug1Capacity - remainX, remainY), remainY - Math.min(jug1Capacity - remainX, remainY)});

            stack.push(new int[]{remainX - Math.min(remainX, jug2Capacity - remainY), remainY + Math.min(remainX, jug2Capacity - remainY)});
        }

        return false;

    }

    private long getHashValue(int x, int y) {
        return (long)x * 1000000L + y;
    }
}

542. 01 矩阵

class Solution {
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int[][] updateMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] dist = new int[m][n];
        boolean[][] seen = new boolean[m][n];
        Queue queue = new LinkedList();
        // 将所有的 0 添加进初始队列中
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                    seen[i][j] = true;
                }
            }
        }

        // 广度优先搜索
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int i = cell[0], j = cell[1];
            for (int d = 0; d < 4; ++d) {
                int ni = i + dirs[d][0];
                int nj = j + dirs[d][1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && !seen[ni][nj]) {
                    dist[ni][nj] = dist[i][j] + 1;
                    queue.offer(new int[]{ni, nj});
                    seen[ni][nj] = true;
                }
            }
        }

        return dist;
    }
}

class Solution {

    public final int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int[][] updateMatrix(int[][] mat) {

        LinkedList que = new LinkedList<>();

        int rows = mat.length;
        int cols = mat[0].length;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (mat[i][j] == 0) {
                    que.addLast(new int[]{i, j});
                } else {
                    mat[i][j] = -1;
                }
            }
        }

        while (!que.isEmpty()) {
            int[] point = que.removeFirst();
            for (int[] dir : dirs) {
                int x1 = point[0] + dir[0];
                int y1 = point[1] + dir[1];
                if (x1 >= 0 && x1 < rows && y1 >= 0 && y1 < cols && mat[x1][y1] == -1) {
                    mat[x1][y1] = mat[point[0]][point[1]] + 1;
                    que.addLast(new int[]{x1, y1});
                }
            }
        }
        return mat;

    }
}