当前位置: 首页 > news >正文

【广度优先搜索】图像渲染 岛屿数量

文章目录

  • 733. 图像渲染
  • 解题思路:BFS
  • 200. 岛屿数量
  • 解题思路:广度优先遍历

在这里插入图片描述

733. 图像渲染

733. 图像渲染

​ 有一幅以 m x n 的二维整数数组表示的图画 image ,其中 image[i][j] 表示该图画的像素值大小。

​ 你也被给予三个整数 sr , scnewColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充

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

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

示例 1:

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

示例 2:

输入: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2
输出: [[2,2,2],[2,2,2]]

提示:

  • m == image.length
  • n == image[i].length
  • 1 <= m, n <= 50
  • 0 <= image[i][j], newColor < 216
  • 0 <= sr < m
  • 0 <= sc < n

解题思路:BFS

​ 这道题我们在学搜索算法的时候就接触到了,当时说可以使用 dfs 以及 bfs 方法来解决,现在我们就用 bfs 方法来解决它,并且这里对于 floodfill 算法以及这道题的思路就不再解释了,具体可以参考递归专题的笔记,但我相信这道题并不难理解!

​ 其实 bfs 非常简单,就是利用 队列 来实现这个过程!首先将起点位置放到队列中,然后进行循环,直到队列为空则停下来,而在循环过程中,将队头元素取出然后进行修改颜色,然后将对头元素邻近元素也就是上下左右四个元素,根据题目要求将符合的元素加入队列中,达到 bfs 效果!

​ 剩下的就没什么好说的了,具体参考下面代码:

class Solution {
private:int dx[4] = { 0, 0, 1, -1 };int dy[4] = { -1, 1, 0, 0 };
public:vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newcolor) {// 1. 因为我们没使用used数组,所以需要先处理一下边界问题,防止死循环int oldcolor = image[sr][sc];if(oldcolor == newcolor)return image;// 2. 将起点放到队列中queue<pair<int, int>> bfs;bfs.push({sr, sc});while(!bfs.empty()){// 3. 将队头元素取出然后进行修改颜色auto [x, y] = bfs.front();bfs.pop();image[x][y] = newcolor;// 4. 将对头元素邻近元素根据要求加入队列中,达到bfs效果for(int i = 0; i < 4; ++i){int newx = x + dx[i], newy = y + dy[i];if(newx >= 0 && newy >= 0 && newx < image.size() && newy < image[newx].size() && image[newx][newy] == oldcolor)bfs.push({newx, newy});}}return image;}
};

在这里插入图片描述

200. 岛屿数量

200. 岛屿数量

​ 给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。

​ 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

​ 此外,你可以假设该网格的四条边均被水包围。

示例 1:

输入:grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]
]
输出:1

示例 2:

输入:grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]
]
输出:3

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] 的值为 '0''1'

解题思路:广度优先遍历

​ 这道题具体思路可以参考递归专题中的笔记,这里不再赘述!

​ 使用 bfs 来解决问题,其实思路都是一样的,以每个元素为起点找寻所有的岛屿,并且记录数量,当遇到 1 的时候,则将记录数量增加,然后进行广度优先遍历,将 1 修改为 0。然后继续遍历二维数组直到岛屿都找到了为止!

​ 这里我们采用的修改方式是直接修改原数组,如果不直接修改原数组也是可以的,就得用一个 used 数组来判断是否走过,都是一样的套路,这里就不演示了!

​ 此外,我们将 {i, j} 邻近的符合要求的节点添加到队列中时,就要将其从 1 改为 0,这样子可以减少许多不必要的重复遍历操作,并且不这么做的话,这道题也是会超时的!

