【算法与数据结构】1020、130、LeetCode飞地的数量 被围绕的区域

文章目录

  • 一、1020、飞地的数量
  • 二、130、被围绕的区域
  • 三、完整代码

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、1020、飞地的数量

在这里插入图片描述
在这里插入图片描述

  思路分析：博主认为题目很抽象，非常难理解。想了好久，要理解题目什么意思，必须理解“移动”这个概念。“移动”是指陆地可以移动，移动到连接的陆地单元或者跨过边界。例如示例1中的(1, 0)这块陆地可以移出边界，示例2中(2, 2)这块陆地，可以按照 ( 1 , 2 ) − > ( 0 , 2 ) − > ( 0 , 1 ) − > 边界外 (1, 2)->(0, 2)->(0, 1)->边界外 (1,2)−>(0,2)−>(0,1)−>边界外 的顺序离开网格边界。其他的陆地也类似，连接的陆地都可以移出边界。另一方面，从题目来理解更简单，要求飞地的数量。所谓飞地就是不和边界挨着的陆地，这也和任意次数“移动”出网格边界的定义一致。

  飞地的数量我们一眼就能看出，不和边界挨着的就是飞地。反过来想，我们顺着边界找到所有连接的陆地，讲这些陆地全部删除，剩下的就都是飞地，然后统计数量即可。程序当中，删除的这一操作不必实际进行，我们将其标记为已遍历，只要坐标是陆地且没有被遍历过就是飞地。

  程序如下：

// 1020、飞地的数量-深度优先搜索
class Solution {
private:
	int Area = 0;
	vector<vector<int>> delta_x_y = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };	// 上下左右四个方向的偏移量
	void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {	// 1、递归输入参数
		// 2、终止条件 访问过或者遇到海水，又或者越界
		if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || visited[x][y] || grid[x][y] == 0) return;  // 越界了，直接跳过
		visited[x][y] = true;
		//grid[x][y] = 0;		// 可以省略
		// 3、单层递归逻辑
		for (int i = 0; i < 4; i++) {
			int nextx = x + delta_x_y[i][0];
			int nexty = y + delta_x_y[i][1];			 
			dfs(grid, visited, nextx, nexty);
		}
	}
public:
    int numEnclaves(vector<vector<int>>& grid) {
		vector<vector<bool>> visited = vector<vector<bool>>(grid.size(), vector<bool>(grid[0].size(), false));	// 遍历过的坐标
		// 遍历最外面的一圈
		for (int i = 0; i < grid.size(); i++) {		// 遍历两列
			dfs(grid, visited, i, 0);
			dfs(grid, visited, i, grid[0].size() - 1);
		}
		for (int j = 1; j < grid[0].size() - 1; j++) {	// 遍历两行
			dfs(grid, visited, 0, j);
			dfs(grid, visited, grid.size() - 1, j);
		}

		for (int i = 1; i < grid.size() - 1; i++) {	// 遍历行
			for (int j = 1; j < grid[0].size() - 1; j++) {	// 遍历列
				if (grid[i][j] == 1 && !visited[i][j]) Area++;	// 深度优先搜索，将连接的陆地都标记上true
			}
		}
		return Area;
    }
};

复杂度分析：

  • 时间复杂度： O ( m × n ) O(m \times n) O(m×n)，其中 m m m和 n n n分别是岛屿数组的行数和列数。
  • 空间复杂度： O ( m × n ) O(m \times n) O(m×n)，主要是栈的调用，最坏情况下，网格全是陆地，深度优先搜索的深度达到 m × n m \times n m×n。

二、130、被围绕的区域

在这里插入图片描述
在这里插入图片描述

  思路分析：本题需要求将飞地改成‘X’。那么一个思路就是沿着网格边界搜索一遍，找到所有的‘O’并标记，表示这些‘O’不是飞地。然后，再将网格数组中的所有未标记过的‘O’改成‘X’即可。按照这样的思路需要一个额外的visited数组来标记‘O’，造成额外开销。实际上我们只需要区别标记过的‘O’（挨着边界的陆地）和未标记的‘O’（飞地），将标记过的‘O’改成其他字符即可（例如‘A’或者‘B’或者其他任意一个字符）。

  程序当中，先沿着边界遍历挨着边界的陆地，都改成‘A’。然后遍历边界以外的网格点，碰见‘O’就必然是飞地，将其改成‘X’。最后再将‘A’变回‘O’。

  程序如下：

