【综合算法学习】（第十五篇）
目录
图像渲染（medium）
题目解析
讲解算法原理
编写代码
岛屿数量（medium）
题目解析
讲解算法原理
编写代码
图像渲染（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
有⼀幅以mxn的⼆维整数数组表⽰的图画image，其中image[i][j]表⽰该图画的像素值⼤⼩。
你也被给予三个整数sr,sc和newColor。你应该从像素image[sr][sc]开始对图像进⾏上⾊填充。
为了完成上⾊⼯作，从初始像素开始，记录初始坐标的上下左右四个⽅向上像素值与初始坐标相同的相连像素点，接着再记录这四个⽅向上符合条件的像素点与他们对应四个⽅向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜⾊值改为newColor。
最后返回经过上⾊渲染后的图像。
⽰例1:
输⼊: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]]
解析:在图像的正中间，(坐标(sr,sc)=(1,1)),在路径上所有符合条件的像素点的颜⾊都被更改成2。
注意，右下⻆的像素没有更改为2，因为它不是在上下左右四个⽅向上与初始点相连的像素点。
⽰例2:
输⼊:image=[[0,0,0],[0,0,0]],sr=0,sc=0,newColor=2输出:[[2,2,2],[2,2,2]]
讲解算法原理
算法思路：
可以利⽤「深搜」或者「宽搜」，遍历到与该点相连的所有「像素相同的点」，然后将其修改成指定
的像素即可。递归函数设计：• 参数：
a. 原始矩阵；
b. 当前所在的位置；
c. 需要修改成的颜⾊。
• 函数体：
a. 先将该位置的颜⾊改成指定颜⾊（因为我们的判断，保证每次进⼊递归的位置都是需要修改的
位置）；
b. 遍历四个⽅向上的位置：
▪ 如果当前位置合法，并且与初试颜⾊相同，就递归进去。
编写代码
c++算法代码：
class Solution
{int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int m, n;int prev;
public:vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc,
int color) {if(image[sr][sc] == color) return image;m = image.size(), n = image[0].size();prev = image[sr][sc];dfs(image, sr, sc, color);return image;}void dfs(vector<vector<int>>& image, int i, int j, int color){image[i][j] = color;for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev){dfs(image, x, y, color);}}}
};java算法代码：
class Solution
{int[] dx = {0, 0, 1, -1};int[] dy = {1, -1, 0, 0};int m, n;int prev;public int[][] floodFill(int[][] image, int sr, int sc, int color) {if(image[sr][sc] == color) return image;m = image.length; n = image[0].length;prev = image[sr][sc];dfs(image, sr, sc, color);return image;}public void dfs(int[][] image, int i, int j, int color){image[i][j] = color;for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev){dfs(image, x, y, color);}}}
}岛屿数量（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给你⼀个由'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
提⽰：
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为'0'或'1'
讲解算法原理
算法思路：
遍历整个矩阵，每次找到「⼀块陆地」的时候：• 说明找到「⼀个岛屿」，记录到最终结果 ret ⾥⾯；
• 并且将这个陆地相连的所有陆地，也就是这块「岛屿」，全部「变成海洋」。这样的话，我们下次
遍历到这块岛屿的时候，它「已经是海洋」了，不会影响最终结果。
• 其中「变成海洋」的操作，可以利⽤「深搜」和「宽搜」解决，其实就是733.图像渲染这道题
这样，当我们，遍历完全部的矩阵的时候， ret 存的就是最终结果。
解法（dfs）：
算法流程：
1. 初始化 ret = 0 ，记录⽬前找到的岛屿数量;2. 双重循环遍历⼆维⽹格，每当遇到⼀块陆地，标记这是⼀个新的岛屿，然后将这块陆地相连的陆地全部变成海洋。
递归函数的设计：
1. 把当前格⼦标记为⽔；
2. 向上、下、左、右四格递归寻找陆地，只有在下标位置合理的情况下，才会进⼊递归：
a. 下⼀个位置的坐标合理；
b. 并且下⼀个位置是陆地
编写代码
c++算法代码：
class Solution
{vector<vector<bool>> vis;int m, n;
public:int numIslands(vector<vector<char>>& grid) {m = grid.size(), n = grid[0].size();vis = vector<vector<bool>>(m, vector<bool>(n));int ret = 0;for(int i = 0; i < m; i++)for(int j = 0; j < n; j++){if(!vis[i][j] && grid[i][j] == '1'){ret++;dfs(grid, i, j);}}return ret;}int dx[4] = {0, 0, -1, 1};int dy[4] = {1, -1, 0, 0};void dfs(vector<vector<char>>& grid, int i, int j){vis[i][j] = true;for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y]
== '1'){dfs(grid, x, y);}}}
};java算法代码：
class Solution
{boolean[][] vis;int m, n;int[] dx = {0, 0, -1, 1};int[] dy = {1, -1, 0, 0};public int numIslands(char[][] grid) {m = grid.length; n = grid[0].length;vis = new boolean[m][n];int ret = 0;for(int i = 0; i < m; i++)for(int j = 0; j < n; j++){if(!vis[i][j] && grid[i][j] == '1'){ret++;dfs(grid, i, j);}}return ret;}public void dfs(char[][] grid, int i, int j){vis[i][j] = true;for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y]
== '1'){dfs(grid, x, y);}}}
}