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

【每日刷题】Day143

【每日刷题】Day143

🥕个人主页:开敲🍉

🔥所属专栏:每日刷题🍍

🌼文章目录🌼

1. 200. 岛屿数量 - 力扣(LeetCode)

2. LCR 105. 岛屿的最大面积 - 力扣(LeetCode)

3. 130. 被围绕的区域 - 力扣(LeetCode)

1. 200. 岛屿数量 - 力扣(LeetCode)

//思路:floodfill算法+哈希

class Solution {

public:

    int ans = 0;

    void dfs(vector<vector<char>>& grid,int i,int j,vector<vector<bool>>& hash)

    {

        if(i>=grid.size()||i<0||j>=grid[0].size()||j<0||grid[i][j]=='0')//回溯:越界 || 当前位置为字符 '0'

            return;

       

        hash[i][j] = true;//每访问一个 ‘1’ ,将该位置设为 "已访问"

//上、下、左、右递归

        if(i-1>=0&&!hash[i-1][j])

            dfs(grid,i-1,j,hash);

        if(i+1<=grid.size()&&!hash[i+1][j])

            dfs(grid,i+1,j,hash);

        if(j-1>=0&&!hash[i][j-1])

            dfs(grid,i,j-1,hash);

        if(j+1<=grid[0].size()&&!hash[i][j+1])

            dfs(grid,i,j+1,hash);

    }

    int numIslands(vector<vector<char>>& grid)

    {

        vector<vector<bool>> hash(301,vector<bool>(301));

        for(int i = 0;i<grid.size();i++)

        {

            for(int j = 0;j<grid[0].size();j++)

            {

                if(!hash[i][j]&&grid[i][j]=='1')//在该位置进行 dfs 的条件

                {

                    ans++;

                    dfs(grid,i,j,hash);

                }

            }

        }

        return ans;

    }

};

2. LCR 105. 岛屿的最大面积 - 力扣(LeetCode)

//思路:floodfill算法+哈希

//这些题的思路基本都是一样的,实在是没必要重复画那么多决策树。

//本题的思路与上一题 "岛屿数量" 是完全类似的:

//遍历数组,遇到没有访问过的位置 并且 该位置值为1,在该位置进行 dfs,计算当前位置所组成岛屿的面积;dfs结束后与结果进行比较,记录较大值。

class Solution {

public:

    int ans = 0;

    void dfs(vector<vector<int>>& grid,int i,int j,vector<vector<bool>>& hash,int& tmp)

    {

        if(i>=grid.size()||i<0||j>=grid[0].size()||j<0||!grid[i][j])//回溯:越界 || 当前位置值为0

            return;

        hash[i][j] = true;//每到一个 1 位置,将该位置设为 "已访问"

        tmp++;//统计岛屿面积

//上、下、左、右依次递归

        if(i-1>=0&&!hash[i-1][j])

            dfs(grid,i-1,j,hash,tmp);

        if(i+1<=grid.size()&&!hash[i+1][j])

            dfs(grid,i+1,j,hash,tmp);

        if(j-1>=0&&!hash[i][j-1])

            dfs(grid,i,j-1,hash,tmp);

        if(j+1<=grid[0].size()&&!hash[i][j+1])

            dfs(grid,i,j+1,hash,tmp);

    }

    int maxAreaOfIsland(vector<vector<int>>& grid)

    {

        vector<vector<bool>> hash(51,vector<bool>(51));

        for(int i = 0;i<grid.size();i++)

        {

            for(int j = 0;j<grid[0].size();j++)

            {

                int tmp = 0;//tmp用于统计面积

                if(!hash[i][j]&&grid[i][j])

                {

                    dfs(grid,i,j,hash,tmp);

                    ans = ans>tmp?ans:tmp;//比较取较大值

                }

            }

        }

        return ans;

    }

};

3. 130. 被围绕的区域 - 力扣(LeetCode)

//思路:floodfill+哈希

//本题思路还是类似,唯一的区别在于:我们如何区分哪些相连的 'O' 区域需要填充为 'X',哪些不需要?

class Solution {

public:

    void dfs(vector<vector<char>>& board,int i,int j,vector<vector<bool>>& hash)

    {

        if(i>=board.size()||i<0||j>=board[0].size()||j<0||board[i][j]=='X')//回溯:越界 || 当前位置为 'X'

            return;

        hash[i][j] = true;//将当前位置标记为 "已访问"

        board[i][j] = 'X';//并将当前位置的 'O' 更改为 'X'

//上、下、左、右递归

        if(i-1>=0&&!hash[i-1][j])

            dfs(board,i-1,j,hash);

        if(i+1<=board.size()&&!hash[i+1][j])

            dfs(board,i+1,j,hash);

        if(j-1>=0&&!hash[i][j-1])

            dfs(board,i,j-1,hash);

        if(j+1<=board[0].size()&&!hash[i][j+1])

            dfs(board,i,j+1,hash);

    }

    void solve(vector<vector<char>>& board)

