当前位置: 首页 > 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…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

Nginx server_name 配置说明

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

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

JavaScript 数据类型详解

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

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...