带孩子做网站,大专学历怎么自考,银川森淼生态园,竞价推广开户公司【每日刷题】Day143 #x1f955;个人主页#xff1a;开敲#x1f349; #x1f525;所属专栏#xff1a;每日刷题#x1f34d; #x1f33c;文章目录#x1f33c;
1. 200. 岛屿数量 - 力扣#xff08;LeetCode#xff09;
2. LCR 105. 岛屿的最大面积 - 力扣…【每日刷题】Day143 个人主页开敲 所属专栏每日刷题 文章目录
1. 200. 岛屿数量 - 力扣LeetCode
2. LCR 105. 岛屿的最大面积 - 力扣LeetCode
3. 130. 被围绕的区域 - 力扣LeetCode 1. 200. 岛屿数量 - 力扣LeetCode //思路floodfill算法哈希 class Solution { public: int ans 0; void dfs(vectorvectorchar grid,int i,int j,vectorvectorbool hash) { if(igrid.size()||i0||jgrid[0].size()||j0||grid[i][j]0)//回溯越界 || 当前位置为字符 0 return; hash[i][j] true;//每访问一个 ‘1’ 将该位置设为 已访问 //上、下、左、右递归 if(i-10!hash[i-1][j]) dfs(grid,i-1,j,hash); if(i1grid.size()!hash[i1][j]) dfs(grid,i1,j,hash); if(j-10!hash[i][j-1]) dfs(grid,i,j-1,hash); if(j1grid[0].size()!hash[i][j1]) dfs(grid,i,j1,hash); } int numIslands(vectorvectorchar grid) { vectorvectorbool hash(301,vectorbool(301)); for(int i 0;igrid.size();i) { for(int j 0;jgrid[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(vectorvectorint grid,int i,int j,vectorvectorbool hash,int tmp) { if(igrid.size()||i0||jgrid[0].size()||j0||!grid[i][j])//回溯越界 || 当前位置值为0 return; hash[i][j] true;//每到一个 1 位置将该位置设为 已访问 tmp;//统计岛屿面积 //上、下、左、右依次递归 if(i-10!hash[i-1][j]) dfs(grid,i-1,j,hash,tmp); if(i1grid.size()!hash[i1][j]) dfs(grid,i1,j,hash,tmp); if(j-10!hash[i][j-1]) dfs(grid,i,j-1,hash,tmp); if(j1grid[0].size()!hash[i][j1]) dfs(grid,i,j1,hash,tmp); } int maxAreaOfIsland(vectorvectorint grid) { vectorvectorbool hash(51,vectorbool(51)); for(int i 0;igrid.size();i) { for(int j 0;jgrid[0].size();j) { int tmp 0;//tmp用于统计面积 if(!hash[i][j]grid[i][j]) { dfs(grid,i,j,hash,tmp); ans anstmp?ans:tmp;//比较取较大值 } } } return ans; } }; 3. 130. 被围绕的区域 - 力扣LeetCode //思路floodfill哈希 //本题思路还是类似唯一的区别在于我们如何区分哪些相连的 O 区域需要填充为 X哪些不需要 class Solution { public: void dfs(vectorvectorchar board,int i,int j,vectorvectorbool hash) { if(iboard.size()||i0||jboard[0].size()||j0||board[i][j]X)//回溯越界 || 当前位置为 X return; hash[i][j] true;//将当前位置标记为 已访问 board[i][j] X;//并将当前位置的 O 更改为 X //上、下、左、右递归 if(i-10!hash[i-1][j]) dfs(board,i-1,j,hash); if(i1board.size()!hash[i1][j]) dfs(board,i1,j,hash); if(j-10!hash[i][j-1]) dfs(board,i,j-1,hash); if(j1board[0].size()!hash[i][j1]) dfs(board,i,j1,hash); } void solve(vectorvectorchar board) { vectorvectorbool hash(201,vectorbool(201)); vectorvectorchar copy_board board;//替死鬼数组帮助我们标记 不能更改 的区域 //遍历 列边界标记 列边界的 不能更改 的区域 for(int i 0;icopy_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;jcopy_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;iboard.size();i) { for(int j 0;jboard[0].size();j) { if(!hash[i][j]board[i][j]O) dfs(board,i,j,hash); } } } };
