图论第二天|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.最大人工岛
目录 Leetcode695. 岛屿的最大面积Leetcode1020. 飞地的数量Leetcode130. 被围绕的区域Leetcode417. 太平洋大西洋水流问题Leetcode827.最大人工岛 Leetcode695. 岛屿的最大面积 文章链接:代码随想录 题目链接:695. 岛屿的最大面积 思路:dfs …...

【JavaScript 基础入门】02 JavaScrip 详细介绍
JavaScrip 详细介绍 目录 JavaScrip 详细介绍1. JavaScript 是什么2. JavaScript的作用3. HTML/CSS/JS 的关系4. 浏览器执行 JS 简介5. JavaScript 的组成6. JavaScript 的特点 1. JavaScript 是什么 JavaScript,通常缩写为 JS,是一种高级的,…...

鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之CheckboxGroup组件
鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之CheckboxGroup组件 一、操作环境 操作系统: Windows 10 专业版、IDE:DevEco Studio 3.1、SDK:HarmonyOS 3.1 二、CheckboxGroup组件 提供多选框组件,通常用于某选项的打开或关…...

【极数系列】Flink配置参数如何获取?(06)
文章目录 gitee码云地址简介概述01 配置值来自.properties文件1.通过路径读取2.通过文件流读取3.通过IO流读取 02 配置值来自命令行03 配置来自系统属性04 注册以及使用全局变量05 Flink获取参数值Demo1.项目结构2.pom.xml文件如下3.配置文件4.项目主类5.运行查看相关日志 gite…...

【docker】linux系统docker的安装及使用
一、docker应用的安装 1.1 安装方式 Docker的自动化安装,即使用提供的一键安装的脚本,进行安装。 官方的一键安装方式:curl -fsSL https://get.docker.com | bash -s docker --mirror Aliyun 国内 daocloud一键安装命令:curl -s…...

【C++】一题掌握空指针
今天看见一道面试题,比较有意思,这一分享出来: 1.下面程序能编译通过吗? 2.下面程序会崩溃吗?在哪里崩溃 class A {public:void PrintA(){cout<<_a<<endl;}void Show(){cout<<"Show()"&…...
初识HarmonyOS
一、HarmonyOS VS Android 相信很多关注鸿蒙的⼈,都会关注的⼀个焦点话题,那就是HarmonyOS是不是Android的套壳,对于这个话题,我只想阐明以下⼏个观点: HarmonyOS并不是Android的替代品,HarmonyOS与Android并⾮同⼀个赛道。HarmonyOS⽬前缺乏⽣态⽀持这⼀点远远⽐不上An…...

备战蓝桥杯---二分(入门)
话不多说,先来个模板题来回顾一下上次讲的: 下面是AC代码: 下面进入正题: 本题对1,2行与3,4行组合,再用二分查找即可实现n^2logn的复杂度。 下面是AC代码: 接题: 让我们…...
开发 Chrome 浏览器插件时进行 Vue3+Vite 多页面多入口配置
使用 Vite 开发 Chrome 插件时,构建多页面以及多 js 文件 因为发现 Vite 多页面构建有很多分歧以及问题点,所以我把我在 Chrome 插件开发上面使用到的 Vite 多页面以及多入口文件构建配置单独拿出来 开发 Chrome 插件是,一般会需要一个 popup…...

MacOS X 中 OpenGL 环境搭建 Makefile的方式
1,预备环境 安装 brew: /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)" 安装glfw: brew install glfw 安装glew: brew install glew 2.编译 下载源代码…...

前端工程化之:webpack1-6(编译过程)
一、webpack编译过程 webpack 的作用是将源代码编译(构建、打包)成最终代码。 整个过程大致分为三个步骤: 初始化编译输出 1.初始化 初始化时我们运行的命令 webpack 为核心包, webpack-cli 提供了 webpack 命令,通过…...
javaweb学习问题集
1 创建一个Javaweb项目 因为项目要放在tomcat10里运行,在添加tomcat10的依赖时,右键模块没有add frameworks support ,解决方法:按两下shift键,直接搜索 add frameworks support index.jsp文件我们已经不用了 我们在ideal上开发…...

java—AWT
AWT 课程:1、GUI编程简介_哔哩哔哩_bilibili 一.介绍 包含了很多类和接口!GUI!元素:窗口、按钮、文本框java.awt 二.窗口 1.构造 2.方法 // 实例化frame类Frame frame new Frame("这个一个框");// 设置可见性frame.…...

SQL注入-sqli-labs-master第一关
实验环境: Nginx.1.15.11 MySQL:5.7.26 实验步骤: 1.第一步: 在id1后加入一个闭合符号,如果报错,再在后面加上 -- 将后面注释掉,如果不报错,则证明为字符型。 http://127.0.0.1/…...

简述云原生基础定义及关键技术
云原生是什么 云原生是面向“云”而设计的应用,因此技术部分依赖于传统云计算的 3 层概念,基础设施即服务(IaaS)、平台即服务(PaaS)和软件即服务(SaaS)。 例如,敏捷的不可变基础设施交付类似于 IaaS,用来提供计算网络存储等基础资源,这些资源是可编程且不可变的,直…...
游戏中排行榜的后台实现
游戏中经常会有排行榜需求需要实现,例如常见的战力排行榜、积分排行榜等等。 排行榜一般会用到 Redis 来实现,原因是: Redis 基于内存操作,速度快Redis 提供了高效的有序集合 zset 例如创建一个名为 rank 的排行榜 # 为用户use…...

《动手学深度学习(PyTorch版)》笔记3.1
Chapter3 Linear Neural Networks 3.1 Linear Regression 3.1.1 Basic Concepts 我们通常使用 n n n来表示数据集中的样本数。对索引为 i i i的样本,其输入表示为 x ( i ) [ x 1 ( i ) , x 2 ( i ) , . . . , x n ( i ) ] ⊤ \mathbf{x}^{(i)} [x_1^{(i)}, x_2…...

【贪吃蛇:C语言实现】
文章目录 前言1.了解Win32API相关知识1.1什么是Win32API1.2设置控制台的大小、名称1.3控制台上的光标1.4 GetStdHandle(获得控制台信息)1.5 SetConsoleCursorPosition(设置光标位置)1.6 GetConsoleCursorInfo(获得光标…...

01.领域驱动设计:微服务设计为什么要选择DDD学习总结
目录 1、前言 2、软件架构模式的演进 3、微服务设计和拆分的困境 4、为什么 DDD适合微服务 5、DDD与微服务的关系 6、总结 1、前言 我们知道,微服务设计过程中往往会面临边界如何划定的问题,不同的人会根据自己对微服务的理 解而拆分出不同的微服…...

写静态页面——魅族导航_前端页面练习
0、效果: 1、html代码:: <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><…...

利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...

shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》
这段 Python 代码是一个完整的 知识库数据库操作模块,用于对本地知识库系统中的知识库进行增删改查(CRUD)操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 📘 一、整体功能概述 该模块…...

免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...