算法【洪水填充】

2024-09-03 21:12
文章标签 算法 填充 洪水

本文主要是介绍算法【洪水填充】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

洪水填充是一种很简单的技巧,设置路径信息进行剪枝和统计,类似感染的过程。路径信息不撤销,来保证每一片的感染过程可以得到区分。看似是暴力递归过程,其实时间复杂度非常好,遍历次数和样本数量的规模一致。

下面通过一些题目来加深理解。

题目一

测试链接:https://leetcode.cn/problems/number-of-islands/

分析:洪水填充更可以看作是一个感染过程,将空间中符合条件的位置感染成我们需要的东西。这道题可以从是陆地的地方深度优先开始感染,将陆地感染成用以区分不再是陆地的信号。当遍历完整个空间后,我们就知道有多少个岛屿。代码如下。

class Solution {
public:int arr[5] = {0, 1, 0, -1, 0};void dfs(int i, int j, int row, int column, vector<vector<char>>& grid){if(i < 0 || i >= row || j < 0 || j >= column || grid[i][j] != '1'){return;}grid[i][j] = '0';for(int index = 0;index < 4;++index){dfs(i+arr[index], j+arr[index+1], row, column, grid);}}int numIslands(vector<vector<char>>& grid) {int row = grid.size();int column = grid[0].size();int ans = 0;for(int i = 0;i < row;++i){for(int j = 0;j < column;++j){if(grid[i][j] == '1'){++ans;dfs(i, j, row, column, grid);}}}return ans;}
};

其中,arr数组是用于遍历一个位置的周围即上下左右;在numIslands方法中调用dfs方法时,岛屿数加1,相当于重新感染一个新岛屿。

题目二

测试链接:https://leetcode.cn/problems/surrounded-regions/

分析:这个题可以看出,如果一个O和矩阵的四周存在的O相连,则这个O不会被替换成X,那么我们可以对矩阵的四周,也就是上下左右四个边界的O,使用深度优先进行感染,将其设为一个用以区分的信号。最后将矩阵中所有没有被更新为信号的O,更新为X;将更新为信号的位置更新为O。代码如下。

class Solution {
public:int arr[5] = {0, 1, 0, -1, 0};void dfs(int i, int j, int row, int column, vector<vector<char>>& board){if(i < 0 || i >= row || j < 0 || j >= column || board[i][j] != 'O'){return;}board[i][j] = 'z';for(int index = 0;index < 4;++index){dfs(i+arr[index], j+arr[index+1], row, column, board);}}void solve(vector<vector<char>>& board) {int row = board.size();int column = board[0].size();for(int i = 0;i < column;++i){if(board[0][i] == 'O'){dfs(0, i, row, column, board);}}for(int i = 0;i < column;++i){if(board[row-1][i] == 'O'){dfs(row-1, i, row, column, board);}}for(int i = 0;i < row;++i){if(board[i][0] == 'O'){dfs(i, 0, row, column, board);}}for(int i = 0;i < row;++i){if(board[i][column-1] == 'O'){dfs(i, column-1, row, column, board);}}for(int i = 0;i < row;++i){for(int j = 0;j < column;++j){if(board[i][j] == 'O'){board[i][j] = 'X';}else if(board[i][j] == 'z'){board[i][j] = 'O';}}}}
};

其中,信号为z,也就是说在最后更新时,O更新为X,z更新为O;最开始的4个for循环是对上下左右四个边界的O进行感染。

题目三

测试链接:https://leetcode.cn/problems/making-a-large-island/

分析:这道题涉及到岛屿的面积,所以在感染时,我们设置的信号应该是岛屿的编号。这样方便对不同编号的岛屿进行面积统计。在感染之后,我们得到了岛屿的数量,以及每个岛屿的面积。这时,遍历空间中那些不是岛屿的位置并进行判定。判定过程为对这些位置上下左右是否连接了岛屿,如果连接了,则加上这个岛屿的面积,注意不要重复计算岛屿面积,最后再加上这个位置的面积,也就是再加1。遍历空间中不是岛屿的位置,最终得到最大值。代码如下。

class Solution {
public:int area[125003] = {0};set<int> used;int arr[5] = {0, 1, 0, -1, 0};void dfs(int i, int j, int n, vector<vector<int>>& grid, int number){if(i < 0 || i >= n || j < 0 || j >= n || grid[i][j] != 1){return;}grid[i][j] = number;++area[number];for(int index = 0;index < 4;++index){dfs(i+arr[index], j+arr[index+1], n, grid, number);}}int largestIsland(vector<vector<int>>& grid) {int n = grid.size();int number = 2;int ans = 0;int temp_ans;for(int i = 0;i < n;++i){for(int j = 0;j < n;++j){if(grid[i][j] == 1){dfs(i, j, n, grid, number);++number;}}}for(int i = 2;i < number;++i){ans = ans > area[i] ? ans : area[i];}for(int i = 0;i < n;++i){for(int j = 0;j < n;++j){if(grid[i][j] == 0){temp_ans = 0;for(int index = 0;index < 4;++index){if(i+arr[index] >= 0 && i+arr[index] < n && j+arr[index+1] >= 0 && j+arr[index+1] < n &&grid[i+arr[index]][j+arr[index+1]] != 0 && used.count(grid[i+arr[index]][j+arr[index+1]]) == 0){temp_ans += area[grid[i+arr[index]][j+arr[index+1]]];used.insert(grid[i+arr[index]][j+arr[index+1]]);}}++temp_ans;ans = ans > temp_ans ? ans : temp_ans;used.clear();}}}return ans;}
};

其中,used用来判断一个岛屿是否已经被加过;number是当前岛屿的编号,因为0和1已经被使用所以number从2开始;需要将ans的初始值设为最大岛屿值是因为有可能全部是陆地,也就是没有连接的机会,那么这时的最大值自然就是最大岛屿值。

