力扣(Leetcode)733. 图像渲染(Java)带注释

2024-02-10 17:58

本文主要是介绍力扣(Leetcode)733. 图像渲染(Java)带注释,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.题目描述

官方链接733.图像渲染。以下是复制内容。
有一幅以二维整数数组表示的图画,每一个整数表示该图画的像素值大小,数值在 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]内。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/flood-fill
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2.个人题目理解

起初我也没看懂题目的意思,通过代码理解了。

官方题解是这样子讲的

本题要求将给定的二维数组中指定的「色块」染成另一种颜色。「色块」的定义是:直接或间接相邻的同色方格构成的整体。

可以发现,「色块」就是被不同颜色的方格包围的一个同色岛屿。我们从色块中任意一个地方开始,利用广度优先搜索或深度优先搜索即可遍历整个岛屿。

注意:当目标颜色和初始颜色相同时,我们无需对原数组进行修改。

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/flood-fill/solution/tu-xiang-xuan-ran-by-leetcode-solution/
来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

我的理解

我的理解就是从source点开始,将source点所在的currentColour色块换成newColour,就像围棋一样。

3.解法

1.BFS(广度优先搜索)

思路及算法
BFS需要一个队列管理source点所在色块的所有点,通过队列来实现对这些点的颜色的更改与遍历。

首先从source点开始,进行上下左右的搜索,如果其中某个点与currentColour颜色相同,则加入队列以便继续搜索,同时将这个点的颜色更改为newColour。如果队列为空了,则说明所有的currentColour的点颜色都改为了newColour。

对Java中队列不太理解的可以看另一篇Java中队列(Queue)用法

下面是官方题解的代码,我加上了注释。

class Solution {int[]dx = {1,0,0,-1};//控制点的左右移动int[]dy = {0,1,-1,0};//控制点的上下移动public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {int currentColour = image[sr][sc];//获得source的颜色if(currentColour == newColor){return image;}int n = image.length,m = image[0].length;//获得二维数组的长和宽Queue<int[]> queue = new LinkedList<int[]>();//新建二维的队列记录更改颜色的点queue.offer(new int[]{sr,sc});//将初始点先放进去image[sr][sc] = newColor;//更改初始点的颜色while(!queue.isEmpty()){int[]cell = queue.poll();int x = cell[0],y=cell[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]==currentColour){//判断该点是否需要改颜色queue.offer(new int[]{mx,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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

2.DFS(深度优先搜索)

dfs简单很多,主要是递归,一直往下去就行了。

代码如下

class Solution {int[]dx = {1,0,0,-1};//控制点的左右移动int[]dy = {0,1,-1,0};//控制点的上下移动public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {int currentColour = image[sr][sc];//获得source的颜色if(currentColour != newColor){//判断是否需要改颜色dfs(image,sr,sc,currentColour,newColor);}return image;}private void dfs(int[][]image,int x,int y,int colour,int newColour){if(image[x][y]==colour){image[x][y]=newColour;//更改该点颜色for(int i = 0;i<4;i++){int mx = x+dx[i],my= y+dy[i];//获得上下左右四个点if(mx >=0&&mx<image.length&&my>=0&&my<image[0].length&&image[mx][my]==colour){//判断该点是否需要改颜色dfs(image,mx,my,colour,newColour);//继续下一个递归}}}}
}作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/flood-fill/solution/tu-xiang-xuan-ran-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

这篇关于力扣(Leetcode)733. 图像渲染(Java)带注释的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/697735

相关文章

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控

Java中读取YAML文件配置信息常见问题及解决方法

《Java中读取YAML文件配置信息常见问题及解决方法》:本文主要介绍Java中读取YAML文件配置信息常见问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要... 目录1 使用Spring Boot的@ConfigurationProperties2. 使用@Valu

创建Java keystore文件的完整指南及详细步骤

《创建Javakeystore文件的完整指南及详细步骤》本文详解Java中keystore的创建与配置,涵盖私钥管理、自签名与CA证书生成、SSL/TLS应用,强调安全存储及验证机制,确保通信加密和... 目录1. 秘密键(私钥)的理解与管理私钥的定义与重要性私钥的管理策略私钥的生成与存储2. 证书的创建与

浅析Spring如何控制Bean的加载顺序

《浅析Spring如何控制Bean的加载顺序》在大多数情况下,我们不需要手动控制Bean的加载顺序,因为Spring的IoC容器足够智能,但在某些特殊场景下,这种隐式的依赖关系可能不存在,下面我们就来... 目录核心原则:依赖驱动加载手动控制 Bean 加载顺序的方法方法 1:使用@DependsOn(最直

SpringBoot中如何使用Assert进行断言校验

《SpringBoot中如何使用Assert进行断言校验》Java提供了内置的assert机制,而Spring框架也提供了更强大的Assert工具类来帮助开发者进行参数校验和状态检查,下... 目录前言一、Java 原生assert简介1.1 使用方式1.2 示例代码1.3 优缺点分析二、Spring Fr

java使用protobuf-maven-plugin的插件编译proto文件详解

《java使用protobuf-maven-plugin的插件编译proto文件详解》:本文主要介绍java使用protobuf-maven-plugin的插件编译proto文件,具有很好的参考价... 目录protobuf文件作为数据传输和存储的协议主要介绍在Java使用maven编译proto文件的插件

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

Javaee多线程之进程和线程之间的区别和联系(最新整理)

《Javaee多线程之进程和线程之间的区别和联系(最新整理)》进程是资源分配单位,线程是调度执行单位,共享资源更高效,创建线程五种方式:继承Thread、Runnable接口、匿名类、lambda,r... 目录进程和线程进程线程进程和线程的区别创建线程的五种写法继承Thread,重写run实现Runnab

Java 方法重载Overload常见误区及注意事项

《Java方法重载Overload常见误区及注意事项》Java方法重载允许同一类中同名方法通过参数类型、数量、顺序差异实现功能扩展,提升代码灵活性,核心条件为参数列表不同,不涉及返回类型、访问修饰符... 目录Java 方法重载(Overload)详解一、方法重载的核心条件二、构成方法重载的具体情况三、不构

Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式

《Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式》本文详细介绍如何使用Java通过JDBC连接MySQL数据库,包括下载驱动、配置Eclipse环境、检测数据库连接等关键步骤,... 目录一、下载驱动包二、放jar包三、检测数据库连接JavaJava 如何使用 JDBC 连接 mys