class Solution {
private:int dx[4] = { 0, 0, 1, -1 };int dy[4] = { -1, 1, 0, 0 };
public:int numIslands(vector<vector<char>>& grid) {// 以每个元素为起点找寻所有的岛屿,并且记录数量int ret = 0;for(int i = 0; i < grid.size(); ++i){for(int j = 0; j < grid[i].size(); ++j){if(grid[i][j] == '1'){ret++;bfs(grid, i, j); // 进行广度优先遍历,将'1'修改为'0'}}}return ret;}void bfs(vector<vector<char>>& grid, int i, int j){queue<pair<int, int>> qe;qe.push({i, j});grid[i][j] = '0';while(!qe.empty()){auto [x, y] = qe.front();qe.pop();for(int k = 0; k < 4; ++k){int newx = x + dx[k], newy = y + dy[k];if(newx >= 0 && newy >= 0 && newx < grid.size() && newy < grid[newx].size() && grid[newx][newy] == '1'){qe.push({newx, newy});grid[newx][newy] = '0'; // 提前将邻近节点改为'0',可以减少许多不必要的重复}}}}
};

在这里插入图片描述

相关文章:

【广度优先搜索】图像渲染 岛屿数量

文章目录 733. 图像渲染解题思路&#xff1a;BFS200. 岛屿数量解题思路&#xff1a;广度优先遍历 733. 图像渲染 733. 图像渲染 ​ 有一幅以 m x n 的二维整数数组表示的图画 image &#xff0c;其中 image[i][j] 表示该图画的像素值大小。 ​ 你也被给予三个整数 sr , sc 和…...

Rust学习总结之-枚举

枚举是一个很多语言都有的功能&#xff0c;不过不同语言中其功能各不相同但是要表达的意思是一致的&#xff0c;枚举就是对于一个事物可以穷举出所有可能得值。比如说人的性别就可以用枚举&#xff0c;男人和女人两种。下面我们来学习Rust中的枚举。 一&#xff1a;枚举定义 …...

Linux下用route命令修改默认网关,不用重启网络

在Linux系统中&#xff0c;可以使用route命令来修改默认网关&#xff0c;而不需要重启网络。 下面是使用route命令修改默认网关的步骤&#xff1a; 打开终端窗口&#xff0c;以root用户或拥有sudo权限的用户身份登录。 使用以下命令查看当前的路由表信息&#xff1a; route…...

Datawhale 数学建模导论二 笔记5 多模数据与智能模型

主要涉及到的知识点有&#xff1a; 数字图像处理与计算机视觉 计算语言学与自然语言处理 数字信号处理与智能感知 10.1 数字图像处理与计算机视觉 视觉信息是我们第一种非常规的数据模式&#xff0c;在Python当中可以使用opencv处理数字图像&#xff0c;并提取出视觉特征用…...

【练习】【贪心】力扣1005. K 次取反后最大化的数组和

题目 1005 K 次取反后最大化的数组和 给你一个整数数组 nums 和一个整数 k &#xff0c;按以下方法修改该数组&#xff1a; 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。 以这种方式修改数组后&#xff0c;返回数组 可…...

python学习七

作用域&#xff1a; 在编程语言中定义变量的可见性和生命周期的规则集合。它决定了在程序中的哪些位置可以访问或引用某个变量 1.全局作用域&#xff1a; 全局作用域是指在整个程序中都可见的变量。在函数外 部定义的变量通常具有全局作用域&#xff0c;在任何地方都可以访问和…...

安全运营的“黄金4小时“:如何突破告警疲劳困局

在当今复杂多变的网络安全环境中&#xff0c;安全团队面临着前所未有的挑战。尤其是面对高级持续性威胁&#xff08;APT&#xff09;时&#xff0c;最初的“黄金4小时”成为决定成败的关键窗口。在这段时间内&#xff0c;快速而准确地响应可以极大地降低损失&#xff0c;然而&a…...

本地部署Embedding模型API服务的实战教程

大家好,我是herosunly。985院校硕士毕业,现担任算法研究员一职,热衷于大模型算法的研究与应用。曾担任百度千帆大模型比赛、BPAA算法大赛评委,编写微软OpenAI考试认证指导手册。曾获得阿里云天池比赛第一名,CCF比赛第二名,科大讯飞比赛第三名。授权多项发明专利。对机器学…...

数据结构:二叉树的链式结构及相关算法详解

目录 一.链式结构的实现 1.二叉树结点基本结构&#xff0c;初始化与销毁&#xff1a; 二.链式结构二叉树的几种遍历算法 1.几种算法的简单区分&#xff1a; 2.前序遍历&#xff1a; 3.中序遍历&#xff1a; 4.后序遍历&#xff1a; 5.层序遍历&#xff08;广度优先遍历B…...

10.【线性代数】—— 四个基本子空间

十、 四个基本子空间 1. 列空间 C ( A ) C(A) C(A) in R m R^m Rm2. 零空间 N ( A ) N(A) N(A) in R n R^n Rn3. 行空间 C ( A T ) C(A^T) C(AT) in R n R^n Rn4. 左零空间 N ( A T ) N(A^T) N(AT) in R m R^m Rm综述5. 新的向量空间 讨论矩阵 A m ∗ n A_{m*n} Am∗n​…...

计算机黑皮书191本分享pdf

“黑皮书”通常指的是由机械工业出版社出版的计算机科学丛书。这些书籍的封面通常是黑色的&#xff0c;因此得名“黑皮书”。这些书籍涵盖了计算机科学的各个领域&#xff0c;包括操作系统、计算机网络、软件工程、编译原理、数据库等。 获取链接&#xff1a;链接:https://pan…...

MySQL Connector/J下载

MySQL Connector/J下载 下载mysql驱动jar包。 官网&#xff1a;https://downloads.mysql.com/archives/c-j/ 我下载的是8.0.33&#xff0c;下载的时候要注意与MySQL的版本对应。...

AIGC生图产品PM必须知道的Lora训练知识!

hihi&#xff0c;其实以前在方向AIGC生图技术原理和常见应用里面已经多次提到Lora的概念了&#xff0c;但是没有单独拿出来讲过&#xff0c;今天就耐心来一下&#xff01; &#x1f525; 一口气摸透AIGC文生图产品SD&#xff08;Stable Diffusion&#xff09;&#xff01; 一、…...

【Swift 算法实战】城市天际线问题解法

网罗开发 &#xff08;小红书、快手、视频号同名&#xff09; 大家好&#xff0c;我是 展菲&#xff0c;目前在上市企业从事人工智能项目研发管理工作&#xff0c;平时热衷于分享各种编程领域的软硬技能知识以及前沿技术&#xff0c;包括iOS、前端、Harmony OS、Java、Python等…...

易错点abc

在同一个输入流上重复创建Scanner实例可能会导致一些问题&#xff0c;包括但不限于输入流的混乱。尤其是在处理标准输入&#xff08;System.in&#xff09;时&#xff0c;重复创建Scanner对象通常不是最佳实践&#xff0c;因为这可能导致某些输入数据丢失或者顺序出错。 为什么…...

C++ 正则表达式分组捕获入门指南

在 C 中&#xff0c;正则表达式&#xff08;regex&#xff09;是一种用于匹配字符串模式的强大工具。正则表达式不仅能帮助你查找符合特定模式的字符&#xff0c;还能捕获匹配的子字符串&#xff08;即分组捕获&#xff09;。这篇文章将介绍 C 正则表达式中的分组捕获机制&…...

AI人工智能机器学习之降维和数据压缩

1、概要 本篇学习AI人工智能机器学习之降维和数据压缩&#xff0c;以主成分分析&#xff08;PCA, Principal Component Analysis&#xff09;为例&#xff0c;从代码层面讲述机器学习中的降维和数据压缩。 2、降维和数据压缩 - 简介 在机器学习和数据分析中&#xff0c;降维&…...

17 款电脑压缩工具详解及下载指南(2025 年最新版)

在数字时代,文件压缩是日常工作与生活中不可或缺的操作。无论是视频剪辑师压缩视频以便上传,还是普通用户节省存储空间,一款优质的压缩软件都能极大提升效率。本文将详细介绍 17 款热门电脑压缩软件,涵盖它们的特点、下载地址及适用场景,助你找到最适合自己的工具。 一、…...

DeepSeek开源周Day5压轴登场:3FS与Smallpond,能否终结AI数据瓶颈之争?

2025年2月28日&#xff0c;DeepSeek开源周迎来了第五天&#xff0c;也是本次活动的收官之日。自2月24日启动以来&#xff0c;DeepSeek团队以每天一个开源项目的节奏&#xff0c;陆续向全球开发者展示了他们在人工智能基础设施领域的最新成果。今天&#xff0c;他们发布了Fire-F…...

ROS2软件调用架构和机制解析:Publisher创建

术语 DDS (Data Distribution Service): 用于实时系统的数据分发服务标准&#xff0c;是ROS 2底层通信的基础RMW (ROS Middleware): ROS中间件接口&#xff0c;提供与具体DDS实现无关的抽象APIQoS (Quality of Service): 服务质量策略&#xff0c;控制通信的可靠性、历史记录、…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

Kafka主题运维全指南:从基础配置到故障处理

#作者&#xff1a;张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1&#xff1a;主题删除失败。常见错误2&#xff1a;__consumer_offsets占用太多的磁盘。 主题日常管理 …...