题目四

测试链接:https://leetcode.cn/problems/bricks-falling-when-hit/

分析:这个题我们看到了稳定和掉落这两个状态,很容易想到使用并查集。使用并查集的思路是,在没有打落砖块的时候,使用并查集将稳定的砖块设为一个集合,不稳定的砖块设为一个集合。最开始顶部的砖块是稳定的,然后相邻砖块之间归为一个集合。设置一个是否稳定的数组,顶部砖块是稳定的设为true,其他设为false。在union方法合并的时候,更新代表元素的是否稳定数组。遍历完砖块后,查询有多少个砖块的集合的代表元素是稳定的,这时候得到没有打入炮弹时的稳定砖块数目。实际上这个数目应该是统计的砖块数目。然后每打落一个砖块,重新统计一次稳定的数目,然后用上一次稳定的数目减此次稳定的数目再减1,因为打落的砖块是消失不计入不稳定的数目,但是这个方法复杂度太高,会超时。所以使用洪水填充加时光倒流。我们需要得到每次炮弹掉落的砖块数目,那么可以在所有炮弹打落之后往回加,也就是从最后一个炮弹开始,每一个炮弹没打之后多了多少稳定的砖块。主要流程就是,首先,将所有炮弹打出去,也就是把炮弹的指向位置的网格值减1,然后将顶部的网格,也就是已经稳定的网格开始洪水填充现存的砖块,将网格值更新为2(什么都行主要要区分1),然后开始时光倒流,从最后一个炮弹往前遍历,把炮弹指向位置处加1,如果为0,则代表之前这个位置没有砖块,continue;如果大于0,则判定这个位置的上下左右是否有等于2的砖块,因为2代表了现在稳定的砖块,如果有,则从炮弹恢复的位置开始洪水填充将1更新为2,更新的数目减1则为这个炮弹对应掉落的砖块数目,减1是因为炮弹指向位置不计入掉落的砖块数目。代码如下。

class Solution {
public:int arr[5] = {0, 1, 0, -1, 0};int dfs(int i, int j, int row, int column, vector<vector<int>>& grid){if(i < 0 || i >= row || j < 0 || j >= column || grid[i][j] != 1){return 0;}int num = 1;grid[i][j] = 2;for(int index = 0;index < 4;++index){num += dfs(i+arr[index], j+arr[index+1], row, column, grid);}return num;}vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {vector<int> ans;int row = grid.size();int column = grid[0].size();int length = hits.size();ans.assign(length, 0);for(int i = 0;i < length;++i){--grid[hits[i][0]][hits[i][1]];}for(int i = 0;i < column;++i){if(grid[0][i] == 1){dfs(0, i, row, column, grid);}}for(int i = length-1;i >= 0;--i){++grid[hits[i][0]][hits[i][1]];if(grid[hits[i][0]][hits[i][1]] == 0){continue;}if(hits[i][0] == 0){ans[i] = dfs(hits[i][0], hits[i][1], row, column, grid) - 1;}else if(hits[i][0] >= 0 && hits[i][0] < row && hits[i][1]+1 >= 0 && hits[i][1]+1 < column && grid[hits[i][0]][hits[i][1]+1] == 2){ans[i] = dfs(hits[i][0], hits[i][1], row, column, grid) - 1;}else if(hits[i][0] >= 0 && hits[i][0] < row && hits[i][1]-1 >= 0 && hits[i][1]-1 < column && grid[hits[i][0]][hits[i][1]-1] == 2){ans[i] = dfs(hits[i][0], hits[i][1], row, column, grid) - 1;}else if(hits[i][0]+1 >= 0 && hits[i][0]+1 < row && hits[i][1] >= 0 && hits[i][1] < column && grid[hits[i][0]+1][hits[i][1]] == 2){ans[i] = dfs(hits[i][0], hits[i][1], row, column, grid) - 1;}else if(hits[i][0]-1 >= 0 && hits[i][0]-1 < row && hits[i][1] >= 0 && hits[i][1] < column && grid[hits[i][0]-1][hits[i][1]] == 2){ans[i] = dfs(hits[i][0], hits[i][1], row, column, grid) - 1;}}return ans;}
};

其中,在恢复炮弹指向位置时大于0的判定中,如果指向位置本身就是顶部位置,那么不管这个位置的上下左右是否有为2的位置,直接填充。

这篇关于算法【洪水填充】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1134061

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

SpringBoot自定义注解如何解决公共字段填充问题

《SpringBoot自定义注解如何解决公共字段填充问题》本文介绍了在系统开发中,如何使用AOP切面编程实现公共字段自动填充的功能,从而简化代码,通过自定义注解和切面类,可以统一处理创建时间和修改时间... 目录1.1 问题分析1.2 实现思路1.3 代码开发1.3.1 步骤一1.3.2 步骤二1.3.3

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Go Mongox轻松实现MongoDB的时间字段自动填充

《GoMongox轻松实现MongoDB的时间字段自动填充》这篇文章主要为大家详细介绍了Go语言如何使用mongox库,在插入和更新数据时自动填充时间字段,从而提升开发效率并减少重复代码,需要的可以... 目录前言时间字段填充规则Mongox 的安装使用 Mongox 进行插入操作使用 Mongox 进行更

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

基于Java实现模板填充Word

《基于Java实现模板填充Word》这篇文章主要为大家详细介绍了如何用Java实现按产品经理提供的Word模板填充数据,并以word或pdf形式导出,有需要的小伙伴可以参考一下... Java实现按模板填充wor编程d本文讲解的需求是:我们需要把数据库中的某些数据按照 产品经理提供的 word模板,把数据

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系