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

算法学习——LeetCode力扣图论篇1

算法学习——LeetCode力扣图论篇1

在这里插入图片描述

797. 所有可能的路径

797. 所有可能的路径 - 力扣(LeetCode)

描述

给你一个有 n 个节点的 有向无环图(DAG),请你找出所有从节点 0 到节点 n-1 的路径并输出(不要求按特定顺序)

graph[i] 是一个从节点 i 可以访问的所有节点的列表(即从节点 i 到节点 graph[i][j]存在一条有向边)。

示例

示例 1:
在这里插入图片描述

输入:graph = [[1,2],[3],[3],[]]
输出:[[0,1,3],[0,2,3]]
解释:有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

示例 2:

在这里插入图片描述

输入:graph = [[4,3,1],[3,2,4],[3],[4],[]]
输出:[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

提示

n == graph.length
2 <= n <= 15
0 <= graph[i][j] < n
graph[i][j] != i(即不存在自环)
graph[i] 中的所有元素 互不相同
保证输入为 有向无环图(DAG)

代码解析

class Solution {
public:vector<vector<int>> result;vector<int> path;void dfs(vector<vector<int>>& graph , int indnx){if(indnx == graph.size()-1) {path.push_back(graph.size()-1);result.push_back(path);path.pop_back();return;}for(int i=0 ; i<graph[indnx].size() ;i++){path.push_back(indnx);dfs(graph,graph[indnx][i]);path.pop_back();}return;}vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {dfs(graph,0);return result;}
};

200. 岛屿数量

200. 岛屿数量 - 力扣(LeetCode)

描述

给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。

岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外,你可以假设该网格的四条边均被水包围。

示例

示例 1:

输入:grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
输出:1

示例 2:

输入:grid = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]
输出:3

提示

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 ‘0’ 或 ‘1’

代码解析

深度优先搜索dfs
class Solution {
public:int result = 0;int m =0 ,n=0;int dir[4][2] = {0,1, 0,-1 , -1,0 , 1,0};void dfs(vector<vector<char>>& 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) continue;else if( path[next_x][next_y] == false && grid[next_x][next_y] == '1') {   path[next_x][next_y] = true;dfs(grid,path,next_x,next_y);}}return;}int numIslands(vector<vector<char>>& 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'){result++;path[i][j] = true;dfs(grid,path,i,j);}}}return result;}
};
广度优先搜索bfs
class Solution {
public:int result = 0;int m =0 ,n=0;int dir[4][2] = {0,1, 0,-1 , -1,0 , 1,0};void bfs(vector<vector<char>>& grid , vector<vector<bool>> &path , int x , int y){queue<pair<int,int>> my_que;my_que.push({x,y});path[x][y] = true;while(my_que.size() != 0){pair<int,int> cur = my_que.front();my_que.pop();for(int i=0 ; i<4 ;i++){int next_x = cur.first + dir[i][0];int next_y = cur.second + dir[i][1];if(next_x<0||next_x>=m||next_y<0||next_y>=n) continue;else if( path[next_x][next_y] == false && grid[next_x][next_y] == '1') {   my_que.push({next_x,next_y});path[next_x][next_y] = true;}}}return;}int numIslands(vector<vector<char>>& 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'){result++;path[i][j] = true;bfs(grid,path,i,j);}}}return result;}
};

695. 岛屿的最大面积

695. 岛屿的最大面积 - 力扣(LeetCode)

描述

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿,则返回面积为 0 。

示例

示例 1:
在这里插入图片描述

输入:grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出:6
解释:答案不应该是 11 ,因为岛屿只能包含水平或垂直这四个方向上的 1 。
示例 2:

输入:grid = [[0,0,0,0,0,0,0,0]]
输出:0

提示

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] 为 0 或 1

代码解析

class Solution {
public:int dir[4][2] = {0,1,0,-1,-1,0,1,0};int m=0,n=0;int result = 0;int tmp_result = 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) continue;if(grid[next_x][next_y] == 1 && path[next_x][next_y] == false){tmp_result++;path[next_x][next_y] = true;dfs(grid,path,next_x,next_y);}}}int maxAreaOfIsland(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(grid[i][j] == 1 && path[i][j] == false){path[i][j] = true;tmp_result = 1;dfs(grid,path,i,j);if(tmp_result > result) result =tmp_result;}}}return result;}
};

