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

LeetCode130. Surrounded Regions

文章目录

    • 一、题目
    • 二、题解

一、题目

Given an m x n matrix board containing ‘X’ and ‘O’, capture all regions that are 4-directionally surrounded by ‘X’.

A region is captured by flipping all 'O’s into 'X’s in that surrounded region.

Example 1:

Input: board = [[“X”,“X”,“X”,“X”],[“X”,“O”,“O”,“X”],[“X”,“X”,“O”,“X”],[“X”,“O”,“X”,“X”]]
Output: [[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“O”,“X”,“X”]]
Explanation: Notice that an ‘O’ should not be flipped if:

  • It is on the border, or
  • It is adjacent to an ‘O’ that should not be flipped.
    The bottom ‘O’ is on the border, so it is not flipped.
    The other three ‘O’ form a surrounded region, so they are flipped.
    Example 2:

Input: board = [[“X”]]
Output: [[“X”]]

Constraints:

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] is ‘X’ or ‘O’.

二、题解

visited数组法——使用额外空间

与上题的方法类似,遍历四条边上值为’O’的值,并找出与其相邻的所有’O’,将其标记为已走过,最后遍历整张图,找到没走过的值为’O’的各自,并将其修改为’X’即可。本方法由于使用了visited数组,因此空间复杂度较高。

