算法学习——LeetCode力扣图论篇2(1020. 飞地的数量、130. 被围绕的区域、827. 最大人工岛)

news/2024/6/15 16:12:38/文章来源:https://blog.csdn.net/qq_44814825/article/details/137183755

算法学习——LeetCode力扣图论篇2

在这里插入图片描述

1020. 飞地的数量

1020. 飞地的数量 - 力扣(LeetCode)

描述

给你一个大小为 m x n 的二进制矩阵 grid ,其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

示例

示例 1:
在这里插入图片描述

输入:grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出:3
解释:有三个 1 被 0 包围。一个 1 没有被包围,因为它在边界上。

示例 2:
在这里插入图片描述

输入:grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出:0
解释:所有 1 都在边界上或可以到达边界。

提示

m == grid.length
n == grid[i].length
1 <= m, n <= 500
grid[i][j] 的值为 0 或 1

代码解析

class Solution {
public:int result = 0 , tmp_size = 1;int m =0 ,n=0;bool borad_flag = false;int dir[4][2] = {0,1, 0,-1 , -1,0 , 1,0};void dfs(vector<vector<int>>& grid , vector<vector<bool>> &path , int x , int y){for(int i=0 ; i<4 ;i++){int next_x = x + dir[i][0];int next_y = y + dir[i][1];if(next_x<0||next_x>=m||next_y<0||next_y>=n){borad_flag = true;continue;}if( path[next_x][next_y] == false && grid[next_x][next_y] == 1) {   tmp_size++;path[next_x][next_y] = true;dfs(grid,path,next_x,next_y);}}return;}int numEnclaves(vector<vector<int>>& grid) {m = grid.size();n = grid[0].size();vector<vector<bool>> path( m , vector<bool>( n ,false) );for(int i=0 ; i<m ;i++){for(int j=0 ; j<n ;j++){if(path[i][j] == false && grid[i][j] == 1){tmp_size = 1;borad_flag = false;path[i][j] = true;dfs(grid,path,i,j);if(borad_flag == false ) result += tmp_size;}}}return result;}
};

130. 被围绕的区域

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

描述

给你一个 m x n 的矩阵 board ,由若干字符 ‘X’ 和 ‘O’ ,找到所有被 ‘X’ 围绕的区域,并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

示例

示例 1:
在这里插入图片描述

输入:board = [[“X”,“X”,“X”,“X”],[“X”,“O”,“O”,“X”],[“X”,“X”,“O”,“X”],[“X”,“O”,“X”,“X”]]
输出:[[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“O”,“X”,“X”]]
解释:被围绕的区间不会存在于边界上,换句话说,任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上,或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。

示例 2:

输入:board = [[“X”]]
输出:[[“X”]]

提示

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

代码解析

class Solution {
public:int m=0 , n=0;bool board_flag = false;int dir[4][2] = {0,-1,0,1,-1,0,1,0};void dfs(vector<vector<char>>& board ,  vector<vector<bool>> &path ,int x , int y ,bool exchange){   for(int i=0 ; i<4 ;i++){int next_x = x + dir[i][0];int next_y = y + dir[i][1];if(next_x<0 || next_x >= m || next_y<0||next_y>=n){board_flag = true;continue;}if(exchange == false && board[next_x][next_y] == 'O' && path[next_x][next_y] == false){path[next_x][next_y] = true;dfs(board,path,next_x,next_y,exchange);}if(exchange == true && board[next_x][next_y] == 'O'){board[next_x][next_y] = 'X';dfs(board,path,next_x,next_y,exchange);}}}void solve(vector<vector<char>>& board) {m = board.size();n = board[0].size();vector<vector<bool>> path(m,vector<bool>(n,false));for(int i=0 ; i<m ;i++){for(int j=0 ; j<n ;j++){if(board[i][j] == 'O' && path[i][j] == false){board_flag = false;path[i][j] = true;dfs(board,path,i,j,false);if(board_flag == false){board[i][j] = 'X';dfs(board,path,i,j,true);} }}}}
};

827. 最大人工岛

827. 最大人工岛 - 力扣(LeetCode)

描述

给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。

返回执行此操作后,grid 中最大的岛屿面积是多少?

岛屿 由一组上、下、左、右四个方向相连的 1 形成。

示例

示例 1:

输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1,最终连通两个小岛得到面积为 3 的岛屿。

示例 2:

输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1,岛屿的面积扩大为 4。

示例 3:

输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1,面积依然为 4。

提示

n == grid.length
n == grid[i].length
1 <= n <= 500
grid[i][j] 为 0 或 1

代码解析