    {

        vector<vector<bool>> hash(201,vector<bool>(201));

        vector<vector<char>> copy_board = board;//"替死鬼"数组,帮助我们标记 "不能更改" 的区域

//遍历 列边界,标记 列边界的 "不能更改" 的区域

        for(int i = 0;i<copy_board.size();i++)

        {

            if(copy_board[i][0]=='O')

                dfs(copy_board,i,0,hash);

            if(copy_board[i][copy_board[0].size()-1]=='O')

                dfs(copy_board,i,copy_board[0].size()-1,hash);

        }

       

//遍历 行边界,标记 行边界的 "不能更改" 的区域

        for(int j = 0;j<copy_board[0].size();j++)

        {

            if(copy_board[0][j]=='O')

                dfs(copy_board,0,j,hash);

            if(copy_board[copy_board.size()-1][j]=='O')

                dfs(copy_board,copy_board.size()-1,j,hash);

        }

//"替死鬼"数组帮我们标记了好了 "不能更改" 的区域,这里放心大胆地遍历board数组进行更改即可

        for(int i = 0;i<board.size();i++)

        {

            for(int j = 0;j<board[0].size();j++)

            {

                if(!hash[i][j]&&board[i][j]=='O')

                    dfs(board,i,j,hash);

            }

        }

    }

};

相关文章:

【每日刷题】Day143

【每日刷题】Day143 &#x1f955;个人主页&#xff1a;开敲&#x1f349; &#x1f525;所属专栏&#xff1a;每日刷题&#x1f34d; &#x1f33c;文章目录&#x1f33c; 1. 200. 岛屿数量 - 力扣&#xff08;LeetCode&#xff09; 2. LCR 105. 岛屿的最大面积 - 力扣&…...

基于Springboot智能学习平台的设计与实现

基于Springboot智能学习平台的设计与实现 开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 数据库&#xff1a;mysql 5.7 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;idea 源码获取&#xff1a;https://download.csdn.net/downlo…...

黑马javaWeb笔记重点备份11:Web请求与响应

请求 SpringBoot内置Servlet 在Tomcat这类Web服务器中&#xff0c;是不识别我们自己定义的Controller的&#xff0c;但在tomcat中是可以识别 Servlet程序的。在SpringBoot进行web程序开发时&#xff0c;它内置了一个核心的Servlet程序 DispatcherServlet&#xff0c;称之为 核…...

H5对接海康硬盘录像机视频简单说明

开发过程中使用HTML5(通常是通过Web技术栈,如HTML、CSS、JavaScript)与海康威视(Hikvision)的硬盘录像机(DVR)进行视频对接,通常涉及以下步骤: 获取DVR的RTSP流地址:海康威视DVR支持RTSP协议,你可以通过DVR的管理界面获取每个摄像头的RTSP流地址。 使用视频播放器库…...

测试人必备的Linux常用命令大全...【全网最全面整理】

Linux常用命令大全&#xff08;非常全&#xff01;&#xff01;&#xff01;&#xff09; 最近都在和Linux打交道&#xff0c;感觉还不错。我觉得Linux相比windows比较麻烦的就是很多东西都要用命令来控制&#xff0c;当然&#xff0c;这也是很多人喜欢linux的原因&#xff0c…...

苹果AI落后两年?——深度解析苹果在AI领域的挑战与前景

# 苹果AI落后两年&#xff1f;——深度解析苹果在AI领域的挑战与前景 近年来&#xff0c;人工智能&#xff08;AI&#xff09;领域的技术竞争日益激烈&#xff0c;各大科技巨头纷纷推出突破性的AI产品。然而&#xff0c;关于苹果公司在AI领域的表现&#xff0c;最近传出一些内…...

三菱PLC伺服-停止位置不正确故障排查

停止位置不正确时&#xff0c;请确认以下项目。 1)请确认伺服放大器(驱动单元)的电子齿轮的设定是否正确。 2&#xff09;请确认原点位置是否偏移。 1、设计近点信号(DOG)时&#xff0c;请考虑有足够为0N的时间能充分减速到爬行速度。该指令在DOG的前端开始减速到爬行速度&…...

Mybatis 批量操作存在则更新或者忽略,不存在则插入

Mybatis 批量操作新增&#xff0c;如果存在重复有下列2种处理方式&#xff1a; 1、存在则忽略代码示例&#xff1a; <insert id"insertDuplicateKeyIgnoreList">INSERT IGNORE INTO specs(status,type,code,name,create_time,create_by)VALUES<foreach col…...

「C/C++」C++ STL容器库 之 std::deque 双端队列容器

✨博客主页何曾参静谧的博客&#x1f4cc;文章专栏「C/C」C/C程序设计&#x1f4da;全部专栏「VS」Visual Studio「C/C」C/C程序设计「UG/NX」BlockUI集合「Win」Windows程序设计「DSA」数据结构与算法「UG/NX」NX二次开发「QT」QT5程序设计「File」数据文件格式「PK」Parasoli…...

一招教你解决Facebook广告账号问题

