BFS和codetop复习
BFS和codetop复习
- BFS
- 1.[图像渲染](https://leetcode.cn/problems/flood-fill/description/)
- 2.[岛屿数量](https://leetcode.cn/problems/number-of-islands/)
- 3.[岛屿的最大面积](https://leetcode.cn/problems/max-area-of-island/description/)
- 4.[被围绕的区域](https://leetcode.cn/problems/surrounded-regions/description/)
- 2.递归
- 1.[反转链表](https://leetcode.cn/problems/reverse-linked-list/)
BFS
1.图像渲染
class Solution {
public:vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {if(image[sr][sc]!=color) dfs(image,sr,sc,color,image[sr][sc]);return image;}int dx[4]={-1,1,0,0};int dy[4]={0,0,-1,1};void dfs(vector<vector<int>>& image, int r, int c, int newcolor,int oldcolor){ //先写越界条件if(r<0||c<0||r>=image.size()||c>=image[0].size()) return;if(image[r][c]==oldcolor)//如果是旧颜色{image[r][c]=newcolor;//这变成新颜色//然后从四个方向去遍历for(int i=0;i<4;i++) dfs(image,r+dx[i],c+dy[i],newcolor,oldcolor); //这里要加dx[i],dy[i] }}
};
2.岛屿数量
把是1的岛屿全部标记,每次上下左右走到底之后,ret++
class Solution {
public:int numIslands(vector<vector<char>>& sl) {int ret=0;for(int i=0;i<sl.size();i++)for(int j=0;j<sl[0].size();j++)if(sl[i][j]=='1'){dfs(sl,i,j);ret++;}return ret;}int dx[4]={-1,1,0,0};int dy[4]={0,0,-1,1};void dfs(vector<vector<char>>& sl,int x,int y){if(x<0||y<0||x>=sl.size()||y>=sl[0].size()||sl[x][y]!='1') return;//把这份方格里所有1全变成2sl[x][y]='2';for(int i=0;i<4;i++){dfs(sl,x+dx[i],y+dy[i]);}}
};3.岛屿的最大面积
//这里把每个岛屿的面积先用cur记录,出dfs的时候再与s作比较
//把每个岛屿的1用2替换避免重复记录(cur++)
//每次进dfs的时候初始化cur=0;
4.被围绕的区域
//先从边缘搜索然后改成1,再遍历把x->o,再把1->o
2.递归
1.反转链表
//1.链表是一种特殊的树,逆置只需要做一次后序遍历
//2.相信dfs
