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日

相关推荐

  • leetcode111-二叉树的最小深度

    原题 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,nul…

    算法 2020年3月25日
    0210
  • leetcode55-跳跃游戏

    原题 原题 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例1: 输入: [2,3,1…

    算法 2020年2月9日
    060
  • leetcode203-移除链表元素

    原题 删除链表中等于给定值 val 的所有节点。 示例: 输入: 1->2->6->3->4->5->6, val = 6 输出: 1->2->3->4->5 解法 思想 pre指…

    算法 2019年12月16日
    0360
  • leetcode5-最长回文子串

    原题 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例1: 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有…

    算法 2020年2月20日
    0110
  • leetcode66-加一

    原题 给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。 最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外,这个整数不会以…

    算法 2019年11月14日
    0140
  • leetcode453-最小移动次数使数组元素相等

    原题 给定一个长度为 n 的非空整数数组,找到让数组所有元素相等的最小移动次数。每次移动将会使 n - 1 个元素增加 1。 示例: 输入: [1,2,3] 输出: 3 解释: 只…

    算法 2020年6月7日
    0120
  • leetcode141-环形链表

    原题 给定一个链表,判断链表中是否有环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没…

    2019年12月14日
    090
  • leetcode234-回文链表

    原题 请判断一个链表是否为回文链表。 示例1: 输入: 1->2 输出: false 示例2: 输入: 1->2->2->1 输出: true 进阶: 你能否用 O(n) 时间复杂…

    2019年12月16日
    0100
  • leetcode38-外观数列

    原题 「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。前五项如下: 1. 1 2. 11 3. 21 4. 1211 5. 111221 1 被读作…

    算法 2020年4月30日
    0290
  • leetcode57-插入区间

    原题 给出一个无重叠的 ,按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 示例 1: 输入: …

    算法 2020年5月12日
    0270

发表回复

登录后才能评论