算法入门C——733. 图像渲染
2021/11/9 22:40:15
本文主要是介绍算法入门C——733. 图像渲染,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
LeetCode刷题——算法学习计划(入门部分)
文章目录
- 题目描述
- 思路介绍
- 我的第一次正确提交
- 官方版本
- 方法一:广度优先搜索
- 方法二:深度优先搜索
题目描述
思路介绍
个人思路:(深度优先搜索)
根据题目的提示,我们可以得知像素存放在二维数组image
中,它的行数为imageSize
,列数为imageColSize[0]
(第一行的列数),定义一个递归函数dfs()
,函数里将image[sr,sc]
的像素值与其上下左右四个像素点的像素值对比,如果相同,则将像素值进行修改(改成newColor
),同时继续调用递归函数dfs()
,直到某像素点上下左右的像素都与原来image[sr,sc]
不同,或者到达像素数组的四个边界。
我的第一次正确提交
/** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). */ void dfs(int** image, int imageSize, int *imageColSize, int x, int y, int color, int newColor) { if(x < 0 || x >= imageSize || y < 0 || y >= imageColSize[0]) return; if(image[x][y] == color) { image[x][y] = newColor; dfs(image, imageSize, imageColSize, x - 1, y, color, newColor); dfs(image, imageSize, imageColSize, x, y - 1, color, newColor); dfs(image, imageSize, imageColSize, x + 1, y, color, newColor); dfs(image, imageSize, imageColSize, x, y + 1, color, newColor); } } int** floodFill(int** image, int imageSize, int* imageColSize, int sr, int sc, int newColor, int* returnSize, int** returnColumnSizes) { if(image[sr][sc] != newColor) { dfs(image, imageSize, imageColSize, sr, sc, image[sr][sc], newColor); } *returnSize = imageSize; *returnColumnSizes = imageColSize; return image; }
官方版本
方法一:广度优先搜索
我们从给定的起点开始,进行广度优先搜索。每次搜索到一个方格时,如果其与初始位置的方格颜色相同,就将该方格加入队列,并将该方格的颜色更新,以防止重复入队。
注意:因为初始位置的颜色会被修改,所以我们需要保存初始位置的颜色,以便于之后的更新操作。
——作者:LeetCode-Solution——链接——来源:力扣(LeetCode)
const int dx[4] = {1, 0, 0, -1}; const int dy[4] = {0, 1, -1, 0}; int** floodFill(int** image, int imageSize, int* imageColSize, int sr, int sc, int newColor, int* returnSize, int** returnColumnSizes) { int n = imageSize, m = imageColSize[0]; *returnSize = n; for (int i = 0; i < n; i++) { (*returnColumnSizes)[i] = m; } int currColor = image[sr][sc]; if (currColor == newColor) return image; int que[n * m][2]; int l = 0, r = 0; que[r][0] = sr, que[r++][1] = sc; image[sr][sc] = newColor; while (l < r) { int x = que[l][0], y = que[l++][1]; for (int i = 0; i < 4; i++) { int mx = x + dx[i], my = y + dy[i]; if (mx >= 0 && mx < n && my >= 0 && my < m && image[mx][my] == currColor) { que[r][0] = mx, que[r++][1] = my; image[mx][my] = newColor; } } } return image; } 作者:LeetCode-Solution 链接:https://leetcode-cn.com/problems/flood-fill/solution/tu-xiang-xuan-ran-by-leetcode-solution/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
复杂度分析
时间复杂度:O(n×m),其中 n 和 m 分别是二维数组的行数和列数。最坏情况下需要遍历所有的方格一次。
空间复杂度:O(n×m),其中 n 和 m 分别是二维数组的行数和列数。主要为队列的开销。
——作者:LeetCode-Solution——链接
方法二:深度优先搜索
我们从给定的起点开始,进行深度优先搜索。每次搜索到一个方格时,如果其与初始位置的方格颜色相同,就将该方格的颜色更新,以防止重复搜索;如果不相同,则进行回溯。
注意:因为初始位置的颜色会被修改,所以我们需要保存初始位置的颜色,以便于之后的更新操作。
——作者:LeetCode-Solution——链接——来源:力扣(LeetCode)
const int dx[4] = {1, 0, 0, -1}; const int dy[4] = {0, 1, -1, 0}; int n, m; void dfs(int** image, int x, int y, int color, int newColor) { if (image[x][y] == color) { image[x][y] = newColor; for (int i = 0; i < 4; i++) { int mx = x + dx[i], my = y + dy[i]; if (mx >= 0 && mx < n && my >= 0 && my < m) { dfs(image, mx, my, color, newColor); } } } } int** floodFill(int** image, int imageSize, int* imageColSize, int sr, int sc, int newColor, int* returnSize, int** returnColumnSizes) { n = imageSize, m = imageColSize[0]; *returnSize = n; for (int i = 0; i < n; i++) { (*returnColumnSizes)[i] = m; } int currColor = image[sr][sc]; if (currColor != newColor) { dfs(image, sr, sc, currColor, newColor); } return image; } 作者:LeetCode-Solution 链接:https://leetcode-cn.com/problems/flood-fill/solution/tu-xiang-xuan-ran-by-leetcode-solution/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
复杂度分析
时间复杂度:O(n×m),其中 n 和 m 分别是二维数组的行数和列数。最坏情况下需要遍历所有的方格一次。
空间复杂度:O(n×m),其中 n 和 m 分别是二维数组的行数和列数。主要为队列的开销。
——作者:LeetCode-Solution——链接
这篇关于算法入门C——733. 图像渲染的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享
- 2024-07-04make后如何升级ssh-icode9专业技术文章分享
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享
- 2024-07-03微信支付提示订单号重复-icode9专业技术文章分享
- 2024-07-02微服务启动nacos注册上去了,但是一直没有收到请求-icode9专业技术文章分享
- 2024-07-02如何检查文件的编码格式-icode9专业技术文章分享
- 2024-07-02sublime 更改编码格式-icode9专业技术文章分享