相关文章:

算法学习——LeetCode力扣图论篇1

算法学习——LeetCode力扣图论篇1 797. 所有可能的路径 797. 所有可能的路径 - 力扣&#xff08;LeetCode&#xff09; 描述 给你一个有 n 个节点的 有向无环图&#xff08;DAG&#xff09;&#xff0c;请你找出所有从节点 0 到节点 n-1 的路径并输出&#xff08;不要求按特…...

Stable Diffusion 模型下载:epiCPhotoGasm(真实、照片)

本文收录于《AI绘画从入门到精通》专栏&#xff0c;专栏总目录&#xff1a;点这里&#xff0c;订阅后可阅读专栏内所有文章。 文章目录 模型介绍生成案例案例一案例二案例三案例四案例五案例六案例七案例八 下载地址 模型介绍 该模型对照片是什么有很高的了解&#xff0c;所以…...

WPF 路由事件 数据驱动 、Window 事件驱动

消息层层传递&#xff0c;遇到安装有事件侦听器的对象&#xff0c;通过事件处理器响应事件&#xff0c;并决定事件是否继续传递&#xff1b; 后置代码中使用AddHandler方法设置事件监听器&#xff0c;该方法的 第一个参数是指定监听的路由事件类型对象&#xff0c; 第二个参数…...

【UI框架】——保姆式使用教程

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;开发者-曼亿点 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 曼亿点 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a…...

第10讲:操作符详解

第10讲&#xff1a;操作符详解 1. 操作符的分类2. 二进制和进制转换2.1 二进制转十进制10进制转2进制数 ![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/45fb3048f5164084b9d494b3d233bc42.png)2.2 二进制转八进制和十六进制2.2.1 二进制转八进制2.2.2 二进制转十六…...

数据可视化Grafana Windows 安装使用教程(中文版)

1.跳转连接 天梦星服务平台 (tmxkj.top)https://tmxkj.top/#/site?url 2.下载应用程序 官网地址&#xff1a;Grafana get started | Cloud, Self-managed, Enterprisehttps://grafana.com/get/ 3.修改配置文件 grafana\conf\defaults 4.启动\bin\目录下serve应用程序 浏…...

【No.21】蓝桥杯组合数学|数位排序|加法计数原理|乘法计数原理|排列数|组合数|抽屉原理|小蓝吃糖果|二项式定理|杨辉三角|归并排序(C++)

组合数学 数位排序 【问题描述】 小蓝对一个数的数位之和很感兴趣,今天他要按照数位之和给数排序。当两个数各个数位之和不同时,将数位和较小的排在前面,当数位之和相等时,将数值小的排在前面。 例如,2022 排在 409 前面, 因为 2022 的数位之和是 6,小于 409 的数位 之和 13。…...

主流公链 - Monero

Monero: 加密货币的隐私标杆 1. 简介 Monero&#xff08;XMR&#xff09;&#xff0c;世界语中货币的意思&#xff0c;是一种去中心化的加密货币&#xff0c;旨在提供隐私和匿名性。与比特币等公开区块链不同&#xff0c;Monero专注于隐私保护&#xff0c;使用户的交易记录和余…...

C#中让字典、列表、数组作为只读的方法参考

一、字典 在 C# 中&#xff0c;可以通过使用 ReadOnlyDictionary<TKey, TValue> 类或者是通过调用普通字典的 .AsReadOnly() 方法来创建一个只读的字典。ReadOnlyDictionary 不允许修改字典&#xff0c;任何试图改变字典的操作都会抛出 NotSupportedException。 以下是使…...

深入理解 React 中的 children props 和 render props

深入理解 React 中的 children props 和 render props 在 React 中&#xff0c;children props 和 render props 是两种常见的组件复用模式&#xff0c;它们都可以帮助我们更好地组织和复用组件代码。虽然它们的实现方式有所不同&#xff0c;但都能够有效地实现组件之间的数据…...

前端日期组件layui使用,月模式