// 130、被围绕的区域-深度优先搜索
class Solution2 {
private:
	vector<vector<int>> delta_x_y = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };	// 上下左右四个方向的偏移量
	void dfs(vector<vector<char>>& board, int x, int y) {	// 1、递归输入参数
		// 2、终止条件 遇到海水或者越界,遇到遍历过的陆地
		if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size() || board[x][y] == 'X' || board[x][y] == 'A') return;
		board[x][y] = 'A';
		// 3、单层递归逻辑
		for (int i = 0; i < 4; i++) {
			int nextx = x + delta_x_y[i][0];
			int nexty = y + delta_x_y[i][1];
			dfs(board, nextx, nexty);
		}
	}
public:
	void solve(vector<vector<char>>& board) {
		vector<vector<bool>> visited = vector<vector<bool>>(board.size(), vector<bool>(board[0].size(), false));	// 遍历过的坐标
		// 遍历最外面的一圈，找到挨着边界的陆地
		for (int i = 0; i < board.size(); i++) {		// 遍历外圈的两列
			if (board[i][0] == 'O') dfs(board, i, 0);
			if (board[i][board[0].size() - 1] == 'O') dfs(board, i, board[0].size() - 1);
		}
		for (int j = 1; j < board[0].size() - 1; j++) {	// 遍历外圈的两行
			if (board[0][j] == 'O') dfs(board, 0, j);
			if (board[board.size() - 1][j] == 'O') dfs(board, board.size() - 1, j);
		}
		// 遍历除边界以外的格点
		for (int i = 0; i < board.size(); i++) {	// 遍历行
			for (int j = 0; j < board[0].size(); j++) {	// 遍历列
				if (board[i][j] == 'O') board[i][j] = 'X';	// 删除飞地
 				if (board[i][j] == 'A') board[i][j] = 'O';	// 还原'O'
			}
		}
	}
};

复杂度分析：

  • 时间复杂度： O ( m × n ) O(m \times n) O(m×n)，其中 m m m和 n n n分别是网格数组的行数和列数。
  • 空间复杂度： O ( m × n ) O(m \times n) O(m×n)，主要是栈的调用。最坏情况下，网格全是‘O’，深度优先搜索的深度达到 m × n m \times n m×n。

三、完整代码

# include <iostream>
# include <vector>
# include <string>
using namespace std;

// 1020、飞地的数量-深度优先搜索
class Solution {
private:
	int Area = 0;
	vector<vector<int>> delta_x_y = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };	// 上下左右四个方向的偏移量
	void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {	// 1、递归输入参数
		// 2、终止条件 访问过或者遇到海水，又或者越界
		if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || visited[x][y] || grid[x][y] == 0) return;  // 越界了，直接跳过
		visited[x][y] = true;
		//grid[x][y] = 0;		// 可以省略
		// 3、单层递归逻辑
		for (int i = 0; i < 4; i++) {
			int nextx = x + delta_x_y[i][0];
			int nexty = y + delta_x_y[i][1];			 
			dfs(grid, visited, nextx, nexty);
		}
	}
public:
    int numEnclaves(vector<vector<int>>& grid) {
		vector<vector<bool>> visited = vector<vector<bool>>(grid.size(), vector<bool>(grid[0].size(), false));	// 遍历过的坐标
		// 遍历最外面的一圈
		for (int i = 0; i < grid.size(); i++) {		// 遍历外圈的两列
			dfs(grid, visited, i, 0);
			dfs(grid, visited, i, grid[0].size() - 1);
		}
		for (int j = 1; j < grid[0].size() - 1; j++) {	// 遍历外圈的两行
			dfs(grid, visited, 0, j);
			dfs(grid, visited, grid.size() - 1, j);
		}

		for (int i = 1; i < grid.size() - 1; i++) {	// 遍历行
			for (int j = 1; j < grid[0].size() - 1; j++) {	// 遍历列
				if (grid[i][j] == 1 && !visited[i][j]) Area++;	// 深度优先搜索，将连接的陆地都标记上true
			}
		}
		return Area;
    }
};

