当前位置: 首页 > news >正文

图论第二天|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. 岛屿的最大面积 文章链接&#xff1a;代码随想录 题目链接&#xff1a;695. 岛屿的最大面积 思路&#xff1a;dfs …...

【JavaScript 基础入门】02 JavaScrip 详细介绍

JavaScrip 详细介绍 目录 JavaScrip 详细介绍1. JavaScript 是什么2. JavaScript的作用3. HTML/CSS/JS 的关系4. 浏览器执行 JS 简介5. JavaScript 的组成6. JavaScript 的特点 1. JavaScript 是什么 JavaScript&#xff0c;通常缩写为 JS&#xff0c;是一种高级的&#xff0c;…...

鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之CheckboxGroup组件

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

【极数系列】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的自动化安装&#xff0c;即使用提供的一键安装的脚本&#xff0c;进行安装。 官方的一键安装方式&#xff1a;curl -fsSL https://get.docker.com | bash -s docker --mirror Aliyun 国内 daocloud一键安装命令&#xff1a;curl -s…...

【C++】一题掌握空指针

今天看见一道面试题&#xff0c;比较有意思&#xff0c;这一分享出来&#xff1a; 1.下面程序能编译通过吗&#xff1f; 2.下面程序会崩溃吗&#xff1f;在哪里崩溃 class A {public:void PrintA(){cout<<_a<<endl;}void Show(){cout<<"Show()"&…...

初识HarmonyOS

一、HarmonyOS VS Android 相信很多关注鸿蒙的⼈,都会关注的⼀个焦点话题,那就是HarmonyOS是不是Android的套壳,对于这个话题,我只想阐明以下⼏个观点: HarmonyOS并不是Android的替代品,HarmonyOS与Android并⾮同⼀个赛道。HarmonyOS⽬前缺乏⽣态⽀持这⼀点远远⽐不上An…...

备战蓝桥杯---二分(入门)

话不多说&#xff0c;先来个模板题来回顾一下上次讲的&#xff1a; 下面是AC代码&#xff1a; 下面进入正题&#xff1a; 本题对1&#xff0c;2行与3&#xff0c;4行组合&#xff0c;再用二分查找即可实现n^2logn的复杂度。 下面是AC代码&#xff1a; 接题&#xff1a; 让我们…...

开发 Chrome 浏览器插件时进行 Vue3+Vite 多页面多入口配置

使用 Vite 开发 Chrome 插件时&#xff0c;构建多页面以及多 js 文件 因为发现 Vite 多页面构建有很多分歧以及问题点&#xff0c;所以我把我在 Chrome 插件开发上面使用到的 Vite 多页面以及多入口文件构建配置单独拿出来 开发 Chrome 插件是&#xff0c;一般会需要一个 popup…...

MacOS X 中 OpenGL 环境搭建 Makefile的方式

1&#xff0c;预备环境 安装 brew&#xff1a; /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)" 安装glfw&#xff1a; brew install glfw 安装glew&#xff1a; brew install glew 2.编译 下载源代码…...

前端工程化之:webpack1-6(编译过程)

一、webpack编译过程 webpack 的作用是将源代码编译&#xff08;构建、打包&#xff09;成最终代码。 整个过程大致分为三个步骤&#xff1a; 初始化编译输出 1.初始化 初始化时我们运行的命令 webpack 为核心包&#xff0c; webpack-cli 提供了 webpack 命令&#xff0c;通过…...

javaweb学习问题集

1 创建一个Javaweb项目 因为项目要放在tomcat10里运行&#xff0c;在添加tomcat10的依赖时&#xff0c;右键模块没有add frameworks support ,解决方法&#xff1a;按两下shift键&#xff0c;直接搜索 add frameworks support index.jsp文件我们已经不用了 我们在ideal上开发…...

java—AWT

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

SQL注入-sqli-labs-master第一关

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

简述云原生基础定义及关键技术

云原生是什么 云原生是面向“云”而设计的应用,因此技术部分依赖于传统云计算的 3 层概念,基础设施即服务(IaaS)、平台即服务(PaaS)和软件即服务(SaaS)。 例如,敏捷的不可变基础设施交付类似于 IaaS,用来提供计算网络存储等基础资源,这些资源是可编程且不可变的,直…...

游戏中排行榜的后台实现

游戏中经常会有排行榜需求需要实现&#xff0c;例如常见的战力排行榜、积分排行榜等等。 排行榜一般会用到 Redis 来实现&#xff0c;原因是&#xff1a; Redis 基于内存操作&#xff0c;速度快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的样本&#xff0c;其输入表示为 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&#xff08;获得控制台信息&#xff09;1.5 SetConsoleCursorPosition&#xff08;设置光标位置&#xff09;1.6 GetConsoleCursorInfo&#xff08;获得光标…...

01.领域驱动设计:微服务设计为什么要选择DDD学习总结

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

写静态页面——魅族导航_前端页面练习

0、效果&#xff1a; 1、html代码&#xff1a;&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

深入浅出Diffusion模型:从原理到实践的全方位教程

I. 引言&#xff1a;生成式AI的黎明 – Diffusion模型是什么&#xff1f; 近年来&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;领域取得了爆炸性的进展&#xff0c;模型能够根据简单的文本提示创作出逼真的图像、连贯的文本&#xff0c;乃至更多令人惊叹的…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...