网站开发中心,百度网站上传,兰州交通发展建设集团公司网站,iis网站无法启动目录 1#xff0c; 算法介绍2#xff0c;算法原理和代码实现(含题目链接)733.图像渲染200.岛屿的数量695.岛屿的最大面积130.被围绕的区域 3#xff0c; 算法总结 1#xff0c; 算法介绍
FloodFill(洪水灌溉) 算法介绍#xff1a;
假设一个 4 * 4 的方格代表一块土地 算法介绍2算法原理和代码实现(含题目链接)733.图像渲染200.岛屿的数量695.岛屿的最大面积130.被围绕的区域 3 算法总结 1 算法介绍
FloodFill(洪水灌溉) 算法介绍
假设一个 4 * 4 的方格代表一块土地土地上有些地方是凹陷的假设用负数表示-1-2-3……大小表示凹陷程度有些地方是凸起的假设用正数表示1,2,3,4……大小表示凸起程度。
此时如果发洪水或是下雨就会把凹陷的地方填满水凸起的部分就会把凹陷的部分包围填满水的区域会被连成一片一片的。 所以这类问题要么是问有多少块填平的区域要么是问最大的区域面积是多少要么是问某一块区域的边长是多少。 有些问题是规定只能上下左右联通有些是斜对角也能联通。
本质就是找出具有相同性质的联通块。 解决方法 dfs 深度优先遍历使用递归 bfs宽度优先遍历层序遍历 2算法原理和代码实现(含题目链接)
733.图像渲染 算法原理 使用队列进行层序遍历(bfs)。首先要记录原坐标的像素值再以这个坐标为中心上下左右四个方向进行遍历如果发现有相等的像素值就把这个坐标入队列并且修改成指定的像素值。接着再取出队头元素进行判断修改遍历四个方向入队列…直到队列为空此时就把图中所有等于原像素值的位置修改成了指定的像素值。 细节/技巧问题
(1) 记录完原坐标的像素值时先进行一次判断是否等于要修改的值如果是就直接返回图像。
(2) 要得到上下左右四个方向的坐标有技巧。
(3) 要注意遍历四个方向时坐标不能越界。
代码实现
class Solution
{typedef pairint, int PII;int dx[4] {0,0,1,-1};int dy[4] {1,-1,0,0};
public:vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int color) {int prev image[sr][sc];if(prev color) return image; // 处理特殊情况int m image.size();int n image[0].size();queuePII q;q.push({sr ,sc});while(q.size()){auto [a, b] q.front();q.pop();if(image[a][b] prev) image[a][b] color;// 判断上下左右的值for(int i 0; i 4; i){int x a dx[i];int y b dy[i];if(x 0 x m y 0 y n image[x][y] prev)q.push({x, y});}}return image;}
};200.岛屿的数量 算法原理 这道题就是第一道题的进阶版也是使用队列层序遍历(bfs)只不过是多次使用bfs算法所以把它写成一个函数bfs在这里的作用是标记陆地。遍历整个矩阵当遇到陆地(‘1’)并且没有被遍历过时使用bfs并岛屿数量1。 细节/技巧问题 (1) 当取出队头坐标进行上下左右遍历时一定会遍历到相同的位置此时就要进行区分。可以定义一个bool类型的标记数组vis如果位置已经遍历过置为true否则为false。
(2) 给bfs函数进行传参时如果想要形参简洁一些可以把一些变量定义在main函数外变为公有的这样可以减少麻烦。比如这道题里矩阵的行和列标记数组vis等
代码实现
class Solution
{int dx[4] {0,0,1,-1};int dy[4] {1,-1,0,0};int m,n;bool vis[301][301]; // 记录位置有没有被遍历过true有,false没有
public:int numIslands(vectorvectorchar grid) {m grid.size(), n grid[0].size();int ret 0; //记录岛屿数量// 遍历整个网格for(int i 0;i m; i){for(int j 0;j n; j){// 如果是陆地并且没有遍历过if(grid[i][j] 1 !vis[i][j]){// 把这块陆地标记bfs( grid,i, j);ret;}}} return ret;}void bfs(vectorvectorchar grid, int i, int j){queuepairint ,int q;q.push({i, j});vis[i][j] true; // 入队列代表你已经遍历过了要标记while(q.size()){auto [a,b] q.front();q.pop();for(int k 0; k 4; k){int x a dx[k], y b dy[k];if(x 0 x m y 0 y n grid[x][y] 1 !vis[x][y]){q.push({x,y});vis[x][y] true;}}}}
};695.岛屿的最大面积 算法原理 这道题也是基于前两题的bfs算法也要多次使用bfs所以也写成函数。它的作用是标记陆地并且统计每块陆地的面积。遍历矩阵当遇到没有被遍历过的陆地(1)时调用bfs函数进行标记与统计遇到符合要求的坐标并且入队列后陆地面积1。统计完每一块陆地的面积再返回给main函数。 细节/技巧问题
参考前面两题。
代码实现
class Solution
{int dx[4] {0,0,1,-1};int dy[4] {1,-1,0,0};bool vis[51][51];int m,n;
public:int maxAreaOfIsland(vectorvectorint grid) {m grid.size(), n grid[0].size();int ret_max 0;int ret 0;for(int i 0;i m; i){for(int j 0; j n; j){if(grid[i][j] 1 !vis[i][j]){ret bfs(grid, i, j);ret_max max(ret, ret_max);}}}return ret_max;}int bfs(vectorvectorint grid, int i, int j){int ret 0; // 记录岛屿面积queuepairint ,int q;q.push({i, j});vis[i][j] true; // 记得标记ret;while(q.size()){auto[a,b] q.front();q.pop();for(int k 0; k 4; k){int x adx[k], y bdy[k];if(x 0 x m y 0 y n grid[x][y] 1 !vis[x][y]){q.push({x, y});vis[x][y] true;ret;}}}return ret;}
};130.被围绕的区域 算法原理 这道题也是bfs算法的综合运用。如果按照题意正面去解决就是直接把除与边界’O’(包括边界)联通的区域外其余全部修改为’X’会显的很麻烦。所以正难则反我们可以先把与边界’O’(包括边界)联通的区域修改为其他字符再遍历整个数组把剩余的’O’区域修改为’X’最后把原来修改为的其他字符还原为’O’这样也可以解决问题并且整个代码书写也更清晰。当然这里的bfs算法也不止使用一次所以也要写成函数它的作用是把与边界’O’(包括边界)联通的区域修改为其他字符。 细节/技巧问题
参考前面三题
代码实现
class Solution
{int dx[4] {0,0,1,-1};int dy[4] {1,-1,0,0};int m, n;bool vis[201][201];
public:void solve(vectorvectorchar board) {m board.size(), n board[0].size();// 先把边界上的O区域改为无关字符for(int i 0; i m; i){if(board[i][0] O) bfs(board, i, 0);if(board[i][n-1] O) bfs(board, i, n-1);}for(int j 0; j n; j){if(board[0][j] O) bfs(board, 0, j);if(board[m-1][j] O) bfs(board, m-1, j);}// 再遍历矩阵把所有O改为Xfor(int i 0; i m; i){for(int j 0; j n; j){if(board[i][j] O !vis[i][j])board[i][j] X;}}// 最后还要把前面改过的.还原为Ofor(int i 0; i m; i){for(int j 0; j n; j)if(board[i][j] .)board[i][j] O;}}void bfs(vectorvectorchar board, int i, int j){queuepairint ,int q;q.push({i ,j});vis[i][j] true;board[i][j] .;while(q.size()){auto[a,b] q.front();q.pop();for(int k 0; k 4; k){int x adx[k], y bdy[k];if(x 0 x m y 0 y n !vis[x][y] board[x][y] O){q.push({x, y});vis[x][y] true;board[x][y] .;}}}}
};3 算法总结 bfs是一种十分经典的算法它总是使用队列来完成层序遍历其实就是以当前位置为中心再进行上下左右四个方向的位置识别查找与统计。通过前面四道题的介绍我们也可以发现bfs算法也是有大致的固定模版只不过每个bfs算法在解决问题的过程中的作用不同而已。
