leetcode原题:颜色填充(经典的递归问题)

这篇具有很好参考价值的文章主要介绍了leetcode原题:颜色填充(经典的递归问题)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目:

编写函数,实现许多图片编辑软件都支持的「颜色填充」功能。

待填充的图像用二维数组 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,],[2,0,1]]
解释:
初始坐标点位于图像的正中间,坐标 (sr,sc)=(1,1)。
初始坐标点周围区域上所有符合条件的像素点的颜色都被更改成 2。
注意,右下角的像素没有更改为 2,因为它不属于初始坐标点的周围区域。

 解题思路:

1.首先要保存初始颜色值,以便后续判断是否是连续的

2.定义四个方向的偏移量,上下左右

3.分别找四个方向的坐标,将符合条件的进行颜色更新

源代码如下:文章来源地址https://www.toymoban.com/news/detail-664748.html

class Solution {
public:
    const int dx[4] = {1, 0, 0, -1};//分别是上下左右四个方向
    const int dy[4] = {0, 1, -1, 0};
    void dfs(vector<vector<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 < image.size() && my >= 0 && my < image[0].size()) {
                    dfs(image, mx, my, color, newColor);
                }
            }
        }
    }
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        //记录初始颜色值
        int currColor = image[sr][sc];
        //需要更新的颜色不是初始颜色,开始递归
        if (currColor != newColor) {
            dfs(image, sr, sc, currColor, newColor);
        }
        //返回原数组
        return image;
    }
};

这道题还可以用广度优先遍历来实现,借助队列,在队列中通过pair对保存坐标的x,y。

将四个方向中符合条件的坐标入队,再进行更新颜色

源代码如下:

class Solution {
public:
    const int dx[4]={1,0,0,-1};
    const int dy[4]={0,1,-1,0};
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int currColor = image[sr][sc];//保存初始颜色值
        //如果要更新的颜色值与初始值相同,就不用改了,直接返回数组
        if (currColor == newColor) {
            return image;
		}
        //记录图像的行和列
        int n = image.size(), m = image[0].size();
        //在队列中保存的是一个个pair对
        queue<pair<int, int>> que;
        //先将初始值入队
        que.emplace(sr, sc);
        //初始坐标更新颜色
        image[sr][sc] = newColor;
        while (!que.empty()) {
            //取坐标
            int x = que.front().first, y = que.front().second;
            //坐标出队
            que.pop();
            //查找四个方向的坐标是否相连
            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.emplace(mx, my);
                    //更新颜色
                    image[mx][my] = newColor;
                }
            }
        }
        return image;
    }
};

到了这里,关于leetcode原题:颜色填充(经典的递归问题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】之多指针算法经典问题

    本文为 【数据结构与算法】多指针算法经典问题 相关介绍,下边将对 链表反转 (包含 迭代反转链表 、 递归反转 、 头插法反转 ), 双指针-快慢指针 (包含 寻找单向无环链表的中点 、 判断单向链表是否有环及找环入口 ), 双指针-左右指针 (包含 两数之和 、 二分查

    2024年02月03日
    浏览(54)
  • 【数据结构与算法】【约瑟夫问题】还在用递归?教你用链表秒杀约瑟夫

     🎉🎉欢迎光临🎉🎉 🏅我是苏泽,一位对技术充满热情的探索者和分享者。🚀🚀 🌟特别推荐给大家我的最新专栏 《数据结构与算法:初学者入门指南》📘📘 本专栏纯属为爱发电永久免费!!! 这是苏泽的个人主页可以看到我其他的内容哦👇👇 努力的苏泽 http://su

    2024年02月19日
    浏览(37)
  • 数据结构与算法之数组: Leetcode 605. 种花问题 (Typescript版)

    种花问题 https://leetcode.cn/problems/can-place-flowers/ 描述 假设有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花不能种植在相邻的地块上,它们会争夺水源,两者都会死去。 给你一个整数数组 flowerbed 表示花坛,由若干 0 和 1 组成,其中 0 表示没种植花,1 表示

    2024年02月02日
    浏览(44)
  • C语言递归算法实现经典例题

    递归是一种编程技术,它通过在函数内部反复调用自身来解决问题。当一个程序调用自己时,这就称为递归调用。递归可以有助于简化某些算法的实现和理解。在递归过程中,每个调用都会将一些数据保存在栈上,直到递归结束后才能被处理并弹出栈。 递归通常有两个部分:

    2024年02月05日
    浏览(54)
  • leetcode原题: 生存人数

    题目: 给定 N 个人的出生年份和死亡年份,第 i 个人的出生年份为 birth[i] ,死亡年份为 death[i] ,实现一个方法以计算生存人数最多的年份。 你可以假设所有人都出生于 1900 年至 2000 年(含 1900 和 2000 )之间。如果一个人在某一年的任意时期处于生存状态,那么他应该被纳入

    2024年02月10日
    浏览(45)
  • leetcode原题: 峰与谷

    题目: 在一个整数数组中,“峰”是大于或等于相邻整数的元素,相应地,“谷”是小于或等于相邻整数的元素。例如,在数组{5, 8, 4, 2, 3, 4, 6}中,{8, 6}是峰, {5, 2}是谷。现在给定一个整数数组,将该数组按峰与谷的交替顺序排序。 示例: 输入: [5, 3, 1, 2, 3] 输出: [5, 1, 3,

    2024年02月11日
    浏览(53)
  • leetcode原题:变位词组(哈希)

    题目: 编写一种方法,对字符串数组进行排序,将所有变位词组合在一起。变位词是指字母相同,但排列不同的字符串。 示例: 输入: [\\\"eat\\\", \\\"tea\\\", \\\"tan\\\", \\\"ate\\\", \\\"nat\\\", \\\"bat\\\"], 输出: [   [\\\"ate\\\",\\\"eat\\\",\\\"tea\\\"],   [\\\"nat\\\",\\\"tan\\\"],   [\\\"bat\\\"] ] 解题思路: 本题是需要将相同的变位词放在一维数组中,

    2024年02月11日
    浏览(37)
  • leetcode原题:节点间通路

    题目: 给定有向图,设计一个算法,找出两个节点之间是否存在一条路径。 示例:  输入:n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2  输出:true  解题思路: 本题借助队列,利用队列的先进先出的特点,保证访问每个节点的顺序不被破坏。 1. 建立邻接表map ,讲

    2024年02月13日
    浏览(50)
  • leetcode原题:绘制直线(位运算)

    题目: 已知一个由像素点组成的单色屏幕,每行均有 w 个像素点,所有像素点初始为 0 ,左上角位置为 (0,0) 。 现将每行的像素点按照「每 32 个像素点」为一组存放在一个 int 中,再依次存入长度为 length 的一维数组中。 我们将在屏幕上绘制一条从点 (x1,y) 到点 (x2,y) 的直线(

    2024年02月12日
    浏览(37)
  • 算法 数据结构 递归插入排序 java插入排序 递归求解插入排序算法 如何用递归写插入排序 插入排序动图 插入排序优化 数据结构(十)

    1. 插入排序(insertion-sort):                                           是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入     算法稳定性:                  

    2024年02月09日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包