// 130、被围绕的区域-深度优先搜索
class Solution2 {
private:
	vector<vector<int>> delta_x_y = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };	// 上下左右四个方向的偏移量
	void dfs(vector<vector<char>>& board, int x, int y) {	// 1、递归输入参数
		// 2、终止条件 遇到海水或者越界,遇到遍历过的陆地
		if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size() || board[x][y] == 'X' || board[x][y] == 'A') return;
		board[x][y] = 'A';
		// 3、单层递归逻辑
		for (int i = 0; i < 4; i++) {
			int nextx = x + delta_x_y[i][0];
			int nexty = y + delta_x_y[i][1];
			dfs(board, nextx, nexty);
		}
	}
public:
	void solve(vector<vector<char>>& board) {
		vector<vector<bool>> visited = vector<vector<bool>>(board.size(), vector<bool>(board[0].size(), false));	// 遍历过的坐标
		// 遍历最外面的一圈，找到挨着边界的陆地
		for (int i = 0; i < board.size(); i++) {		// 遍历外圈的两列
			if (board[i][0] == 'O') dfs(board, i, 0);
			if (board[i][board[0].size() - 1] == 'O') dfs(board, i, board[0].size() - 1);
		}
		for (int j = 1; j < board[0].size() - 1; j++) {	// 遍历外圈的两行
			if (board[0][j] == 'O') dfs(board, 0, j);
			if (board[board.size() - 1][j] == 'O') dfs(board, board.size() - 1, j);
		}
		// 遍历除边界以外的格点
		for (int i = 0; i < board.size(); i++) {	// 遍历行
			for (int j = 0; j < board[0].size(); j++) {	// 遍历列
				if (board[i][j] == 'O') board[i][j] = 'X';	// 删除飞地
 				if (board[i][j] == 'A') board[i][j] = 'O';	// 还原'O'
			}
		}
	}
};

void my_print(vector<vector<char>> board, string message) {
	cout << message << endl;
	for (vector<vector<char>>::iterator it = board.begin(); it != board.end(); it++) {
		for (vector<char>::iterator jt = (*it).begin(); jt != (*it).end(); jt++) {
			cout << *jt << " ";
		}
		cout << endl;
	}
}

int main() {
	// // 1020、飞地的数量-深度优先搜索-测试案例
    //vector<vector<int>> grid = { {0, 0, 0, 0}, { 1, 0, 1, 0 }, { 0, 1, 1, 0 }, { 0, 0, 0, 0 } };
    //Solution s1;
    //int result = s1.numEnclaves(grid);
    //cout << result << endl;

	// 130、被围绕的区域-深度优先搜索-测试案例
	vector<vector<char>> board = { {'X', 'X', 'X', 'X'}, {'X', 'O', 'O', 'X'}, {'X', 'X', 'O', 'X'}, {'X', 'O', 'X', 'X'} };
	my_print(board, "替换前：");
	Solution2 s1;
	s1.solve(board);
	my_print(board, "替换后：");
    system("pause");
    return 0;
}

end

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/401408.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

(っ•̀ω•́)っ 如何在PPT中为文本框添加滚动条

(っ•̀ω•́)っ 如何在PPT中为文本框添加滚动条

本人在写技术分享的PPT时&#xff0c;遇到问题&#xff1a;有一大篇的代码&#xff0c;如何在一张PPT页面上显示&#xff1f;急需带有滚动条的文本框&#xff01;百度了不少&#xff0c;自己也来总结一篇&#xff0c;如下&#xff1a; 1、找到【文件】-【选项】 2、【自定义功…
阅读更多...
基于 QUIC 协议的 HTTP/3 正式发布！

基于 QUIC 协议的 HTTP/3 正式发布！

近期&#xff0c;超文本传输协议新版本 HTTP/3 RFC 文档&#xff0c;已由互联网工程任务组&#xff08;IETF&#xff09;对外发布。HTTP/3 全称为 HTTP-over-QUIC&#xff0c;指在 QUIC&#xff08;Quick UDP Internet Connections, 快速 UDP 互联网连接&#xff09;上映射 HTT…
阅读更多...
3个精美的wordpress企业网站模板

3个精美的wordpress企业网站模板

