## 算法学习——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 == 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 == 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 == 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;}
};
``````

### RDGCN阅读笔记

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

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

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

### 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;在系统中不同目…

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

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