算法学习——LeetCode力扣图论篇1(797. 所有可能的路径、200. 岛屿数量、695. 岛屿的最大面积)

算法学习——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;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/510616.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

STM32 DWT数据观察触发器作为延时函数的使用

STM32 DWT数据观察触发器作为延时函数的使用 &#x1f4d1;DWT(Data Watchpoint and Trace数据观察触发器&#xff09;描述 &#x1f4dd;DWT是属于处理器内核单元中的调试组件之一&#xff0c;由四个比较器组成。它们可配置为&#xff1a;硬件监视点或对ETM或PC采样器或数据地…

Ubuntu20.04安装MatlabR2018a

一、安装包 安装包下载链接 提取码&#xff1a;kve2 网上相关教程很多&#xff0c;此处仅作为安装软件记录&#xff0c;方便后续软件重装&#xff0c;大家按需取用。 二、安装 1. 相关文件一览 下载并解压文件后&#xff0c;如下图所示&#xff1a; 2. 挂载镜像并安装 2…

06 | Swoole 源码分析之 Coroutine 协程模块

首发原文链接&#xff1a;Swoole 源码分析之 Coroutine 协程模块 大家好&#xff0c;我是码农先森。 引言 协程又称轻量级线程&#xff0c;但与线程不同的是&#xff1b;协程是用户级线程&#xff0c;不需要操作系统参与。由用户显式控制&#xff0c;可以在需要的时候挂起、或…

回顾快速排序

快速排序 快速排序的核心&#xff1a; 找到一个key 通常左边的数比key小&#xff0c;右边的数比key大。 找key通常有三种方法&#xff1a; 1. 挖坑法&#xff1a; 代码实现&#xff1a; // int _pivot(int* a, int left, int right) {int begin left, end right;int in…

动态图学习新突破!最新SOTA实现性能全面升级,效率与精度兼得

现实世界中的许多图数据是动态变化的&#xff0c;比如社交网络、交通流量等。而传统的图学习方法通常处理的是静态图&#xff0c;这就导致它缺乏处理动态变化的能力&#xff0c;在适应性方面存在局限性。 相较之下&#xff0c;动态图学习能够捕捉到图数据的动态变化&#xff0…

MuJoCo 入门教程(一)

系列文章目录 前言 一、简介 MuJoCo 是多关节接触动力学&#xff08;Multi-Joint dynamics with Contact&#xff09;的缩写。它是一个通用物理引擎&#xff0c;旨在促进机器人、生物力学、图形和动画、机器学习以及其他需要快速、准确地仿真铰接结构与环境交互的领域的研究和开…

ssm016基于 Java Web 的校园驿站管理系统+jsp

校园驿站管理系统的设计与实现 摘 要 互联网发展至今&#xff0c;无论是其理论还是技术都已经成熟&#xff0c;而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播&#xff0c;搭配信息管理工具可以很好地为人们提供服务。针对校园快递信息管理混乱&#xff0c;出…

阿里云优惠券如何领取使用?

阿里云是阿里巴巴旗下云计算及人工智能科技公司&#xff0c;提供云服务器、云数据库、云存储等云计算服务和云解决方案。为了吸引更多的用户&#xff0c;阿里云经常推出各种优惠活动&#xff0c;其中就包括阿里云优惠券。本文将为大家详细介绍阿里云优惠券领取方法及使用教程&a…

Nginx 基础

文章目录 Nginx概念安装下载上传安装包执行准备条件指定安装位置编译和安装启动服务创建启动脚本 linux文件目录nginx运行原理nginx配置域名概念和原理域名配置 Nginx 概念 Nginx 是一个高性能的HTTP和反向代理web服务器&#xff0c;同时也提供了IMAP/POP3/SMTP服务。Nginx是…

211基于matlab的多类结构动力学

基于matlab的多类结构动力学&#xff0c;凸轮机构、双凸轮、弦振动模拟、阻尼振动 、四连杆机构 、套杆运动 、三根弹簧作用的振子。程序已调通&#xff0c;可直接运行。 211 matlab 结构动力学 根弹簧作用的振子 - 小红书 (xiaohongshu.com)

javaweb学习(day10-服务器渲染技术)

