算法学习 | 深度优先搜索~一条道走到黑

目录

员工的重要性

图像渲染 

岛屿的周长 

被围绕的区域

岛屿数量 

---

 

深度优先搜索(Depth First Search)：深度优先搜索属于图算法的一种，其过程主要是对每一个可能的分支路径深入到不能再深入到为止，而且每个节点只能访问一次。深度优先搜索本质上就是暴力搜索，遍历了所有可能的情况，必然能得到解。DFS搜索的流程是一个树的形式，每次一条路走到黑。

深度优先搜索的关键是解决“当下该如何做”，下一步的做法和当下的做法是一致的。“当下如何做”一般是尝试每一种可能，用for循环遍历对于每一种可能确定之后，继续走下一步，当前的剩余可能等到从下一步回退之后再处理。据此可以抽象出深度优先搜索的模型

dfs(当前这一步的处理逻辑) {
    1.判断边界，是否已经一条道走到黑：回退
    2.尝试当下的每一种可能
    3.确定一种可能之后，继续下一步dfs(下一步)
}

员工的重要性

题目链接：leetcode-690.员工的重要性

示例

输入：[[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1

输出：11

描述：员工1自身的重要度是 5，他有两个直系下属 2 和 3 ，而且 2 和 3 的重要度均为 3 。因此员工 1 的总重要度是 5 + 3 + 3 = 11 。

题目分析：

根据题意，可以根据给定的员工id找到员工，从该员工开始遍历，对于每个员工，将其重要性相加，然后再对该员工的每个下属进行遍历，直到所有下属遍历完毕，此时的总和就是给定id的员工及他所有下属的重要度之和。由于每个员工的编号都不同，可以使用哈希表存储员工编号和对应员工，通过员工编号可以找到对应员工

class Solution {
    public int getImportance(List employees, int id) {
        if (employees.isEmpty()) {
            return 0;
        }
        Map info = new HashMap<>();
        for (Employee e : employees) {
            info.put(e.id, e);
        }
        return dfs(info, id);
    }
    private int dfs(Map info, int id) {
        Employee curE = info.get(id);
        int sumE = curE.importance;
        for (int curId : curE.subordinates) {
            sumE += dfs(info, curId);
        }
        return sumE;
    }
}

图像渲染 

题目链接：leetcode-773.图像渲染

 

示例 

输入：image = [[1,1,1],[1,1,0],[1,0,1]]，sr = 1, sc = 1, newColor = 2

输出：[[2,2,2],[2,2,0],[2,0,1]]

 

题目分析： 

本题的意思是给定一个二维数组表示的图画，并给定一个初始位置和修改后的颜色数字，从初始位置开始，遍历它的上下左右，如果值与初始位置的值相等，就进行修改，一直到遍历完所有符合条件的结点为止.

class Solution {
    int[][] nextPosition = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        if (image == null || image.length == 0) {
            return new int[0][0];
        }
        int flag = image[sr][sc];
        if (flag != color) {
            dfs(image, sr, sc, color, flag);
        }
        // dfs(image, sr, sc, color, flag);
        return image;
    }
    private void dfs(int[][] image, int sr, int sc, int color, int flag) {
        if (image[sr][sc] == flag) {
            image[sr][sc] = color;
            for (int i = 0; i < 4; i++) {
                int newSr = sr + nextPosition[i][0];
                int newSc = sc + nextPosition[i][1];
                if (newSr >= 0 && newSr < image.length && newSc >= 0 && newSc < image[0].length) {
                    dfs(image, newSr, newSc, color, flag);
                }
            }
        }
    }
}

岛屿的周长 

题目链接：leetcode-463.岛屿的周长

示例 

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

输出：16

题目分析

根据题意，每次遍历到陆地时，先判断其是否处于边界，如果处于上下左右四个边界，则周长+1，如果不处于边界，就判断其上下左右是否为海洋，如果为海洋，则周长+1，如果为陆地，则不进行操作，每遍历一个陆地后，将其标记出来，下次如果又到了这块陆地，就返回。

class Solution {
    int[][] nextPosition = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
    int ret;
    public int islandPerimeter(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[][] book = new int[m][n];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    dfs(grid, book, i, j, m, n);
                    break;
                }
            }
        }
        return ret;
    }
    private void dfs(int[][] grid, int[][] book, int row, int col, int m, int n) {
        if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == 0) {
            ret++;
            return ;
        }
        if (book[row][col] == 1) {
            return ;
        }
        book[row][col] = 1;
        for (int i = 0; i < 4; i++) {
            int newRow = row + nextPosition[i][0];
            int newCol = col + nextPosition[i][1];
            dfs(grid, book, newRow, newCol, m, n);
        }
    }
}

被围绕的区域

题目链接：leetcode-130.被围绕的区域

 

例如

输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

题目分析：

 由题意分析可知，只要其他的O与边界上的O相连，就不能被更换，因此，从四个边界的O符号开始，每次判断它的上下左右，只要与边界相连，就将其暂时设为*，接下来从这个*开始，继续寻找它的上下左右，直至到边界值为止，这里的边界值即超越矩阵范围或者遇到X为止.

注意：

        if (board[x][y] == '*') {
            return ;
        }

该判断语句一定要加上，否则当遇到*时，就会一直陷入死循环

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return ;
        }
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                dfs(board, i, 0);
            }
            if (board[i][n - 1] == 'O') {
                dfs(board, i, n - 1);
            }
        }
        for (int i = 1; i < n - 1; i++) {
            if (board[0][i] == 'O') {
                dfs(board, 0, i);
            }
            if (board[m - 1][i] == 'O') {
                dfs(board, m - 1, i);
            }
        }
        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';
                }
            }
        }
    }
    private void dfs(char[][] board, int x, int y) {
        if (x < 0 || y < 0 || x >= board.length || y >= board[0].length || board[x][y] == 'X') {
            return ;
        }
        if (board[x][y] == '*') {
            return ;
        }
        board[x][y] = '*';
        dfs(board, x + 1, y);
        dfs(board, x - 1, y);
        dfs(board, x, y + 1);
        dfs(board, x, y - 1);       
    }
}

岛屿数量 

题目链接：leetcode-200.岛屿数量

 

例如

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

输出： 1

题目分析：

对于该题，从任意一个陆地出发，一直遍历它的上下左右，直至四周都是边界或海洋为止，对于每个遍历到过的陆地都将其标记出来，遍历整个二维数组，将每一个未标记过的陆地都作为起点遍历一遍。每次结束之后岛屿数量+1，直至所有陆地都被标记过后为止

代码

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid[0].length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[][] book = new int[m][n];
        int ret = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && book[i][j] == 0) {
                    dfs(grid, book, i, j);
                    ret++;
                }
            }
        }
        return ret;
    }
    private void dfs(char[][] grid, int[][] book, int x, int y) {
        if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] == '0') {
            return ;
        }
        if (book[x][y] == 1) {
            return ;
        }
        book[x][y] = 1;
        dfs(grid, book, x + 1, y);
        dfs(grid, book, x - 1, y);
        dfs(grid, book, x, y + 1);
        dfs(grid, book, x, y - 1);
    }
}