目录

员工的重要性

图像渲染 

岛屿的周长 

被围绕的区域

岛屿数量 

深度优先搜索(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);}
}