图论第二天|695. 岛屿的最大面积 1020. 飞地的数量 130. 被围绕的区域 417. 太平洋大西洋水流问题 827.最大人工岛

本文主要是介绍图论第二天|695. 岛屿的最大面积 1020. 飞地的数量 130. 被围绕的区域 417. 太平洋大西洋水流问题 827.最大人工岛,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • Leetcode695. 岛屿的最大面积
  • Leetcode1020. 飞地的数量
  • Leetcode130. 被围绕的区域
  • Leetcode417. 太平洋大西洋水流问题
  • Leetcode827.最大人工岛

Leetcode695. 岛屿的最大面积

文章链接:代码随想录
题目链接:695. 岛屿的最大面积

思路:dfs

class Solution {
public:int count;int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){for (int i = 0; i < 4; i++){int nex = x + dir[i][0];int ney = y + dir[i][1];if (nex < 0 || nex >= grid.size() || ney < 0 || ney >= grid[0].size()) continue;if (!visited[nex][ney] && grid[nex][ney] == 1){visited[nex][ney] = true;count++;dfs(grid, visited, nex, ney);}}}int maxAreaOfIsland(vector<vector<int>>& grid) {int result = 0;vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), 0));for (int i = 0; i < grid.size(); i++){for (int j = 0; j < grid[0].size(); j++){if (!visited[i][j] && grid[i][j] == 1){visited[i][j] = true;count = 1;dfs (grid, visited, i, j);result = max(result, count);}}}return result;}};

bfs

class Solution {
public:int count;int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){queue<pair<int, int>> que;que.push({x, y});while(!que.empty()){pair<int, int> cur = que.front();que.pop();for (int i = 0; i < 4; i++){int nex = cur.first + dir[i][0];int ney = cur.second + dir[i][1];if (nex < 0 || nex >= grid.size() || ney < 0 || ney >= grid[0].size()) continue;if (!visited[nex][ney] && grid[nex][ney] == 1){visited[nex][ney] = true;count++;que.push({nex, ney});}}}}int maxAreaOfIsland(vector<vector<int>>& grid) {int result = 0;vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), 0));for (int i = 0; i < grid.size(); i++){for (int j = 0; j < grid[0].size(); j++){if (!visited[i][j] && grid[i][j] == 1){visited[i][j] = true;count = 1;bfs (grid, visited, i, j);result = max(result, count);}}}return result;}};

Leetcode1020. 飞地的数量

文章链接:代码随想录
题目链接:1020. 飞地的数量

思路:dfs

class Solution {
public:int count = 0;int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};void dfs(vector<vector<int>>& grid, int x, int y){grid[x][y] = 0;count++;for (int i = 0; i < 4; i++){int nex = x + dir[i][0];int ney = y + dir[i][1];if (nex < 0 || nex >= grid.size() || ney < 0 || ney >= grid[0].size()) continue;if (grid[nex][ney] == 1) dfs(grid, nex, ney);}return ;}int numEnclaves(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();int result = 0;for (int i = 0; i < m; i++){if(grid[i][0] == 1) dfs(grid, i, 0);if(grid[i][n - 1] == 1) dfs(grid, i, n - 1);}for (int j = 0; j < n; j++){if (grid[0][j] == 1) dfs(grid, 0, j);if (grid[m - 1][j] == 1) dfs(grid, m - 1, j);}for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if (grid[i][j] == 1) {count = 0;dfs(grid, i, j);result += count;}}}return result;}
};

Leetcode130. 被围绕的区域

文章链接:代码随想录
题目链接:130. 被围绕的区域

思路:dfs

class Solution {
public:int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};void dfs(vector<vector<char>>& board, int x, int y){board[x][y] = 'A';for (int i = 0; i < 4; i++){int nex = x + dir[i][0];int ney = y + dir[i][1];if (nex < 0 || nex >= board.size() || ney < 0 || ney >= board[0].size()) continue;if (board[nex][ney] == 'O') dfs(board, nex, ney);}}    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 = 0; j < n; 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';if (board[i][j] == 'A') board[i][j] = 'O';}}}
};

Leetcode417. 太平洋大西洋水流问题

文章链接:代码随想录
题目链接:417. 太平洋大西洋水流问题

思路:注意终止条件 if (visited[x][y]) return ;

class Solution {
public:int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};void dfs(vector<vector<int>>& heights, vector<vector<bool>>& visited, int x, int y){// 注意终止条件if (visited[x][y]) return ;visited[x][y] = true;for (int i = 0; i < 4; i++){int nex = x + dir[i][0];int ney = y + dir[i][1];if (nex < 0 || nex >= heights.size() || ney < 0 || ney >= heights[0].size()) continue;if (heights[x][y] <= heights[nex][ney]) dfs(heights, visited, nex, ney);}}vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {int m = heights.size();int n = heights[0].size();vector<vector<bool>> pacific(m, vector<bool>(n, false));vector<vector<bool>> atlantic(m, vector<bool>(n, false));vector<vector<int>> result;for (int i = 0; i < m; i++){dfs(heights, pacific, i, 0);dfs(heights, atlantic, i, n - 1);}for (int j = 0; j < n; j++){dfs(heights, pacific, 0, j);dfs(heights, atlantic, m - 1, j);}for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if (pacific[i][j] && atlantic[i][j]) result.push_back({i, j});}}return result;}
};

Leetcode827.最大人工岛

文章链接:代码随想录
题目链接:827.最大人工岛

思路:dfs,先用map记录原有的每块陆地的大小,再在0处遍历连接陆地,选择最大值。

