leetcode733-图像渲染

原题

有一幅以二维整数数组表示的图画,每一个整数表示该图画的像素值大小,数值在 0 到 65535 之间。

给你一个坐标 (sr, sc) 表示图像渲染开始的像素值(行 ,列)和一个新的颜色值 newColor,让你重新上色这幅图像。

为了完成上色工作,从初始坐标开始,记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点,接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点,……,重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。

最后返回经过上色渲染后的图像。

示例1:

输入:
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,
因为它不是在上下左右四个方向上与初始点相连的像素点。

注意:

  • image 和 image[0] 的长度在范围 [1, 50] 内。
  • 给出的初始点将满足 0 <= sr < image.length 和 0 <= sc < image[0].length。
  • image[i][j] 和 newColor 表示的颜色值在范围 [0, 65535]内。

解法

思想

图的BFS

对应示例

代码

class Solution {
    class Point{
        public int x;
        public int y;
        public Point(int x,int y){
            this.x = x;
            this.y = y;
        }
    } 

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(sr,sc));
        int origin = image[sr][sc];
        int height = image.length;
        int width = image[0].length;
        if(newColor == origin) return image;

        while(!queue.isEmpty()){
            Point point = queue.poll();
            image[point.x][point.y] = newColor;
            if(point.x!=height-1 && image[point.x+1][point.y] == origin){
                queue.offer(new Point(point.x+1,point.y));
            }
            if(point.x!=0 && image[point.x-1][point.y] == origin){
                queue.offer(new Point(point.x-1,point.y));
            }
            if(point.y!=width-1 && image[point.x][point.y+1] == origin){
                queue.offer(new Point(point.x,point.y+1));
            }
            if(point.y!= 0&& image[point.x][point.y-1] == origin){
                queue.offer(new Point(point.x,point.y-1));
            }
        }
        return image;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode733-%e5%9b%be%e5%83%8f%e6%b8%b2%e6%9f%93/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年12月12日
下一篇 2019年12月14日

相关推荐

  • leetcode443-压缩字符串

    原题 给定一组字符,使用原地算法将其压缩。 压缩后的长度必须始终小于或等于原数组长度。 数组的每个元素应该是长度为1 的字符(不是 int 整数类型)。 在完成原地修改输入数组后,…

    算法 2020年5月28日
    070
  • leetcode1144-递减元素使数组呈锯齿状

    原题 给你一个整数数组 nums,每次 操作 会从中选择一个元素并 将该元素的值减少 1。 如果符合下列情况之一,则数组 A 就是 锯齿数组: 每个偶数索引对应的元素都大于相邻的元…

    算法 2020年6月5日
    050
  • leetcode622-设计循环队列

    设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是…

    算法 2019年11月24日
    0130
  • 海量数据-两种方法解决top k问题

    假如提供一百万个数据(甚至更大)的无序数组,如何从中获取最大的k个元素? 最容易想到的是先降序排序然后获取前k个元素,那假设我们用最常用的O(nlogn)级别的排序算法,要获取to…

    2020年4月4日
    0200
  • leetcode106-从中序与后序遍历序列构造二叉树

    原题 根据一棵树的中序遍历与后序遍历构造二叉树。 注意:你可以假设树中没有重复的元素。 例如,给出 中序遍历 inorder = [9,3,15,20,7] 后序遍历 postor…

    算法 2020年1月13日
    0380
  • leetcode350-两个数组的交集II

    原题 给定两个数组,编写一个函数来计算它们的交集。 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2,2] 示例2: 输入: nums1 = …

    算法 2019年12月23日
    0390
  • leetcode53-最大子序和

    原题 原题 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4],…

    算法 2020年2月20日
    0120
  • leetcode561-数组拆分I

    原题 给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ,使得从1 到 n 的 min(ai, b…

    算法 2019年11月18日
    080
  • 剑指offer17-打印从1到最大的n位数

    原题(来源Leetcode) 输入数字 n,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数 999。 示例 1: 输入: …

    算法 2020年4月17日
    080
  • leetcode110-平衡二叉树

    原题 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1:  给定二叉树 […

    算法 2020年1月17日
    0170

发表回复

登录后才能评论