初学前端&#xff0c;实战总结 概要 有一个日期组件&#xff0c;我的谷歌浏览器选完日期后&#xff0c;偶尔获取不到最新数据&#xff0c;有一个客户&#xff0c;是经常出不来数据。 日期组件是Wdate&#xff1a;调用的方法是WdatePicker onpicking&#xff0c;代码片段如下…...

Rust编程(四)PackageCrateModule

这一部分的中文教程/文档都很混乱,翻译也五花八门,所以我建议直接看英文官方文档,对于一些名词不要进行翻译,翻译只会让事情更混乱,本篇从实战和实际需求出发,讲解几个名称的关系。 Module & Crate & Package & Workspace 英文中的意思: Cargo:货物 Crate:…...

命名空间【C++】(超详细)

文章目录 命名空间的概念命名空间的定义命名空间定义的位置作用域每一个命名空间都是一个独立的域作用域符&#xff1a;&#xff1a; 编译器找一个变量/函数等的定义&#xff0c;寻找域的顺序为什么要有命名空间&#xff1f;1.解决库与程序员定义的同名的重定义问题2.解决程序员…...

OceanBase OBCA 数据库认证专员考证视频

培训概述 OceanBase 认证是 OceanBase 官方推出的唯一人才能力认证体系&#xff0c;代表了阿里巴巴及蚂蚁集团官方对考生关于 OceanBase 技术能力的认可&#xff0c;旨在帮助考生更好地学习 OceanBase 数据库产品&#xff0c;早日融入 OceanBase 技术生态体系&#xff0c;通过由…...

卷积神经网络(CNN)——基础知识整理

文章目录 1、卷积神经网络 2、图片格式 3、图片卷积运算 4、Kernel 与 Feature Map 5、padding/边缘填充 6、Stride/步长 7、pooling/池化 8、shape 9、epoch、batch、Batch Size、step 10、神经网络 11、激活函数 1、卷积神经网络 既然叫卷积神经网络&#xff0c;这里面首先是…...

2024四川省赛“信息安全管理与评估“--网络事件响应--应急响应(高职组)

2024四川省赛“信息安全管理与评估“(高职组)任务书 2024四川省赛“信息安全管理与评估“任务书第一阶段竞赛项目试题第二阶段竞赛项目试题任务 1 应急响应(40分)第三阶段竞赛项目试题2024四川省赛“信息安全管理与评估“任务书 第一阶段竞赛项目试题 先略 第二阶段竞赛…...

Java类与对象:从概念到实践的全景解析!

​ 个人主页&#xff1a;秋风起&#xff0c;再归来~ 文章专栏&#xff1a;javaSE的修炼之路 个人格言&#xff1a;悟已往之不谏&#xff0c;知来者犹可追 克心守己&#xff0c;律己则安&#xff01; 1、类的定义格式 在java中定义类时需要用到…...

MySQL与SQLite区别

MySQL和SQLite都是关系型数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;它们都使用SQL&#xff08;结构化查询语言&#xff09;作为标准查询语言。然而&#xff0c;尽管它们共享许多共同点&#xff0c;但它们在语法、功能、性能和存储机制方面存在一些差异。 以下是…...

【社会救助管理系统】主要设计及拟采用的技术方案

主要设计及拟采用的技术方案 1. 主要设计&#xff08;1&#xff09;系统架构设计&#xff08;2&#xff09;功能设计&#xff08;3&#xff09;安全性设计 2. 设计思想&#xff08;1&#xff09;系统架构设计思想&#xff08;2&#xff09;功能设计思想&#xff08;3&#xff0…...

视频素材库哪个软件好?这8个高清无版权的素材网推荐

小伙伴们在制作短视频的时候&#xff0c;是不是为找素材发愁呢&#xff1f;一个高质量的无水印视频对创作者的帮助太大了&#xff0c;而且还需要无版权可商用的&#xff0c;那究竟有没有这样的网站呢&#xff1f;今天我来告诉大家。 1&#xff0c;蛙学府&#xff08;中国&…...

故障发现滞后、处置不及时引发的业务中断与数据风险,超自动化巡检帮您解决