class Solution {
public:int count;int mark = 2;int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){if (visited[x][y] || grid[x][y] == 0) return ;visited[x][y] = true;count++;grid[x][y] = mark;for (int i = 0; i < 4; i++){int nex = x + dir[i][0];int ney = y + dir[i][1];if (nex < 0 || nex >= grid.size() || ney < 0 || ney >= grid[0].size()) continue;dfs(grid, visited, nex, ney);}}int largestIsland(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();vector<vector<bool>> visited(m, vector<bool>(n, false));unordered_map<int, int> gridNum;bool isAllGrid = true;int result = 0;for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if (grid[i][j] == 0) isAllGrid = false;if (!visited[i][j] && grid[i][j] == 1){count = 0;dfs(grid, visited, i, j);gridNum[mark] = count;mark++;}}}// cout << count << endl;// cout << gridNum[2] << endl;if (isAllGrid) return n * m;unordered_set<int> visitedGrid;for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){visitedGrid.clear();if (grid[i][j] == 0){count = 1;for (int k = 0; k < 4; k++){int nex = i + dir[k][0];int ney = j + dir[k][1];if (nex < 0 || nex >= grid.size() || ney < 0 || ney >= grid[0].size()) continue;if (visitedGrid.count(grid[nex][ney]) == 0){count += gridNum[grid[nex][ney]];visitedGrid.insert(grid[nex][ney]);}}result = max(result, count);}}}return result;}
};

图论第二天打卡,整体来说套路感挺重的,理解和做起来挺简单的,但写多了也头晕哈哈,加油!!!

这篇关于图论第二天|695. 岛屿的最大面积 1020. 飞地的数量 130. 被围绕的区域 417. 太平洋大西洋水流问题 827.最大人工岛的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/654863

相关文章

Vue3绑定props默认值问题

《Vue3绑定props默认值问题》使用Vue3的defineProps配合TypeScript的interface定义props类型,并通过withDefaults设置默认值,使组件能安全访问传入的... 目录前言步骤步骤1:使用 defineProps 定义 Props步骤2:设置默认值总结前言使用T

Web服务器-Nginx-高并发问题

《Web服务器-Nginx-高并发问题》Nginx通过事件驱动、I/O多路复用和异步非阻塞技术高效处理高并发,结合动静分离和限流策略,提升性能与稳定性... 目录前言一、架构1. 原生多进程架构2. 事件驱动模型3. IO多路复用4. 异步非阻塞 I/O5. Nginx高并发配置实战二、动静分离1. 职责2

解决升级JDK报错:module java.base does not“opens java.lang.reflect“to unnamed module问题

《解决升级JDK报错:modulejava.basedoesnot“opensjava.lang.reflect“tounnamedmodule问题》SpringBoot启动错误源于Jav... 目录问题描述原因分析解决方案总结问题描述启动sprintboot时报以下错误原因分析编程异js常是由Ja

MySQL 表空却 ibd 文件过大的问题及解决方法

《MySQL表空却ibd文件过大的问题及解决方法》本文给大家介绍MySQL表空却ibd文件过大的问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考... 目录一、问题背景:表空却 “吃满” 磁盘的怪事二、问题复现:一步步编程还原异常场景1. 准备测试源表与数据

解决Nginx启动报错Job for nginx.service failed because the control process exited with error code问题

《解决Nginx启动报错Jobfornginx.servicefailedbecausethecontrolprocessexitedwitherrorcode问题》Nginx启... 目录一、报错如下二、解决原因三、解决方式总结一、报错如下Job for nginx.service failed bec

SysMain服务可以关吗? 解决SysMain服务导致的高CPU使用率问题

《SysMain服务可以关吗?解决SysMain服务导致的高CPU使用率问题》SysMain服务是超级预读取,该服务会记录您打开应用程序的模式,并预先将它们加载到内存中以节省时间,但它可能占用大量... 在使用电脑的过程中,CPU使用率居高不下是许多用户都遇到过的问题,其中名为SysMain的服务往往是罪魁

MySQ中出现幻读问题的解决过程

《MySQ中出现幻读问题的解决过程》文章解析MySQLInnoDB通过MVCC与间隙锁机制在可重复读隔离级别下解决幻读,确保事务一致性,同时指出性能影响及乐观锁等替代方案,帮助开发者优化数据库应用... 目录一、幻读的准确定义与核心特征幻读 vs 不可重复读二、mysql隔离级别深度解析各隔离级别的实现差异

C++ vector越界问题的完整解决方案

《C++vector越界问题的完整解决方案》在C++开发中,std::vector作为最常用的动态数组容器,其便捷性与性能优势使其成为处理可变长度数据的首选,然而,数组越界访问始终是威胁程序稳定性的... 目录引言一、vector越界的底层原理与危害1.1 越界访问的本质原因1.2 越界访问的实际危害二、基

Python多线程应用中的卡死问题优化方案指南

《Python多线程应用中的卡死问题优化方案指南》在利用Python语言开发某查询软件时,遇到了点击搜索按钮后软件卡死的问题,本文将简单分析一下出现的原因以及对应的优化方案,希望对大家有所帮助... 目录问题描述优化方案1. 网络请求优化2. 多线程架构优化3. 全局异常处理4. 配置管理优化优化效果1.

Linux部署中的文件大小写问题的解决方案

《Linux部署中的文件大小写问题的解决方案》在本地开发环境(Windows/macOS)一切正常,但部署到Linux服务器后出现模块加载错误,核心原因是Linux文件系统严格区分大小写,所以本文给大... 目录问题背景解决方案配置要求问题背景在本地开发环境(Windows/MACOS)一切正常,但部署到