这段时间&#xff0c;我们写了很多文章来探讨Facebook的广告账户问题&#xff1a;《Facebook被封号该怎么办》《Facebook二不限、三不限账号是什么》《Facebook海外户&#xff08;三不限&#xff09;和账单户该如何选择》《如何区分真假Facebook三不限海外户》相信看过这些文章…...

MySQL启动报错:InnoDB: Unable to lock ./ibdata1 error

MySQL启动报错&#xff1a;InnoDB: Unable to lock ./ibdata1 error 在OS X环境下MySQL启动时报错&#xff1a; 016-03-03T00:02:30.483037Z 0 [ERROR] InnoDB: Unable to lock ./ibdata1 error: 35 2016-03-03T00:02:30.483100Z 0 [Note] InnoDB: Check that you do not alr…...

Linux终端之旅: 打包和压缩

在 Linux 世界中&#xff0c;打包和压缩文件是管理系统资源、传输数据和备份的重要技能。通过命令行工具如 tar、gzip、zip 等&#xff0c;我们可以高效地将多个文件或目录打包为一个文件&#xff0c;并通过压缩减少其体积。接下来&#xff0c;我将记录学习如何利用这些工具&am…...

PDA手持机提升管理效率和准确性

在当今快节奏的商业世界中&#xff0c;管理效率和准确性是企业成功的关键因素。而 PDA 手持机的出现&#xff0c;为企业管理带来了革命性的变革&#xff0c;成为提升管理效率和准确性的有力武器。 PDA 手持机&#xff0c;即个人数字助理手持设备&#xff0c;集数据采集、存储、…...

C++ [项目] 愤怒的小鸟

现在才发现C游戏的支持率这么高&#xff0c;那就发几篇吧 零、前情提要 此篇为 制作,由于他没有CSDN,于是由我代发 一、基本介绍 支持Dev-C5.11版本(务必调为英文输入法),基本操作看游戏里的介绍,怎么做的……懒得说,能看懂就看注释,没有的自己猜,如果你很固执……私我吧 …...

群控系统服务端开发模式-市场分析

刚刚我把群控系统服务端开发模式的文档全部整理了一下&#xff0c;结果发现还缺市场分析这篇文档没有上传&#xff0c;不好意思啦。 一、前言 在互联网高速发展且稳定的时代&#xff0c;营销系统是自运营公司线上最好的系统。加上现在直播行业很火&#xff0c;引流很重要&#…...

智能听诊器革新宠物健康监测

在宠物健康护理领域&#xff0c;智能听诊器的引入标志着一个新时代的开启&#xff0c;它正成为宠物医疗保健的新宠。这款设备通过高精度传感器捕捉宠物的心跳和呼吸声&#xff0c;为宠物主人和兽医提供精确的健康数据。 智能听诊器的即时反馈功能&#xff0c;使得主人能够通过…...

2000-2023年上市公司绿色专利申请授权面板数据

2000-2023年上市公司绿色专利申请授权面板数据 1、时间&#xff1a;2000-2023年 2、来源&#xff1a;国家知识产权局、WPIO清单 3、指标&#xff1a;年份、股票代码、股票简称、行业名称、行业代码、省份、城市、区县、区县代码、上市状态、绿色专利申请总量、绿色发明专利申…...

vue使用xlsx以及file-saver进行下载xlsx文件以及Unit8Array、ArrayBuffer、charCodeAt的使用

先说Unit8Array、ArrayBuffer、charCodeAt的使用下面会用到这三个 Unit8Array&#xff1a;数组类型表示一个 8 位无符号整型数组&#xff0c;创建时内容被初始化为 0。创建完后&#xff0c;可以以对象的方式或使用数组下标索引的方式引用数组中的元素。 new Uint8Array(); //…...

日语表目的的两个句型,柯桥成人零基础日语培训

句型&#xff1a; &#xff08;能做动词的&#xff09;名词&#xff08;或动词连用形&#xff09;に来ました&#xff08;或行きます&#xff09; 例句&#xff1a; わたしは日本へ文学の勉強に来ました。/我是到日本来学习文学的。 翻译&#xff1a; &#xff08;我&#…...

小程序中设置可拖动区域

官方说明文档&#xff1a;https://developers.weixin.qq.com/miniprogram/dev/component/movable-area.htmlhttps://developers.weixin.qq.com/miniprogram/dev/component/movable-view.html demo&#xff1a;浮动控件上下移动交互 .wxmx <movable-area><!-- y"…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...

安卓基础(Java 和 Gradle 版本)

1. 设置项目的 JDK 版本 方法1&#xff1a;通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分&#xff0c;设置 Gradle JDK 方法2&#xff1a;通过 Settings File → Settings... (或 CtrlAltS)…...

【Post-process】【VBA】ETABS VBA FrameObj.GetNameList and write to EXCEL

ETABS API实战:导出框架元素数据到Excel 在结构工程师的日常工作中,经常需要从ETABS模型中提取框架元素信息进行后续分析。手动复制粘贴不仅耗时,还容易出错。今天我们来用简单的VBA代码实现自动化导出。 🎯 我们要实现什么? 一键点击,就能将ETABS中所有框架元素的基…...