【每日刷题】Day143
【每日刷题】Day143
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 200. 岛屿数量 - 力扣（LeetCode）
2. LCR 105. 岛屿的最大面积 - 力扣（LeetCode）
3. 130. 被围绕的区域 - 力扣（LeetCode）
1. 200. 岛屿数量 - 力扣（LeetCode）
//思路：floodfill算法+哈希
class Solution {
public:
int ans = 0;
void dfs(vector<vector<char>>& grid,int i,int j,vector<vector<bool>>& hash)
{
if(i>=grid.size()||i<0||j>=grid[0].size()||j<0||grid[i][j]=='0')//回溯：越界 || 当前位置为字符 '0'
return;
hash[i][j] = true;//每访问一个 ‘1’ ，将该位置设为 "已访问"
//上、下、左、右递归
if(i-1>=0&&!hash[i-1][j])
dfs(grid,i-1,j,hash);
if(i+1<=grid.size()&&!hash[i+1][j])
dfs(grid,i+1,j,hash);
if(j-1>=0&&!hash[i][j-1])
dfs(grid,i,j-1,hash);
if(j+1<=grid[0].size()&&!hash[i][j+1])
dfs(grid,i,j+1,hash);
}
int numIslands(vector<vector<char>>& grid)
{
vector<vector<bool>> hash(301,vector<bool>(301));
for(int i = 0;i<grid.size();i++)
{
for(int j = 0;j<grid[0].size();j++)
{
if(!hash[i][j]&&grid[i][j]=='1')//在该位置进行 dfs 的条件
{
ans++;
dfs(grid,i,j,hash);
}
}
}
return ans;
}
};
2. LCR 105. 岛屿的最大面积 - 力扣（LeetCode）
//思路：floodfill算法+哈希
//这些题的思路基本都是一样的，实在是没必要重复画那么多决策树。
//本题的思路与上一题 "岛屿数量" 是完全类似的：
//遍历数组，遇到没有访问过的位置 并且 该位置值为1，在该位置进行 dfs，计算当前位置所组成岛屿的面积；dfs结束后与结果进行比较，记录较大值。
class Solution {
public:
int ans = 0;
void dfs(vector<vector<int>>& grid,int i,int j,vector<vector<bool>>& hash,int& tmp)
{
if(i>=grid.size()||i<0||j>=grid[0].size()||j<0||!grid[i][j])//回溯：越界 || 当前位置值为0
return;
hash[i][j] = true;//每到一个 1 位置，将该位置设为 "已访问"
tmp++;//统计岛屿面积
//上、下、左、右依次递归
if(i-1>=0&&!hash[i-1][j])
dfs(grid,i-1,j,hash,tmp);
if(i+1<=grid.size()&&!hash[i+1][j])
dfs(grid,i+1,j,hash,tmp);
if(j-1>=0&&!hash[i][j-1])
dfs(grid,i,j-1,hash,tmp);
if(j+1<=grid[0].size()&&!hash[i][j+1])
dfs(grid,i,j+1,hash,tmp);
}
int maxAreaOfIsland(vector<vector<int>>& grid)
{
vector<vector<bool>> hash(51,vector<bool>(51));
for(int i = 0;i<grid.size();i++)
{
for(int j = 0;j<grid[0].size();j++)
{
int tmp = 0;//tmp用于统计面积
if(!hash[i][j]&&grid[i][j])
{
dfs(grid,i,j,hash,tmp);
ans = ans>tmp?ans:tmp;//比较取较大值
}
}
}
return ans;
}
};
3. 130. 被围绕的区域 - 力扣（LeetCode）
//思路：floodfill+哈希
//本题思路还是类似，唯一的区别在于：我们如何区分哪些相连的 'O' 区域需要填充为 'X'，哪些不需要？
class Solution {
public:
void dfs(vector<vector<char>>& board,int i,int j,vector<vector<bool>>& hash)
{
if(i>=board.size()||i<0||j>=board[0].size()||j<0||board[i][j]=='X')//回溯：越界 || 当前位置为 'X'
return;
hash[i][j] = true;//将当前位置标记为 "已访问"
board[i][j] = 'X';//并将当前位置的 'O' 更改为 'X'
//上、下、左、右递归
if(i-1>=0&&!hash[i-1][j])
dfs(board,i-1,j,hash);
if(i+1<=board.size()&&!hash[i+1][j])
dfs(board,i+1,j,hash);
if(j-1>=0&&!hash[i][j-1])
dfs(board,i,j-1,hash);
if(j+1<=board[0].size()&&!hash[i][j+1])
dfs(board,i,j+1,hash);
}
void solve(vector<vector<char>>& board)
{
vector<vector<bool>> hash(201,vector<bool>(201));
vector<vector<char>> copy_board = board;//"替死鬼"数组，帮助我们标记 "不能更改" 的区域
//遍历 列边界，标记 列边界的 "不能更改" 的区域
for(int i = 0;i<copy_board.size();i++)
{
if(copy_board[i][0]=='O')
dfs(copy_board,i,0,hash);
if(copy_board[i][copy_board[0].size()-1]=='O')
dfs(copy_board,i,copy_board[0].size()-1,hash);
}
//遍历 行边界，标记 行边界的 "不能更改" 的区域
for(int j = 0;j<copy_board[0].size();j++)
{
if(copy_board[0][j]=='O')
dfs(copy_board,0,j,hash);
if(copy_board[copy_board.size()-1][j]=='O')
dfs(copy_board,copy_board.size()-1,j,hash);
}
//"替死鬼"数组帮我们标记了好了 "不能更改" 的区域，这里放心大胆地遍历board数组进行更改即可
for(int i = 0;i<board.size();i++)
{
for(int j = 0;j<board[0].size();j++)
{
if(!hash[i][j]&&board[i][j]=='O')
dfs(board,i,j,hash);
}
}
}
};