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

floodfill算法题目

前言

大家好,我是jiantaoyab,在下面的题目中慢慢体会floodFill算法,虽然是新的算法,但是用的思想和前面的文章几乎一样,代码格式也几乎一样,但不要去背代码

图像渲染

https://leetcode.cn/problems/flood-fill/

解析

image-20240311085056178

代码

可以看到代码这部分,是不是和前面的文章的挺像的

class Solution {int m, n;int pre_color;int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};
public:void dfs(vector<vector<int>>& image, int sr, int sc, int color){image[sr][sc] = color;for(int d = 0; d < 4; d++){int x = sr + dx[d], y = sc + dy[d];if((x >= 0 && x < m) && (y >= 0 && y < n) &&  image[x][y] == pre_color){image[x][y] = color;dfs(image, x, y, color);}}}vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {m = image.size(), n = image[0].size();pre_color = image[sr][sc];if(image[sr][sc] == color) return image;dfs(image, sr, sc, color);return image; }
};

岛屿数量

https://leetcode.cn/problems/number-of-islands/

解析

image-20240311101256605

代码

class Solution {int m, n;vector<vector<bool>> check;int dx[4]= {0, 0, 1, -1};int dy[4]= {1, -1, 0, 0};
public:void dfs(vector<vector<char>>& grid, int i, int j){check[i][j] = true; //从i,j位置来的for(int d = 0; d < 4; d++){int x = i + dx[d], y = j + dy[d];if((x >= 0 && x < m) && (y >= 0 && y < n)  && grid[x][y] == '1' && !check[x][y]){dfs(grid, x, y);}}}int numIslands(vector<vector<char>>& grid) {int m = grid.size(), n = grid[0].size();check = vector<vector<bool>> (m ,vector<bool>(n));int ret = 0;//把整个grid遍历一次for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){//如果是一个岛屿而且是没有出现过的if(grid[i][j] == '1' && !check[i][j]){ret++;dfs(grid, i, j);}}}return ret;}
};

岛屿的最大面积

https://leetcode.cn/problems/ZL6zAn/

解析

大家看这个图就知道题目求的是什么了,比起上一题,多个统计数

image-20240311093330311

代码

class Solution {    int m, n;bool check[51][51];int dx[4] = {1,-1,0,0};int dy[4] = {0, 0,1,-1};int count;
public:void dfs(vector<vector<int>>& grid, int i, int j){count++;check[i][j] = true;for(int d = 0; d < 4; d++){int x = i + dx[d], y = j + dy[d];if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1  && !check[x][y]){dfs(grid, x, y);}}}int maxAreaOfIsland(vector<vector<int>>& grid) {m = grid.size(), n = grid[0].size();int ret = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(!check[i][j] && grid[i][j] == 1){count = 0;dfs(grid, i, j);ret = max(ret, count);}}}return ret;}
};

被围绕的区域

https://leetcode.cn/problems/surrounded-regions/

解析

image-20240311105332642

代码

