颜色填充(程序员面试金典08.10)Java深度优先遍历实现
2023-03-14 22:52:15 时间
一、题目描述
编写函数,实现许多图片编辑软件都支持的「颜色填充」功能。
待填充的图像用二维数组 image 表示,元素为初始颜色值。初始坐标点的行坐标为 sr 列坐标为 sc。需要填充的新颜色为 newColor 。
「周围区域」是指颜色相同且在上、下、左、右四个方向上存在相连情况的若干元素。
请用新颜色填充初始坐标点的周围区域,并返回填充后的图像。
示例:
输入:
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 ,因为它不属于初始坐标点的周围区域。
二、思路讲解
对于我这种算法小白来说,看见在矩阵里上下左右跑的题目,第一反应是使用dfs深度优先遍历 。
在题目给出的点上进行涂色操作,然后在他的上下左右分别找旧颜色,找到就继续涂色和寻找的操作,如果上面没找到就回溯,找下面,下面没找到,回溯,找左边……如果上下左右都没找到,证明已经涂色完成,返回涂好的数组。
三、java代码实现
class Solution { public static int[][] floodFill(int[][] image, int sr, int sc, int newColor) { //保存原本的颜色 int oldColor = image[sr][sc]; //如果原本颜色就是要填充的颜色,直接将原来的image返回 if(oldColor == newColor) { return image; } int m = image.length-1; int n = image[0].length-1; //将当前位置颜色改变 image[sr][sc] = newColor; if(sr!=0 && image[sr-1][sc]==oldColor) { //向上找旧颜色 floodFill(image, sr-1, sc, newColor); } if(sr!=m && image[sr+1][sc]==oldColor) { //向下找旧颜色 floodFill(image, sr+1, sc, newColor); } if(sc!=0 && image[sr][sc-1]==oldColor) { //向左找旧颜色 floodFill(image, sr, sc-1, newColor); } if(sc!=n && image[sr][sc+1]==oldColor) { //向右找旧颜色 floodFill(image, sr, sc+1, newColor); } //前后左右都没有旧颜色了,说明填充完了,执行回溯 return image; } }
相关文章
- 发现 Linux SpaceFM 文件管理器的威力
- 夯实数据智能底座 共筑数字经济发展“新基石”
- 五分钟教你使用console.log发布公司的招聘信息
- 微软发布 Windows 11 Beta 预览版 Build 22621.1250 和 22623.1250 (KB5023008)
- Windows 11 学院:在 Windows 11 Build 25290 上如何为文件管理器启用标签页拖拽支持
- 微软Windows 11 Dev 预览版 Build 25290 发布:带来新的开始菜单提醒角标
- 微软正用全屏通知提醒 Windows 10 用户免费升级 Windows 11,要点击 5 次才能退出
- Linux Mint 21.2 将于 6 月发布:改进登录屏幕,优化 Pix 图像管理程序等等
- 字节面试也会问SPI机制?
- 微软正式停售 Windows 10 产品密钥 / 许可证:继续提供 ISO 镜像下载,推荐用户升级 Windows 11
- 用复古电脑程序 Toy CPU 学习低级编程
- Windows 11 新功能泄露:现代音量合成器、实验工具和新的文件管理器
- 微软 Windows 11 文件资源管理器全新设计曝光:UI 迎来大修,整合 Microsoft 365
- 对比Pandas,学习PySpark大数据处理
- 微软宣布为Windows 11 21H2设备开启自动更新到22H2版本
- 互联网都在说降本增效,小红书技术团队是怎么做的?
- 微软将继续提供 Windows 10 ISO 镜像下载,即将停售产品密钥 / 许可证
- 微软宣布为Windows 11 21H2 设备开启自动更新到 22H2 版本
- 面试突击:Properties和Yml有什么区别?
- 微软 Windows 11 Beta 预览版 22621.1245 和 22623.1245 (KB5022358) 发布