class Solution {
public:int dirs[4][2] = {1,0,0,1,-1,0,0,-1};void dfs(vector<vector<char>>& board,vector<vector<bool>>& visted,int x,int y){visted[x][y] = true;for(int i = 0;i < 4;i++){int nextX = x + dirs[i][0];int nextY = y + dirs[i][1];if(nextX < 0 || nextX >= board.size() || nextY < 0 || nextY >= board[0].size()) continue;if(board[nextX][nextY] == 'O' && visted[nextX][nextY] == false){visted[nextX][nextY] = true;dfs(board,visted,nextX,nextY);}}}void solve(vector<vector<char>>& board) {int m = board.size();int n = board[0].size();vector<vector<bool>> visted(m,vector<bool>(n,false));//对左和右进行遍历for(int i = 0;i < m;i++){if(board[i][0] == 'O' && visted[i][0] == false) dfs(board,visted,i,0);if(board[i][n-1] == 'O' && visted[i][n-1] == false) dfs(board,visted,i,n-1);}//对上和下进行遍历for(int j = 1;j < n - 1;j++){if(board[0][j] == 'O' && visted[0][j] == false) dfs(board,visted,0,j);if(board[m-1][j] == 'O' && visted[m-1][j] == false) dfs(board,visted,m-1,j);}//改变被包围飞地的值for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){if(board[i][j] == 'O' && visted[i][j] == false) board[i][j] = 'X';}}}
};

不使用额外空间的方法——直接在原数组中使用数字A进行标记

class Solution {
public:int dirs[4][2] = {1,0,0,1,-1,0,0,-1};void dfs(vector<vector<char>>& board,int x,int y){board[x][y] = 'A';for(int i = 0;i < 4;i++){int nextX = x + dirs[i][0];int nextY = y + dirs[i][1];if(nextX < 0 || nextX >= board.size() || nextY < 0 || nextY >= board[0].size()) continue;if(board[nextX][nextY] == 'O'){board[nextX][nextY] = 'A';dfs(board,nextX,nextY);}}}void solve(vector<vector<char>>& board) {int m = board.size();int n = board[0].size();//对左和右进行遍历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);}//对上和下进行遍历for(int j = 1;j < n - 1;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] == 'O') board[i][j] = 'X';else if(board[i][j] == 'A') board[i][j] = 'O';}}}
};

相关文章:

LeetCode130. Surrounded Regions

文章目录 一、题目二、题解 一、题目 Given an m x n matrix board containing ‘X’ and ‘O’, capture all regions that are 4-directionally surrounded by ‘X’. A region is captured by flipping all O’s into X’s in that surrounded region. Example 1: Input…...

【实战教程】PHP如何轻松对接腾讯云COS,实现文件上传下载?

腾讯云提供了一系列丰富的云服务&#xff0c;其中包括对象存储&#xff08;Cloud Object Storage&#xff0c;简称COS&#xff09;&#xff0c;它是一种高可靠性、可扩展性强的云存储服务。本文将介绍如何使用PHP对接腾讯云COS存储服务&#xff0c;实现文件的上传和下载功能。 …...

pytorch学习10-网络模型的保存和加载

系列文章目录 pytorch学习1-数据加载以及Tensorboard可视化工具pytorch学习2-Transforms主要方法使用pytorch学习3-torchvisin和Dataloader的使用pytorch学习4-简易卷积实现pytorch学习5-最大池化层的使用pytorch学习6-非线性变换&#xff08;ReLU和sigmoid&#xff09;pytorc…...

SQL Server 2016(分离和附加数据库)

1、实验环境。 基于上一个实验《SQL Server&#xff08;创建数据库&#xff09;》 2、需求描述。 class数据库的数据文件和事务日志文件都位于C:\db_class目录下。现在需要把class数据库的数据文件和事务日志文件分开存放&#xff0c;数据文件class.mdf存放于原位置&#xff0…...

用友U8 Cloud RegisterServlet SQL注入漏洞复现

0x01 产品简介 用友U8 Cloud是用友推出的新一代云ERP,主要聚焦成长型、创新型企业,提供企业级云ERP整体解决方案。 0x02 漏洞概述 用友U8 Cloud RegisterServlet接口处存在SQL注入漏洞,未授权的攻击者可通过此漏洞获取数据库权限,从而盗取用户数据,造成用户信息泄露。 …...

coding创建远程分支。并拉取远程新分支+推送代码

进入coding ----项目----代码仓库---点击 下拉之后查看全部----创建分支 创建分支之后执行下面命令 git branch -a // 查看所有分支 这个时候发现自己创建的分支没有显示这是因为自己在远程创建了分支但是本地还没有分支 执行 git fetch命令 用于从远程仓库获取最新的提交…...

坚鹏:中国工商银行内蒙古分行数字化转型发展现状与成功案例培训

中国工商银行围绕“数字生态、数字资产、数字技术、数字基建、数字基因”五维布局&#xff0c;深入推进数字化转型&#xff0c;加快形成体系化、生态化实施路径&#xff0c;促进科技与业务加速融合&#xff0c;以“数字工行”建设推动“GBC”&#xff08;政务、企业、个人&…...

AIGC发展史

1 AIGC概况 1.1 AIGC定义 AIGC&#xff08;AI Generated Content&#xff09;是指利用人工智能技术生成的内容。它也被认为是继PGC,UGC之后的新型内容生产方式&#xff0c;AI绘画、AI写作等都属于AIGC的具体形式。2022年AIGC发展速度惊人&#xff0c;迭代速度更是呈现指数级发…...

面试题库之JAVA基础篇(二)

String 只读字符串。每次操作会隐式的在内存中new一个跟原字符串一样的StringBuilder对象&#xff0c;然后append号后面的字符串。 StringBuilder 可变字符串对象。线程不安全。 StringBuffer 可变字符串对象。线程安全。 数组 一种线性数据结构&#xff0c;使用连续的…...

[Rust] 可迭代类型, 迭代器, 如何正确的创建自定义可迭代类型

在 Rust 中, for 语句的执行依赖于类型对于 IntoIterator 的实现, 如果某类型实现了这个 trait, 那么它就可以直接使用 for 进行循环. 直接实现 在 Rust 中, 如果一个类型实现了 Iterator, 那么它会被同时实现 IntoIterator, 具体逻辑是返回自身, 因为自身就是迭代器. 但是如…...

MySQL中,text,mediumtext, 和 longtext字符类型

需求 由于项目需要&#xff0c;需要在mysql数据库&#xff0c;储存长文本&#xff0c;长文本格式可能为markdown也可能为html。 思路 测试存入html时&#xff0c;字符类型为varcar 255。很明显字符长度达不到要求。数据库抛错&#xff0c;修改字符类型 解决方案 将原本的字…...

网页开发 JS基础

目录 JS概述 基本语法 数据类型内置方法 DOM对象 查找标签 绑定事件 操作标签 jQuery 查找标签 绑定事件 操作标签 Ajax请求 数据接口 前后端分离 ajax的使用 JS概述 一门弱类型的编程语言,属于基于对象和基于原型的脚本语言. 1 直接编写<script>console…...

如何在财税行业查找批量客户?

现在市场上代记账公司也不算少&#xff0c;做过这行的都知道&#xff0c;最初呢行业竞争不强&#xff0c;都是靠地推、老客户转介绍&#xff0c;或者长期以往的蹲守各个地区的工商注册服务中心&#xff0c;找那些才注册企业的老板或者创业者。但是&#xff0c;随着市场经济的发…...

IntelliJ IDEA详细完整安装教程

IntelliJ IDEA 是一款强大的Java集成开发环境&#xff0c;以下是安装和使用教程&#xff1a; 1. 下载IntelliJ IDEA&#xff1a;访问JetBrains官网&#xff08;jetbrains.com&#xff09;&#xff0c;点击“Download”按钮&#xff0c;选择适合自己操作系统的版本进行下载。 2.…...

【.NET Core】Linq查询运算符(一)

【.NET Core】Linq查询运算符&#xff08;一&#xff09; 文章目录 【.NET Core】Linq查询运算符&#xff08;一&#xff09;一、概述二、筛选数据三、投影运算3.1 Select 3.2 SelectMany3.3 Zip3.4 Select 与 SelectMany 四、Set&#xff08;设置&#xff09;运算4.1 Distinct…...

Python sorted函数及用法以及如何用json模块存储数据

Python sorted函数及用法 sorted() 函数与 reversed() 函数类似&#xff0c;该函数接收一个可迭代对象作为参数&#xff0c;返回一个对元素排序的列表。 在交互式解释器中测试该函数&#xff0c;可以看到如下运行过程&#xff1a; >>> a [20, 30, -1.2, 3.5, 90, 3.…...

使用opencv将sRGB格式的图片转换为BT.2020格式【sRGB】【BT.2020】

将sRGB格式的图片转换为BT.2020格式涉及到两个步骤&#xff1a;首先将sRGB转换到线性RGB&#xff0c;然后将线性RGB转换到BT.2020。这是因为sRGB图像通常使用伽马校正&#xff0c;而BT.2020工作在线性色彩空间中。 从sRGB到线性RGB&#xff1a;sRGB图像首先需要进行伽马校正解码…...

聊天注意事项

聊天成功的核心就是双方都能舒服 有些人不会聊天是缺乏引导性 聊天聊两句话就没了 聊天要把话题引导向对方 从倾诉者变为倾听者 才能不断交流 沟通不是一个人的独角戏 每个人都渴望被理解 要注意倾听别人说的话 不要只顾自己说一大堆&#xff0c;别人都瞌睡了 不要查户口式问…...

12.5 作业

1&#xff0c; 以下是一个简单的比喻&#xff0c;将多态概念与生活中的实际情况相联系&#xff1a; 比喻&#xff1a;动物园的讲解员和动物表演 想象一下你去了一家动物园&#xff0c;看到了许多不同种类的动物&#xff0c;如狮子、大象、猴子等。现在&#xff0c;动物园里有…...

深入理解指针3

hello&#xff0c;各位小伙伴&#xff0c;本篇文章跟大家一起继续深入学习指针&#xff0c;感谢大家对我上一篇的支持&#xff0c;如有什么问题&#xff0c;还请多多指教 如果本篇文章对你有帮助&#xff0c;还请各位点点赞&#xff01;&#xff01;&#xff01; 话不多说&am…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

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

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

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台

淘宝扭蛋机小程序系统的开发&#xff0c;旨在打造一个互动性强的购物平台&#xff0c;让用户在购物的同时&#xff0c;能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机&#xff0c;实现旋转、抽拉等动作&#xff0c;增…...