南京网站seo专家,木门行业做网站有什么好处,教育培训机构,杭州网络公司建网站文章目录 733. 图像渲染解题思路#xff1a;BFS200. 岛屿数量解题思路#xff1a;广度优先遍历 733. 图像渲染
733. 图像渲染
有一幅以 m x n 的二维整数数组表示的图画 image #xff0c;其中 image[i][j] 表示该图画的像素值大小。
你也被给予三个整数 sr , sc 和… 文章目录 733. 图像渲染解题思路BFS200. 岛屿数量解题思路广度优先遍历 733. 图像渲染
733. 图像渲染
有一幅以 m x n 的二维整数数组表示的图画 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]]提示:
m image.lengthn image[i].length1 m, n 500 image[i][j], newColor 2160 sr m0 sc n 解题思路BFS
这道题我们在学搜索算法的时候就接触到了当时说可以使用 dfs 以及 bfs 方法来解决现在我们就用 bfs 方法来解决它并且这里对于 floodfill 算法以及这道题的思路就不再解释了具体可以参考递归专题的笔记但我相信这道题并不难理解
其实 bfs 非常简单就是利用 队列 来实现这个过程首先将起点位置放到队列中然后进行循环直到队列为空则停下来而在循环过程中将队头元素取出然后进行修改颜色然后将对头元素邻近元素也就是上下左右四个元素根据题目要求将符合的元素加入队列中达到 bfs 效果
剩下的就没什么好说的了具体参考下面代码
class Solution {
private:int dx[4] { 0, 0, 1, -1 };int dy[4] { -1, 1, 0, 0 };
public:vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int newcolor) {// 1. 因为我们没使用used数组所以需要先处理一下边界问题防止死循环int oldcolor image[sr][sc];if(oldcolor newcolor)return image;// 2. 将起点放到队列中queuepairint, int bfs;bfs.push({sr, sc});while(!bfs.empty()){// 3. 将队头元素取出然后进行修改颜色auto [x, y] bfs.front();bfs.pop();image[x][y] newcolor;// 4. 将对头元素邻近元素根据要求加入队列中达到bfs效果for(int i 0; i 4; i){int newx x dx[i], newy y dy[i];if(newx 0 newy 0 newx image.size() newy image[newx].size() image[newx][newy] oldcolor)bfs.push({newx, newy});}}return image;}
};200. 岛屿数量
200. 岛屿数量
给你一个由 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.lengthn grid[i].length1 m, n 300grid[i][j] 的值为 0 或 1 解题思路广度优先遍历
这道题具体思路可以参考递归专题中的笔记这里不再赘述
使用 bfs 来解决问题其实思路都是一样的以每个元素为起点找寻所有的岛屿并且记录数量当遇到 1 的时候则将记录数量增加然后进行广度优先遍历将 1 修改为 0。然后继续遍历二维数组直到岛屿都找到了为止
这里我们采用的修改方式是直接修改原数组如果不直接修改原数组也是可以的就得用一个 used 数组来判断是否走过都是一样的套路这里就不演示了
此外我们将 {i, j} 邻近的符合要求的节点添加到队列中时就要将其从 1 改为 0这样子可以减少许多不必要的重复遍历操作并且不这么做的话这道题也是会超时的
class Solution {
private:int dx[4] { 0, 0, 1, -1 };int dy[4] { -1, 1, 0, 0 };
public:int numIslands(vectorvectorchar grid) {// 以每个元素为起点找寻所有的岛屿并且记录数量int ret 0;for(int i 0; i grid.size(); i){for(int j 0; j grid[i].size(); j){if(grid[i][j] 1){ret;bfs(grid, i, j); // 进行广度优先遍历将1修改为0}}}return ret;}void bfs(vectorvectorchar grid, int i, int j){queuepairint, int qe;qe.push({i, j});grid[i][j] 0;while(!qe.empty()){auto [x, y] qe.front();qe.pop();for(int k 0; k 4; k){int newx x dx[k], newy y dy[k];if(newx 0 newy 0 newx grid.size() newy grid[newx].size() grid[newx][newy] 1){qe.push({newx, newy});grid[newx][newy] 0; // 提前将邻近节点改为0可以减少许多不必要的重复}}}}
};