WordPress企业网站模板 https://www.zhanyes.com/qiye/6305.html WordPress企业官网模板 https://www.zhanyes.com/qiye/6309.html WordPress律师模板 https://www.zhanyes.com/qiye/23.html
阅读更多...
深入浅出JVM（四）之类文件结构

深入浅出JVM（四）之类文件结构

深入浅出JVM&#xff08;四&#xff09;之类文件结构 Java文件编译成字节码文件后&#xff0c;通过类加载机制到Java虚拟机中&#xff0c;Java虚拟机能够执行所有符合要求的字节码&#xff0c;因此无论什么语言&#xff0c;只要能够编译成符合要求的字节码文件就能够被Java虚拟…
阅读更多...
webpack配置杂记

webpack配置杂记

1、热更新 安装webpack-dev-server : npm i webpack-dev-server -D webpack.config.js配置 module.exports {// 其他配置...,// 热更新配置devServer: {host: "localhost",port: 3000,}, } 2、入口entry&#xff1a;使用相对路径们也就是webpack程序运行的路径&am…
阅读更多...
Qt应用软件【协议篇】MQTT官方源码编译安装

Qt应用软件【协议篇】MQTT官方源码编译安装

文章目录 QT官方代码选择对应的版本Qt Creator编译代码代码下载与编译安装mqtt命令行方式编译与安装代码示例QT官方代码 https://github.com/qt/qtmqtt/tree/5.15.2 选择对应的版本 我们可以在github上切换分支，切换到我们需要的版本上 Qt Creator编译代码 代码下载与编译…
阅读更多...
win10编译openjdk源码

win10编译openjdk源码

上篇文章作者在ubuntu系统上实践完成openjdk源码的编译&#xff0c;但是平常使用更多的是window系统&#xff0c;ubuntu上编译出来JDK无法再windows上使用。所以作者又花费了很长时间在windows系统上完成openjdk源码的编译&#xff0c;陆续花费一个月的时间终于完成了编译。 本…
阅读更多...
2024牛客寒假算法基础集训营5 -- EF soyorin的数组操作

2024牛客寒假算法基础集训营5 -- EF soyorin的数组操作

题目大意&#xff1a; 思路解析&#xff1a; 我们可以发现偶数情况下&#xff0c;我们可以无限做 k n的操作&#xff0c;这样一定会让数组变为非降序数组。 但是奇数情况下&#xff0c;最后一个数没有办法发生变化&#xff0c;所以我们只能统计怎样在保证i--n为非降序情况下最…
阅读更多...
解决IntelliJ IDEA 2023版本创建Spring项目时Java只能选择17或21的问题

解决IntelliJ IDEA 2023版本创建Spring项目时Java只能选择17或21的问题

问题描述&#xff1a; 当使用IntelliJ IDEA2023版本中Spring Initializr新建Spring项目时&#xff0c;即使JDK配置项为1.8&#xff0c;Java配置项仍然只能选17或21. 在JDK为1.8版本情况下&#xff0c;Java选择17或21&#xff0c;点击NEXT按钮&#xff0c;则会弹窗提示SDK不支持…
阅读更多...
ChatGPT丨“成像光谱遥感技术中的AI革命：ChatGPT应用指南“

ChatGPT丨“成像光谱遥感技术中的AI革命：ChatGPT应用指南“

遥感技术主要通过卫星和飞机从远处观察和测量我们的环境&#xff0c;是理解和监测地球物理、化学和生物系统的基石。ChatGPT是由OpenAI开发的最先进的语言模型&#xff0c;在理解和生成人类语言方面表现出了非凡的能力。本文重点介绍ChatGPT在遥感中的应用&#xff0c;人工智能…
阅读更多...
ClickHouse--11--ClickHouse API操作

ClickHouse--11--ClickHouse API操作

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 1.Java 读写 ClickHouse API1.1 首先需要加入 maven 依赖1.2 Java 读取 ClickHouse 集群表数据JDBC--01--简介 ClickHouse java代码 1.3 Java 向 ClickHouse 表中写…
阅读更多...
高校学科竞赛平台|基于springboot高校学科竞赛平台设计与实现(源码+数据库+文档)

高校学科竞赛平台|基于springboot高校学科竞赛平台设计与实现(源码+数据库+文档)

高校学科竞赛平台目录 目录 基于springboot高校学科竞赛平台设计与实现 一、前言 二、系统功能设计 三、系统实现 1、竞赛题库管理 2、竞赛信息管理 3、晋级名单管理 4、往年成绩管理 5、参赛申请管理 四、数据库设计 1、实体ER图 五、核心代码 六、论文参考 七、最…
阅读更多...
typescript 索引签名类型

typescript 索引签名类型

ts索引类型简介 在TypeScript中&#xff0c;索引签名类型&#xff08;Index Signature Type&#xff09;是一种特殊的类型&#xff0c;它定义了对象中键的类型以及相应的值的类型。通过使用索引签名类型&#xff0c;我们可以表示一个对象&#xff0c;该对象的键可以是任意类型…
阅读更多...
Android全新UI框架之常用ComposeUI组件

Android全新UI框架之常用ComposeUI组件

在Compose中&#xff0c;每个组件都是一个带有Composable注解的函数&#xff0c;被称为Composable。Compose已经预置了很多基于MD设计规范的Composable组件。 在布局方面&#xff0c;Compose提供了Column、Row、Box三种布局组件(感觉跟flutter差不多)&#xff0c;类似于传统视图…
阅读更多...
《Python 语音转换简易速速上手小册》第5章 音频数据处理（2024 最新版）

《Python 语音转换简易速速上手小册》第5章 音频数据处理（2024 最新版）

文章目录 5.1 音频数据的基本处理5.1.1 基础知识5.1.2 主要案例&#xff1a;音频剪辑工具案例介绍案例 Demo案例分析 5.1.3 扩展案例 1&#xff1a;自动音量调节器案例介绍案例 Demo案例分析 5.1.4 扩展案例 2&#xff1a;语音识别预处理案例介绍案例 Demo案例分析 5.2 使用 Py…
阅读更多...
LLM 模型融合实践指南：低成本构建高性能语言模型

LLM 模型融合实践指南：低成本构建高性能语言模型

编者按&#xff1a;随着大语言模型技术的快速发展&#xff0c;模型融合成为一种低成本但高性能的模型构建新途径。本文作者 Maxime Labonne 利用 mergekit 库探索了四种模型融合方法&#xff1a;SLERP、TIES、DARE和passthrough。通过配置示例和案例分析&#xff0c;作者详细阐…
阅读更多...
开启智能互动新纪元——ChatGPT提示词工程的引领力

开启智能互动新纪元——ChatGPT提示词工程的引领力

目录 提示词工程的引领力 高效利用ChatGPT提示词方法 提示词工程的引领力 近年来&#xff0c;随着人工智能技术的迅猛发展&#xff0c;ChatGPT提示词工程正逐渐崭露头角&#xff0c;为智能互动注入了新的活力。这一技术的引入&#xff0c;使得人机交流更加流畅、贴近用户需求&…
阅读更多...
S-35390A计时芯片介绍及开发方案

S-35390A计时芯片介绍及开发方案

计时芯片 S-35390A芯片是计时芯片&#xff0c;一般用来计算时间。低功耗&#xff0c;宽电压&#xff0c;受温度影响小&#xff0c;适用于很多电路。它有一个问题&#xff0c;不阻止用户设置不存在的时间&#xff0c;设置进去之后计时或者闹钟定时会出错。 规格书阅读 首先我…
阅读更多...
推荐几款项目经理常用的项目管理软件

推荐几款项目经理常用的项目管理软件

随着科技的发展和项目需求&#xff0c;项目管理工具成为了确保工作顺利进行的关键。市场上有许多优秀的免费项目管理工具&#xff0c;它们功能强大、易于使用&#xff0c;并可以帮助团队更有效地规划、组织、执行和监控项目。以下是几款深受项目经理欢迎&#xff0c;好用且免费…
阅读更多...
【转载】企业资产收集与脆弱性检查工具

【转载】企业资产收集与脆弱性检查工具

简介 云图极速版是针对拥有攻击面管理需求的用户打造的 SaaS 应用&#xff0c;致力于协助用户管理互联网资产攻击面的 SaaS 化订阅服务产品。可实现对备案域名、子域名、IP、端口、服务、网站、漏洞、安全风险等场景进行周期性监控&#xff0c;支持多维度分析攻击面。利用可视化…
阅读更多...
最新文章

Copyright @ 2022~2023