当前位置: 首页 > 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"><…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...