一、基本介绍 1.前言 目前主流的技术是 前后端分离 (比如: Spring Boot Vue/React)JSP 技术使用在逐渐减少&#xff0c;但使用少和没有使用是两个意思&#xff0c;一些老项目和中小公司还在使用 JSP&#xff0c;工作期间&#xff0c;你很有可能遇到 JSPJSP 使用在减少(但是现…

Python深度学习034:cuda的环境如何配置

文章目录 1.安装nvidia cuda驱动CMD中看一下cuda版本:下载并安装cuda驱动2.创建虚拟环境并安装pytorch的torch_cuda3.测试附录1.安装nvidia cuda驱动 CMD中看一下cuda版本: 注意: 红框的cuda版本,是你的显卡能装的最高的cuda版本,所以可以选择低于它的版本。比如我的是11…

人工智能|深度学习——基于Xception算法模型实现一个图像分类识别系统

一、Xception简介 在计算机视觉领域&#xff0c;图像识别是一个非常重要的任务&#xff0c;其应用涵盖了人脸识别、物体检测、场景理解等众多领域。随着深度学习技术的发展&#xff0c;深度卷积神经网络&#xff08;Convolutional Neural Networks&#xff0c;简称CNN&#xff…

阿赵UE学习笔记——24、动画播放控制

阿赵UE学习笔记目录   大家好&#xff0c;我是阿赵。   继续学习虚幻引擎的使用。关于UE的动画系统&#xff0c;之前学习了很多&#xff0c;包括动画合成或者动画蒙太奇等&#xff0c;实际上最后得到的都是一个动画片段。那么这些动画片段&#xff0c;是需要怎样播放控制呢…

乐观锁解决超卖问题

3.6 乐观锁解决超卖问题 修改代码方案一、 VoucherOrderServiceImpl 在扣减库存时&#xff0c;改为&#xff1a; boolean success seckillVoucherService.update().setSql("stock stock -1") //set stock stock -1.eq("voucher_id", voucherId).eq(&q…

STM32-02基于HAL库(CubeMX+MDK+Proteus)GPIO输出案例(LED流水灯)

文章目录 一、功能需求分析二、Proteus绘制电路原理图三、STMCubeMX 配置引脚及模式&#xff0c;生成代码四、MDK打开生成项目&#xff0c;编写HAL库的GPIO输出代码五、运行仿真程序&#xff0c;调试代码 一、功能需求分析 在完成开发环境搭建之后&#xff0c;开始使用STM32GP…

TCP和UDP区别和使用场景

TCP 和 UDP 是计算机⽹络中两种常⽤的传输层协议&#xff0c;⽤于实现可靠传输和⽆连接传输。 TCP TCP&#xff08;Transmission Control Protocol&#xff09;是⼀种⾯向连接的、可靠的传输协议。它通过三次握⼿四次挥⼿进⾏连接和断开链接&#xff0c;保证数据的可靠性、…

H5类似Word文档输入框小记

最近一个需求在客户端编辑输入超长文本带下划线。 最开始的input、textarea无法像span一样换行pass了。柳暗无天日之际&#xff0c;被投喂了一个contenteditable 。试了一下&#xff0c;嗯... 乌龟看绿豆--对眼了。 div 加上 contenteditable 后便继承了inputEvent 开启输入模…

【“状态机” 解析UART不定长度的协议帧】

【“状态机” 解析UART不定长度的协议帧】 1. 数据帧格式2. 状态机原理3. 代码实现 通信设计中考虑协议的灵活性&#xff0c;经常把协议设计成“不定长度”。如果一个系统接收上述“不定长度”的协议帧&#xff0c;将会有一个挑战–如何高效接收与解析。一个实例如下图&#xf…

流量卡VS随身WIFI?手把手教你怎么选!流量卡和随身WiFi哪个好?流量卡和随身WiFi的区别!流量卡和随身WiFi哪个更划算?流量卡和随身WiFi怎么选?

出门在外&#xff0c;网络、流量已经成为了我们必不可少需要考虑的问题&#xff01;在选择如何获取大流量时&#xff0c;很多人都选择困难&#xff1a;是选择一张流量卡&#xff0c;还是一个随身WIFI&#xff1f; 今天&#xff0c;将从功能与形态、信号、适用场景、限制条件等多…