在数字化业务高度依赖IT系统的今天&#xff0c;每一次故障发现滞后、每一次处置不及时&#xff0c;都可能引发连锁反应——从关键业务中断到核心数据泄露&#xff0c;损失往往远超预期。传统运维模式在应对现代复杂系统时已显疲态&#xff0c;而超自动化巡检正成为破解这一困局…...

2025终极指南:如何快速解锁雀魂全角色皮肤?Mod工具使用全攻略

2025终极指南&#xff1a;如何快速解锁雀魂全角色皮肤&#xff1f;Mod工具使用全攻略 【免费下载链接】majsoul_mod_plus 雀魂解锁全角色、皮肤、装扮等&#xff0c;支持全部服务器。 项目地址: https://gitcode.com/gh_mirrors/ma/majsoul_mod_plus 还在为无法体验雀魂…...

so-vits-svc声压级标准化技术解析:从原理到实践的7个关键维度

so-vits-svc声压级标准化技术解析&#xff1a;从原理到实践的7个关键维度 【免费下载链接】so-vits-svc SoftVC VITS Singing Voice Conversion 项目地址: https://gitcode.com/gh_mirrors/so/so-vits-svc 声压级标准化是so-vits-svc&#xff08;SoftVC VITS Singing Vo…...

Thorium浏览器:重新定义现代网页浏览性能标准

Thorium浏览器&#xff1a;重新定义现代网页浏览性能标准 【免费下载链接】thorium Chromium fork named after radioactive element No. 90. Windows and MacOS/Raspi/Android/Special builds are in different repositories, links are towards the top of the README.md. …...

美团、腾讯、字节怎么选?3个真实案例告诉你答案

美团、腾讯、字节怎么选&#xff1f;3个真实案例告诉你答案 2026校招季&#xff0c;三个朋友的不同选择 大厂直通车-校招大礼包&#xff1a;入口入口 写在前面 2026届秋招结束了。 我的三个朋友小A、小B、小C都拿到了心仪的offer。有意思的是&#xff0c;他们分别选了字节、腾…...

2026降AI率工具红黑榜:降AI率工具怎么选?一篇讲透

千笔AI、ThouPen、豆包是当前适配国内高校AI率检测规范的优质选择&#xff1b;需警惕低质免费工具、无正规检测对接、改写痕迹生硬的平台&#xff1b;建议按降AI效果、学术合规性、使用成本三维度筛选&#xff0c;优先匹配A-B-C模型。 一、红榜&#xff1a;10 款高分论文降AI率…...

后端架构师转型AI智能体架构师:3个月实战路径,收藏这份落地指南

如果你本身就是后端/全栈/架构师出身&#xff0c;这意味着你已经有了一套非常扎实的“确定性系统”的构建能力——分布式、高并发、数据库事务、系统稳定性&#xff0c;这些都是你的底牌。 而AI智能体恰恰是“不确定性系统”&#xff08;大模型&#xff09;与“确定性系统”&am…...

OctoLinker:突破跨平台代码导航壁垒,实现无缝开发体验

OctoLinker&#xff1a;突破跨平台代码导航壁垒&#xff0c;实现无缝开发体验 【免费下载链接】OctoLinker OctoLinker — Links together, what belongs together 项目地址: https://gitcode.com/gh_mirrors/oc/OctoLinker 跨平台开发中&#xff0c;开发者常常面临不同…...

别再手动算置信区间了!ArcGIS里用Python脚本批量计算FVC,效率提升90%

遥感植被覆盖度自动化计算&#xff1a;用Python脚本解放ArcGIS生产力 当面对数百景遥感数据需要计算植被覆盖度(FVC)时&#xff0c;手动操作ArcGIS界面不仅耗时费力&#xff0c;还容易因人为失误导致结果不一致。我曾在一个省级生态评估项目中&#xff0c;需要处理3年共36期Lan…...

Python零基础到入门-数据类型的内置方法(1)

当我们在操作 字符串/列表&#xff0c;要想到对字符串或者列表做一些高级的操作字符串 判断这个字符是否以 某个字符开头列表 添加元素 删除元素 修改元素 。。。官方根据上边的功能&#xff0c;给我们提供了一些公共的接口&#xff08;方法&#xff09;【一】整数类型语法&…...