class Solution {
public:int m = 0 , n = 0;int dir[4][2] = {0,-1,0,1,-1,0,1,0};int tmp_sum = 1 , bolck_num = 1;void dfs(vector<vector<int>>& grid ,vector<vector<bool>> &path , int x ,int y ,int num ){for(int i=0 ; i<4 ;i++){int next_x = x + dir[i][0];int next_y = y + dir[i][1];if(next_x<0||next_x>=m||next_y<0||next_y>=n) continue;if(grid[next_x][next_y] == 1 && path[next_x][next_y] == false){tmp_sum++;grid[next_x][next_y] = num;dfs(grid,path,next_x,next_y,num);}}}int largestIsland(vector<vector<int>>& grid) {m = grid.size();n = grid[0].size();vector<vector<bool>> path(m,vector<bool>(n,false));map<int,int> my_map;for(int i=0 ; i<m ;i++){for(int j=0 ; j<n ;j++){if(grid[i][j] == 1 && path[i][j] == false){bolck_num++;path[i][j] = true;grid[i][j] = bolck_num;tmp_sum=1;dfs(grid,path,i,j,bolck_num);my_map[bolck_num] = tmp_sum;}}}int result = 0 , tmp_result = 1;for(int i=0 ; i<m ;i++){for(int j=0 ; j<n ;j++){if(grid[i][j] == 0 && path[i][j] == false){path[i][j] = true;tmp_result = 1;set<int> my_set;for(int k=0 ; k<4 ;k++){int next_x = i + dir[k][0];int next_y = j + dir[k][1];if(next_x<0||next_x>=m||next_y<0||next_y>=n) continue;if(grid[next_x][next_y] != 0 ) my_set.insert(grid[next_x][next_y]);}for(auto it = my_set.begin() ; it!=my_set.end();it++) tmp_result += my_map[*it];my_set.clear();if(tmp_result > result) result = tmp_result;}}}if(result == 0) return m*n;return result;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

wps没保存关闭了恢复数据教程

有时候我们因为电脑问题会忘记保存就关闭wps导致数据丢失&#xff0c;不知道wps没保存关闭了怎么恢复数据&#xff0c;其实数据是无法恢复的。 wps没保存关闭了怎么恢复数据 1、wps没有数据恢复功能&#xff0c;不过可以开启自动备份。 2、我们可以先点击wps左上角的“文件”…

Docker 哲学 - push 本机镜像 到 dockerhub

注意事项&#xff1a; 1、 登录 docker 账号 docker login 2、docker images 查看本地镜像 3、注意的是 push镜像时 镜像的tag 需要与 dockerhub的用户名保持一致 eg&#xff1a;本地镜像 express:1 直接 docker push express:1 无法成功 原因docker不能识别 push到哪里 …

RDGCN阅读笔记

Relation-Aware Entity Alignment for Heterogeneous Knowledge Graphs 面向异质知识图谱的关系感知实体对齐 Abstract 实体对齐是从不同的知识图(KGs)中链接具有相同真实世界实体的任务&#xff0c;最近被基于嵌入的方法所主导。这种方法通过学习KG表示来工作&#xff0c;以…

基于python的matplotlib库绘制折线图

代码 import matplotlib.pyplot as plt# New data for CIDEr metric beam_sizes [1, 3, 5, 7] CIDEr_new [35.2, 35.6, 38.1, 37.6]# Creating the plot for CIDEr vs Beam Size with the updated data plt.figure(figsize(10, 6)) plt.plot(beam_sizes, CIDEr_new, marker^…

常见的Nginx+Redis+MQ+DB架构设计

三高&#xff0c;复杂的架构 SQRS CAP 缓存&#xff0c;限流 【Redis&#xff0c;缓存】 cache-aside 缓存cache&#xff1a;数据源的副本 store 1. Read/Write Through Pattern 读写穿透模式 redis&#xff1a;放当前在线用户&#xff0c;热点数据

破解密码:掌握2024年的营销归因

Cracking the Code: Mastering Marketing Attribution in 2024 营销归因是识别哪些营销渠道和触及点有助于销售或转化的过程。随着消费者继续通过多个渠道与品牌互动&#xff0c;掌握营销归因对企业来说变得越来越重要。在这篇文章中&#xff0c;我们将探讨破解代码和有效衡量…

云计算对象存储服务

对象存储服务&#xff08;OSS&#xff09;中的存储桶(Bucket)叫做‘OBS桶 存储桶&#xff08;Bucket&#xff09;&#xff1a;存储桶式对象存储服务中用于存储对象的基本容器&#xff0c;类似于文件系统中的文件夹。每个存储桶具有唯一的名称&#xff0c;并且可以在桶中存储任…

美摄科技AI智能图像矫正解决方案

图像已经成为了企业传播信息、展示产品的重要媒介&#xff0c;在日常拍摄过程中&#xff0c;由于摄影技巧的限制和拍摄环境的复杂多变&#xff0c;许多企业面临着图像内容倾斜、构图效果不佳等挑战&#xff0c;这无疑给企业的形象展示和信息传递带来了不小的困扰。 美摄科技深…

Redis高可用(持久化)

目录 一、Redis高可用 1. Redis高可用概述 2. Redis高可用策略 二、Redis持久化 1. Redis持久化的功能 2. Redis持久化的两种方式 3. RDB持久化 3.1 触发条件 3.1.1 手动触发 3.1.2 自动触发 ① 配置方式 ②其他自动触发机制 3.2 执行流程 3.3 启动时加载 4. AOF…

jmeter性能压测的标准和实战中会遇到的问题

1.性能标准建议 CPU 使用率&#xff1a;不超过 70% 内存使用率&#xff1a;不超过 70% 磁盘&#xff1a;%util到达80%严重繁忙 &#xff08;os.disIO.filesystem.writeKbPS 每秒写入的千字节&#xff09; 响应时间&#xff1a;95%的响应时间不超过8000ms 事务成功率&#xff1a…

mac怎么删除python

mac 默认安装了python2&#xff1b;自己后面又安装了python3&#xff1b;为了方便&#xff0c;现在想将python3换成Anaconda3。 Anaconda是一个开源的Python发行版本&#xff0c;其包含了conda、Python等180多个科学包及其依赖项。 Python3安装之后&#xff0c;在系统中不同目…

【zlm】音视频流与音频流合并的设计

目录 设想一 设想二 方案三 关键技术 测试语句 测试脚本 参考文档 设想一 //开始录制_option.mp4_save_path custom_path;_option.mp4_max_second max_second;vector<Track::Ptr> mytracks getTracks();auto src MediaSource::find( DEFAULT_VHOST, "1&quo…

Flink学习(二)-基础概念

一、流处理 分为有界流&#xff08;bounded stream&#xff09;和无界流&#xff08;unbounded stream&#xff09;。 通过上图 &#xff0c;可以知道&#xff0c; 有界流&#xff1a;有明显的边界&#xff1b;而无界流&#xff0c;则只有开始&#xff0c;没有结束。 批处理是…

Git 如何合并多个连续的提交

我平常的编程喜欢是写一段代码就提交一次&#xff0c;本地一般不攒代码&#xff0c;生怕本地有什么闪失导致白干。但这样就又导致一个问题&#xff1a;查看历史日志时十分不方便&#xff0c;随便找一段提交可以看到&#xff1a; > git log --oneline 8f06be5 add 12/qemu-h…

YUM安装MySQL报错合集

报错信息 Error:Problem: cannot install the best candidate for the job- nothing provides libcrypto.so.10()(64bit) needed by mysql-community-server-8.0.36-1.el7.x86_64 from mysql80-community- nothing provides libssl.so.10()(64bit) needed by mysql-community-…

工作常用设计模式

设计模式分类 创建者模式&#xff08;5种&#xff09; 单例模式原型模式工厂方法模式抽象工厂模式建造者模式 结构型模式&#xff08;7种&#xff09; 代理模式适配器模式桥接模式装饰者模式外观模式享元模式组合模式 行为型模式&#xff08;11种&#xff09; 模板方法模…

基于TSINGSEE青犀AI视频智能分析技术的山区林区烟火检测方案

随着清明节的临近&#xff0c;山区、林区防火迫在眉睫&#xff0c;TSINGSEE青犀AI智能分析网关V4烟火检测算法利用物联网、人工智能、图像识别技术&#xff0c;有效监测和管理烟火活动&#xff0c;并在火灾发生的同时发出告警&#xff0c;通知护林员与管理人员。 将山区林区的视…

线上研讨会 | 应对汽车毫米波雷达设计中的电磁挑战

智能汽车、新能源汽车最近几年一直是汽车行业关注的热点&#xff0c;随着5G技术越来越普及&#xff0c;汽车智能化发展将越来越迅速。从传统汽车到智能汽车&#xff0c;不是简单功能的增强&#xff0c;而是从单一功能的交通工具变成可移动的办公和娱乐空间&#xff0c;成为物联…

Python(乱学)

字典在转化为其他类型时&#xff0c;会出现是否舍弃value的操作&#xff0c;只有在转化为字符串的时候才不会舍弃value 注释的快捷键是ctrl/ 字符串无法与整数&#xff0c;浮点数&#xff0c;等用加号完成拼接 5不入&#xff1f;&#xff1f;&#xff1f; 还有一种格式化的方法…

AcWing 786. 第k个数——算法基础课题解

AcWing 786. 第k个数 题目描述 给定一个长度为 n的整数数列&#xff0c;以及一个整数 k&#xff0c;请用快速选择算法求出数列从小到大排序后的第 k 个数。 输入格式 第一行包含两个整数 n 和 k。 第二行包含 n 个整数&#xff08;所有整数均在 1∼10^9 范围内&#xff09…