class Solution {int m, n;int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};
public:void dfs(vector<vector<char>>& board, int i, int j){board[i][j] = 'a';for(int d = 0; d < 4; d++){int x = i + dx[d], y = j + dy[d];if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O'){dfs(board, x, y);}}}void solve(vector<vector<char>>& board) {m = board.size(), n = board[0].size();//把左右2列边界处理了for(int i = 0; i < m; i++){if(board[i][0] == 'O') dfs(board, i, 0);if(board[i][n-1] == 'O') dfs(board, i, n-1);}//把上下2行边界处理了for(int j = 0; j < n; j++){if(board[0][j] == 'O') dfs(board, 0, j);if(board[m-1][j] == 'O') dfs(board, m-1, j);}//还原 + 修改for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(board[i][j] == 'a') board[i][j] = 'O';else if(board[i][j] == 'O') board[i][j] = 'X';}}}
};

太平洋大西洋水流问题

https://leetcode.cn/problems/pacific-atlantic-water-flow/

解析

image-20240311172851034

代码

class Solution {int m, n;int dx[4] = {1, -1, 0, 0};int dy[4] = {0,  0, 1, -1};
public:void dfs(vector<vector<int>>& heights, int i, int j, vector<vector<bool>>&check){check[i][j] = true;for(int d = 0; d < 4; d++){int x = i + dx[d], y = j + dy[d];if(x >= 0 && x < m && y >= 0 && y < n &&  !check[x][y] &&heights[x][y] >= heights[i][j] ){dfs(heights, x, y, check);}}}vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {m = heights.size(), n = heights[0].size();vector<vector<bool>> pac(m, vector<bool>(n));vector<vector<bool>> atl(m, vector<bool>(n));//处理pacfor(int j = 0; j < n; j++) dfs(heights, 0, j, pac);for(int i = 0; i < m; i++) dfs(heights, i, 0, pac);//处理altfor(int j = 0; j < n; j++) dfs(heights, m - 1, j, atl);for(int i = 0; i < m; i++) dfs(heights, i, n - 1, atl);vector<vector<int>> ret;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(pac[i][j] && atl[i][j])ret.push_back({i, j});}}return ret;}
};

扫雷游戏

https://leetcode.cn/problems/minesweeper/

解析

image-20240311180338853

代码

class Solution {int dx[8] = {0, 0, -1, 1, 1, 1, -1 ,-1};int dy[8] = {1, -1, 0, 0, 1, -1, 1 ,-1};int m, n;
public:void dfs(vector<vector<char>>& board, int i, int j){int count = 0; //地雷个数//统计地雷个数for(int d = 0; d < 8; d++){int x = i + dx[d], y = j + dy[d];if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M'){count++;}}//周围有地雷if(count){board[i][j] = count + '0';return ;}//周围没地雷展开else{board[i][j] = 'B';for(int d = 0; d < 8; d++){int x = i + dx[d], y = j + dy[d];if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E'){dfs(board, x, y);}}}}vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {m = board.size(), n = board[0].size();int x = click[0], y = click[1];//开局中地雷if(board[x][y] == 'M'){board[x][y] = 'X';return board;}dfs(board, x, y);return board;}
};

相关文章:

floodfill算法题目

前言 大家好&#xff0c;我是jiantaoyab&#xff0c;在下面的题目中慢慢体会floodFill算法&#xff0c;虽然是新的算法&#xff0c;但是用的思想和前面的文章几乎一样&#xff0c;代码格式也几乎一样&#xff0c;但不要去背代码 图像渲染 https://leetcode.cn/problems/flood…...

AI相关的实用工具分享

AI实用工具大赏&#xff1a;赋能科研与生活&#xff0c;探索AI的无限可能 前言 在数字化浪潮汹涌而至的今天&#xff0c;人工智能&#xff08;AI&#xff09;已经渗透到我们生活的方方面面&#xff0c;无论是工作还是生活&#xff0c;都在悄然发生改变。AI的崛起不仅为我们带…...

K8s — PVC|PV Terminating State

在本文中&#xff0c;我们将讨论PV和PVC一直Terminating的状态。 何时会Terminting? 在以下情况下&#xff0c;资源将处于Terminating状态。 在删除Bounded 状态的PVC之前&#xff0c;删除了对应的PV&#xff0c;PV在删除后是Terminting状态。删除PVC时&#xff0c;仍有引用…...

C语言 --- 指针(5)

目录 一.sizeof和strlen对比 1.sizeof 2.strlen 3.strlen 和sizeof的对比 二.数组和指针笔试题目详解 回顾&#xff1a;数组名的理解 1.一维数组 2.字符数组 代码1&#xff1a; 代码2&#xff1a; 代码3&#xff1a; 代码4&#xff1a; 代码5&#xff1a; 代码6&am…...

Android Studio Iguana | 2023.2.1版本

Android Gradle 插件和 Android Studio 兼容性 Android Studio 构建系统基于 Gradle&#xff0c;并且 Android Gradle 插件 (AGP) 添加了一些特定于构建 Android 应用程序的功能。下表列出了每个版本的 Android Studio 所需的 AGP 版本。 如果特定版本的 Android Studio 不支持…...

并查集(蓝桥杯 C++ 题目 代码 注解)

目录 介绍&#xff1a; 模板&#xff1a; 题目一&#xff08;合根植物&#xff09;&#xff1a; 代码&#xff1a; 题目二&#xff08;蓝桥幼儿园&#xff09;&#xff1a; 代码&#xff1a; 题目三&#xff08;小猪存钱罐&#xff09;&#xff1a; 代码&#xff1a; …...

MapReduce内存参数自动推断

MapReduce内存参数自动推断。在Hadoop 2.0中&#xff0c;为MapReduce作业设置内存参数非常繁琐&#xff0c;涉及到两个参数&#xff1a;mapreduce.{map,reduce}.memory.mb和mapreduce.{map,reduce}.java.opts&#xff0c;一旦设置不合理&#xff0c;则会使得内存资源浪费严重&a…...

pyside6 pytq PyDracula QVideoWidget视频只有画面没有声音

解决方案&#xff1a; 先不使用框架&#xff0c;纯pyside6代码&#xff0c;如果添加视频有画面有声音&#xff0c;那可以排除是硬件问题&#xff0c;如果没有画面只有声音&#xff0c;可能是视频解码器无法解码&#xff0c;换个格式的视频文件如果只有使用PyDracula 出问题&am…...

Axure基础 各元件的作用及介绍

图像热区 增加按钮或者文本的点击区域&#xff0c;他是透明的&#xff0c;在预览时看不见。 动态面板 用来绘制一下带交互效果的元件&#xff0c;他是动态的&#xff0c;如轮播图&#xff0c;一个动态面板里可以有多个子面板&#xff0c;每一个子面板对应着不同的效果。 他…...

学习Java的第六天

目录 一、变量 1、变量的定义 2、变量的声明格式 3、变量的注意事项 4、变量的作用域 二、常量 三、命名规范 Java 语言支持如下运算符&#xff1a; 1、算术运算符 解析图&#xff1a; 示例&#xff1a; 2、赋值运算符 解析图&#xff1a; 示例&#xff1a; 3、关…...

基于Spring Boot+ Vue的房屋租赁系统

末尾获取源码作者介绍&#xff1a;大家好&#xff0c;我是墨韵&#xff0c;本人4年开发经验&#xff0c;专注定制项目开发 更多项目&#xff1a;CSDN主页YAML墨韵 学如逆水行舟&#xff0c;不进则退。学习如赶路&#xff0c;不能慢一步。 目录 一、项目简介 二、开发技术与环…...

多轨迹建模方法的介绍与实操-基于R语言

本文介绍了多轨迹建模方法&#xff08;Group-Based Multivariate Trajectory Modeling&#xff09;&#xff0c;这是一种扩展了单指标组基轨迹建模的技术&#xff0c;用于分析多个疾病生物标志物或临床重要因素的联合轨迹&#xff0c;以更好地理解和追踪疾病进程、行为或健康状…...

【Spring】Spring状态机

1.什么是状态机 (1). 什么是状态 先来解释什么是“状态”&#xff08; State &#xff09;。现实事物是有不同状态的&#xff0c;例如一个自动门&#xff0c;就有 open 和 closed 两种状态。我们通常所说的状态机是有限状态机&#xff0c;也就是被描述的事物的状态的数量是有…...

Node.js基础---使用Express写接口

1. 创建基本的服务器 2. 创建 API 路由模块 // aoiRouter.js 路由模块 const express require(express) const apiRouter express.Router()module.exports apiRouter// ------------------------------------------// app.js 导入并注册路由模块 const apiRouter require(…...

小蓝的钥匙(蓝桥杯错排)

现在有28个小朋友&#xff0c;每个人手上有一把钥匙&#xff0c;每一个钥匙都只能打开自己的房间门&#xff0c;现在将所有钥匙都收上来&#xff0c;然后再随机打乱分给每个小朋友&#xff0c;也就是有28&#xff01;的分法&#xff0c;请问现在其中14个小朋友的钥匙能恰好打开…...

【Python】科研代码学习:八 FineTune PretrainedModel (用 trainer,用 script);LLM文本生成

【Python】科研代码学习&#xff1a;八 FineTune PretrainedModel [用 trainer&#xff0c;用 script] LLM文本生成 自己整理的 HF 库的核心关系图用 trainer 来微调一个预训练模型用 script 来做训练任务使用 LLM 做生成任务可能犯的错误&#xff0c;以及解决措施 自己整理的 …...

SpringBoot RestTemplate远程调用总结

1、get请求 GetMapping("/searchEntryRecordPageList") public JSONObject searchEntryRecordPageList(RequestParam Map<String,Object> params){HttpHeaders requestHeaders new HttpHeaders();requestHeaders.add("Authorization","Bearer…...

Python 强大邮件处理库 Imbox

目录 IMAP Mailbox Imbox 安装 特性 提取邮件内容 处理附件 安全性 示例 1&#xff1a;读取收件箱中的邮件 2&#xff1a;搜索并下载附件 3&#xff1a;连接到IMAP服务器获取所有邮件 结论 IMAP Mailbox IMAP&#xff08;Internet Message Access Protocol&#x…...

ElasticSearch深度分页问题如何解决

文章目录 概述解决方法深度分页方式from size深度分页之scrollsearch_after 三种分页方式比较 概述 Elasticsearch 的深度分页问题是指在大数据集上进行大量分页查询时可能导致的性能下降和资源消耗增加的情况。这种情况通常发生在需要访问大量数据的情形下&#xff0c;比如用…...

景安空间不支持指定运行目录tp5

/WEB/public/.htaccess配置 <IfModule mod_rewrite.c> Options FollowSymlinks -Multiviews RewriteEngine on RewriteCond %{REQUEST_FILENAME} !-d RewriteCond %{REQUEST_FILENAME} !-f RewriteRule ^(.*)$ index.php?s$1 [QSA,PT,L] </IfModule>. 2./WEB/.ht…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...