【寸铁的刷题笔记】图论、bfs、dfs

【寸铁的刷题笔记】图论、bfs、dfs

大家好 我是寸铁👊
金三银四图论基础结合bfsdfs是必考的知识点✨
快跟着寸铁刷起来!面试顺利上岸👋
喜欢的小伙伴可以点点关注 💝


🌞详见如下专栏🌞

🍀🍀🍀寸铁的刷题笔记🍀🍀🍀


200. 岛屿数量

考点

递归、dfs

思路

思路:遍历二维数组,遇到陆地则计数器加1
然后,向该陆地四个方向进行搜索。
遇到边界则停止搜索,如果搜索到的网格为陆地,则说明该网格和遍历到的陆地连通
同时,把该搜索到的陆地'1',置为海洋'0'
由于之前遍历二维数组时遇到陆地时计数器加1,由于连通,算作1个岛屿。
这样就避免下次遍历二维数组时重复遍历陆地,导致岛屿数量多算了。

代码

class Solution {
    /*
    思路:遍历二维数组,遇到陆地则计数器加1
    然后,向该陆地上、下、左、右四个方向进行搜索。
    遇到边界则停止搜索,如果搜索到的网格为陆地,则该网格和遍历到的陆地连通。
    同时,把该搜索到的陆地'1',置为海洋'0'
    由于之前遍历二维数组时遇到陆地时计数器加1,由于连通,算作1个岛屿。
    这样就避免下次遍历二维数组时,重复遍历陆地,导致岛屿数量多算了。
    */
    public int numIslands(char[][] grid) {
        int count = 0;//统计陆地的数量
        for(int i = 0; i < grid.length; i++){ //数组的行数
            for(int j = 0; j < grid[0].length; j++){//数组的列数
                if(grid[i][j] == '1'){//如果说遍历到的节点是陆地'1'
                     dfs(grid , i , j);//则调用递归函数将该陆地周围的陆地进行置0操作
                     count++;//陆地数量++   
                }      
          }
        }
    return count;//返回陆地的数量
    }

    public void dfs(char [][]grid , int i , int j){
        //边界条件,遇到边界则搜索停下来。
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0')return;
        //将陆地周围联通的陆地进行置0 , 避免重复遍历,统计陆地的数量不正确。
        grid[i][j] = '0';
        //向上、下、左、右四个方向进行遍历,把能走通的陆地进行置0,避免重复遍历。
        //上
        dfs(grid , i -1 , j);
        //下
        dfs(grid , i + 1 , j);
        //左
        dfs(grid , i , j - 1);
        //右
        dfs(grid , i , j + 1);
    }
}

130. 被围绕的区域

考点

递归、dfs

思路

题目描述

这道题是让我们寻找所有被X围绕的区域,并将这块区域中的所有的'OX进行填充。

转换问题

那么怎么样去寻找所有被X围绕的区域呢?
直接做肯定不好做,不妨反过来思考,什么样的才是不被X围绕的区域呢?


在这里插入图片描述

观察题目图形,我们发现如果O位于棋盘边界的位置,则说明O不被X所围绕,与外界连通。

那么问题就转换为去搜索从边界的O开始连通的O区域,这一部分连通的区域必定是不满足条件的,也就是不用替换为X的。
所以,我们从边界的位置出发,去搜索从边界的O开始连通的O区域,并把搜索过的O标记为*,避免后面被重复遍历

如下图绿色为棋盘的边界部分

在这里插入图片描述


复原操作

最后,对棋盘的字符进行复原操作,把标记的*复原为X
剩下的O则为被包围的区域,进行替换为X即可。


代码

class Solution {
    /*
    思路:
    这道题是让我们寻找所有被'X'围绕的区域,并将这块区域中的所有'O'用'X'进行填充。
    那么,怎么样去寻找所有被'X'围绕的区域呢?
    直接做肯定不好做,不妨反过来思考,什么样的才是不被'X'围绕的区域呢?
    观察图形,我们发现如果O位于棋盘边界的位置,则说明'O'不被'X'所围绕。
    那么问题就转换为去搜索从边界的'O'开始连通的'O'区域,这一部分连通的区域必定是不满足条件的,也就是不用替换为'X'的。
    所以,我们从边界的位置出发,去搜索从边界的'O'开始连通的'O'区域,并把搜索过的'O'标记为'*',避免后面被重复遍历。
    最后,对棋盘的字符进行复原操作,把标记的'*'复原为'X'。
    剩下的'O'则为被包围的区域,进行替换为'X'即可。
    */
    int m;//棋盘的行数
    int n;//棋盘的列数
    public void solve(char[][] board) {
        m = board.length;//行的长度
        n = board[0].length;//列的长度
        for(int i = 0; i < m; i++){
          dfs(board , i , 0);//每一行的第一个位置
          dfs(board , i , n - 1);//每一行的最后一个位置  
        }
        for(int i = 1; i < n - 1; i++){
            dfs(board , 0 , i);//第一行除了头尾之外的位置
            dfs(board , m - 1, i);//最后一行除了头尾之外的位置
        }
        //dfs处理完毕后,再进行棋盘复原操作
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                //如果说最后的棋盘为O 则直接进行赋值为X即可
                if(board[i][j] == 'O')board[i][j] = 'X';
                //把最后棋盘中与外界连通的标记 * 替换为 O
                else if(board[i][j] == '*')board[i][j] = 'O';
            }
        }
    }
    //寻找与外界棋盘O字符连通的区域
    public void dfs(char [][]board , int i , int j){
        //如果说越界了或者说之前被标记为'*'(已经被遍历过)或者是'X'则停止搜索
        if(i < 0 || j < 0 || i >= m || j >= n || board[i][j] == '*' || board[i][j] == 'X')return;
        board[i][j] = '*'; //标记为* 表示与外界连通并且这个位置已经被遍历过了,不再重复遍历。
        //上
        dfs(board , i - 1 , j);
        //下
        dfs(board , i + 1 , j);
        //左
        dfs(board , i , j - 1);
        //右
        dfs(board , i , j + 1);
    }
}

133. 克隆图

考点

哈希表、bfs

思路

思想: bfs,宽搜。
从起点节点开始出发,入队,出队,将该起点节点的邻接节点入队,并标记被搜索过(哈希表记录
再弹出当前队列的节点,入队,并继续标记其邻接节点。
依次一层一层的搜索下去,直至最后队列为,说明已经拷贝完图的所有节点。

代码

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    public Node cloneGraph(Node node) {
        /*
        思想:
        bfs,宽搜。
        从起点节点开始出发,入队,出队,将该起点节点的邻接节点入队,并标记被搜索过。
        再弹出当前队列的节点,入队,并继续标记其邻接节点。
        依次一层一层的搜索下去,直至最后队列为空,说明已经拷贝完图的所有节点。
        */
        if(node == null)return null;//空节点不拷贝
        Node []cloneNodes = new Node[110];//存储的是每一个已经拷贝(克隆)的节点,标记已被搜索过
        cloneNodes[node.val] = new Node(node.val);//克隆起点节点
        Queue<Node>queue = new LinkedList<>();//存储bfs的队列
        queue.offer(node); //起点节点入队
        Node cur; // 记录当前处理的节点
        while(!queue.isEmpty()){
            cur = queue.poll(); //从队列中获取一个待处理的节点
            Node cloneNode = cloneNodes[cur.val];//待处理的节点一定是克隆好的,直接获取其克隆节点
            for(Node neighbor : cur.neighbors){
                if(cloneNodes[neighbor.val] == null){
                    //如果邻接节点未拷贝则进行拷贝
                    cloneNodes[neighbor.val] = new Node(neighbor.val);
                    queue.offer(neighbor);//邻接节点入队,用于下一轮的节点获取。
                }
                //克隆节点的邻居添加入遍历过的拷贝节点的邻接节点
                cloneNode.neighbors.add(cloneNodes[neighbor.val]);
            }
        }
        //返回克隆节点的记录数组即可
        return cloneNodes[node.val];
    }
}

207. 课程表

考点

bfs、拓扑排序

思路

思想: 要想修一门课程,则需要先修它的先修课程。
所以, 我们可以把他看成是一个有向无环图
判断最后每个点是不是入度、出度为0节点数等于课程数即可。

做法

  1. 先将先修课程向要修课程连一条边,同时记录要修课程的入度

  2. 再统计每个点的入度,在bfs时,将待修课程节点的入度--

  3. 最后, 判断入度为0节点数是否等于课程数
    等于则说明可以完成所有课程的学习。
    不等于则说明存在,陷入死循环中,无法完成课程的学习。


代码

class Solution {
    /*
    思想: 要想修一门课程,则需要先修它的先修课程。
    所以, 我们可以把他看成是一个有向无环图。
    判断最后每个点是不是入度、出度为0的节点数等于课程数即可。
    先将先修课程向要修课程连一条边
    再统计每个点的入度,在bfs搜索时,将先修课程节点的出度--
    最后, 入读和出度都为0,则说明可以完成所有课程的学习。
    最后, 判断入度、出度为0的节点数是否等于课程数。
    等于则说明可以完成所有课程的学习。
    不等于则说明存在环,陷入死循环中,无法完成课程的学习。
    */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int []indegress = new int[numCourses];
        List<List<Integer>>adjacency = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; i++){
            adjacency.add(new ArrayList<>());
        }
        for(int []cp : prerequisites){
            //要想修0必须先修1
            //对0而言是入度,对1而言是出度
            indegress[cp[0]]++;//入度++
            //先修课程向要修课程向连一条边
            adjacency.get(cp[1]).add(cp[0]);
        }
        //寻找入度为0的点开始进行拓扑排序
        //入度为0则说明它是可以修的课程
        for(int i = 0; i < numCourses; i++){
            if(indegress[i] == 0)queue.add(i);
        }
        while(!queue.isEmpty()){
            //弹出入度为0的节点,说明该课程可以被修。
            int pre = queue.poll();
            //同时课程数量--
            numCourses--;
            //遍历先修课程的节点
            for(int cur : adjacency.get(pre)){
                //出度--
                //如果说点cur的入度与出度都为0
                //则队列中添加节点cur,用于下一轮的搜索。
                if(--indegress[cur] == 0){
                    queue.add(cur);
                }
            }
        }
        //最后,判断一下是不是课程数等于0
        //如果说课程数等于0 则代表可以完成所有课程的学习。
        return numCourses == 0;
    }
}

210. 课程表 II

考点

bfs、拓扑排序

思路

在课程表题目的基础上,多维护一个数组,用于记录当前弹出的节点的路径(走过的节点)
弹出的节点是入度0的节点,入度0说明为已修的先修课程,并且是先修完的,可以按照这个顺序来。

代码

class Solution {
    //在课程表题目的基础上,多维护一个数组,用于记录当前弹出的节点的路径
    //弹出的节点是入度为0的节点,入度为0说明为已修的先修课程,并且是先修完的,可以按照这个顺序来。
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int []indegress = new int[numCourses];//记录每个节点的入度
        List<List<Integer>>adjacency = new ArrayList<>();//维护一个列表用于存储边
        Queue<Integer>queue = new LinkedList<>();//创建队列,用于存储节点
        for(int i = 0; i < numCourses; i++){
            adjacency.add(new ArrayList<>());//每个节点先添加列表用于存连接的节点(边)
        }
        for(int []cp : prerequisites){
            indegress[cp[0]]++; //要修课程的入度++
            adjacency.get(cp[1]).add(cp[0]);
            //将先修课程和待修课程连一条边
            //用于后续遍历入度为0节点的队列将待修课程的入度--
            //用于下一轮的循环
        }
        //先将入度为0的节点添加入队列
        for(int i = 0; i < numCourses; i++){
            if(indegress[i] == 0)queue.add(i);
        }
        //创建数组ans,用于记录学完所有课程所安排的学习顺序。
        int ans[] = new int[numCourses];
        int index = 0;//数组下标,用于存储学完的课程
        while(!queue.isEmpty()){
            int pre = queue.poll();
            ans[index++]=pre;//入度为0的节点是确保能够修完的先修课程,存到结果数组中。
            for(int cur : adjacency.get(pre)){//将每个待修课程的入度--
                if(--indegress[cur] == 0){
                    queue.add(cur);//入度为0则入队
                }
            }
        }
        
        //最后的结果是入度均为0
        //如果说某个节点的入度 > 0 , 则说明不可能修完全部课程, 存在一个环。
        //如[[0,1],[1,0]]
        //这里无法找到一个入度为0的节点,存在一个环。
        for(int i = 0; i < indegress.length; i++){
            if(indegress[i] > 0)return new int[0];//返回一个空数组即可
        }
        //等价写法如下:
     //如果说index不等于课程数量,则说明存在入度不为0的点,也就是环。
        // if(index != numCourses){
        //     return new int[0];
        // } 
        return ans;//返回结果数组
    }
}

看到这里的小伙伴,恭喜你又掌握了一个技能👊
希望大家能取得胜利,坚持就是胜利💪
我是寸铁!我们下期再见💕

往期好文💕

保姆级教程

【保姆级教程】Windows11下go-zero的etcd安装与初步使用

【保姆级教程】Windows11安装go-zero代码生成工具goctl、protoc、go-zero

【Go-Zero】手把手带你在goland中创建api文件并设置高亮


报错解决

【Go-Zero】Error: user.api 27:9 syntax error: expected ‘:‘ | ‘IDENT‘ | ‘INT‘, got ‘(‘ 报错解决方案及api路由注意事项

【Go-Zero】Error: only one service expected goctl一键转换生成rpc服务错误解决方案

【Go-Zero】【error】 failed to initialize database, got error Error 1045 (28000):报错解决方案

【Go-Zero】Error 1045 (28000): Access denied for user ‘root‘@‘localhost‘ (using password: YES)报错解决方案

【Go-Zero】type mismatch for field “Auth.AccessSecret“, expect “string“, actual “number“报错解决方案

【Go-Zero】Error: user.api 30:2 syntax error: expected ‘)‘ | ‘KEY‘, got ‘IDENT‘报错解决方案

【Go-Zero】Windows启动rpc服务报错panic:context deadline exceeded解决方案


Go面试向

【Go面试向】defer与time.sleep初探

【Go面试向】defer与return的执行顺序初探

【Go面试向】Go程序的执行顺序

【Go面试向】rune和byte类型的认识与使用

【Go面试向】实现map稳定的有序遍历的方式

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

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

相关文章

微信小程序 获取openId - 成功获取

1.点击云开发配置里面的信息 2-基础信息配置结束之后 - 新建一个云函数 - 名字自定义但是要记住&#xff0c;这里定义为login3.保存成功之后出现这个 代表成功 - 这个弹窗可以关闭了 4.定义一个方法 name:login, 这里需要修改成对应的 是刚才上面定义的云函数名称 info()…

博途PLC 单通气缸功能块(SCL源代码)

气缸是工业现场应用非常多的一个重要执行器,气缸在很多场合都有大量应用,今天我们的对象就是"单通气缸",不同的工程师,不同的应用行业,大家对气缸功能块的封装会有所不同。气缸功能块的其它封装大家可以参看下面文章 1、气缸功能块 https://rxxw-control.blog…

mac打不开xxx软件, 因为apple 无法检查其是否包含恶意

1. 安全性与隐私下面的允许来源列表&#xff0c;有些版本中的‘任何来源’选项被隐藏了&#xff0c;有些从浏览器下载的软件需要勾选这个选项才能安装 打开‘任何来源’选项 sudo spctl --master-disable 关闭‘任何来源’选项 sudo spctl --master-enable

DVWA 靶场之 Command Injection(命令执行)原理介绍、分隔符测试、后门写入与源码分析、修复建议

在打靶之前我们需要先解决一个乱码问题 参考我之前的博客&#xff1a; 关于DVWA靶场Command Injection&#xff08;命令注入&#xff09;乱码的解决方案-CSDN博客 简单介绍一下命令执行漏洞&#xff1a; 命令执行漏洞是一种常见的网络安全漏洞&#xff0c;它允许攻击者通过向应…

微服务-商城订单服务项目

文章目录 一、需求二、分析三、设计四、编码4.1 商品服务4.2 订单服务4.3 分布式事务4.4 订单超时 商品、购物车 商品服务&#xff1a; 1.全品类购物平台 SPU:Standard Product Unit 标准化产品单元。是商品信息聚合的最小单位。是一组可复用、易检索的标准化信息的集合&#x…

Biotin-PEG2-Thiol,生物素-PEG2-巯基,应用于抗体标记、蛋白质富集等领域

您好&#xff0c;欢迎来到新研之家 文章关键词&#xff1a;Biotin-PEG2-Thiol&#xff0c;生物素-PEG2-巯基&#xff0c;Biotin PEG2 Thiol&#xff0c;生物素 PEG2 巯基 一、基本信息 【产品简介】&#xff1a;Biotin PEG2 Thiol can bind with antibodies to prepare biot…

第12课-在网络上写作,让你事半功倍的14个独家秘诀

公众号文章写作方向要专一&#xff0c;太杂的内容很难留住用户&#xff0c;这就要求我们早起尽快确定自己擅长的领域&#xff0c;然后不断精进。 在写作的过程中确定自己的写作风格&#xff0c;而写作风格的确立需要长时间的写作积累&#xff0c;会经历迷茫和混乱&#xff0c;…

数据库管理-第156期 Oracle Vector DB AI-07(20240227)

数据库管理156期 2024-02-27 数据库管理-第156期 Oracle Vector DB & AI-07&#xff08;20240227&#xff09;1 Vector相关DDL操作可以在现有的表上新增vector数据类型的字段&#xff1a;可以删除包含vector数据类型的列&#xff1a;可以使用CTAS的方式&#xff0c;从其他有…

centos7系统crond 离线安装

CentOS 7的crond离线安装步骤如下&#xff1a; 下载cronie和crontabs的离线安装包。可以从rpmfind等网站下载与CentOS 7系统版本相匹配的cronie和crontabs离线安装包。 将下载的离线安装包传输到CentOS 7服务器上。 依次执行以下命令进行安装&#xff1a; 安装cronie&#…

【喜讯】优积科技获上海市室内装饰行业“装配式装修示范单位”

2023年12月29日下午&#xff0c;上海市室内装饰行业协会第九届第三次会员大会暨第五次理事会在金茂大厦隆重举行。上海市民政局社会团体管理处副处长姜琦、上海市经济和信息化委员会综合规划处副处长赵广君、上海市工经联党委副书记、执行副会长黄国伟等领导应邀出席会议。出席…

CSS3技巧37:JS+CSS3 制作旋转图片墙

开学了就好忙啊&#xff0c;Three.js 学习的进度很慢。。。 备课备课才是王道。 更一篇 JS CSS3 的内容&#xff0c;做一个图片墙。 其核心要点是把图片摆成这个样子&#xff1a; 看上去这个布局很复杂&#xff0c;其实很简单。其思路是&#xff1a; 所有图片放在一个 div.…

kubectl 声明式资源管理方式

目录 介绍 YAML 语法格式 命令 应用yaml文件指定的资源 删除yaml文件指定的资源 查看资源的yaml格式信息 查看yaml文件字段说明 查看 api 资源版本标签 修改yaml文件指定的资源 离线修改 在线修改 编写yaml文件 创建资源对象 查看创建的pod资源 创建service服务对…

07-Linux部署Nginx

Linux部署Nginx 简介 NGINX是一款高性能的HTTP和反向代理服务器&#xff0c;也是一个IMAP/POP3/SMTP代理服务器。它的特点包括占用内存少、并发能力强&#xff0c;因此在处理高负载和高并发的场景时表现优秀。NGINX由俄罗斯的程序设计师Igor Sysoev开发&#xff0c;最初是为俄…

Swagger3 使用详解

Swagger3 使用详解 一、简介1 引入依赖2 开启注解3 增加一个测试接口4 启动服务报错1.5 重新启动6 打开地址&#xff1a;http://localhost:8093/swagger-ui/index.html 二、Swagger的注解1.注解Api和ApiOperation2.注解ApiModel和ApiModelProperty3.注解ApiImplicitParams和Api…

如何在 Linux 上使用 dmesg 命令

文章目录 1. Overview2.ring buffer怎样工作&#xff1f;3.dmesg命令4.移除sudo需求5. 强制彩色输出6.使用人性化的时间戳7.使用dmesg的人性化可读时间戳8.观察实时event9.检索最后10条消息10.搜索特定术语11.使用Log Levels12.使用Facility Categories13.Combining Facility a…

【六袆-Golang】Golang:安装与配置Delve进行Go语言Debug调试

安装与配置Delve进行Go语言Debug调试 一、Delve简介二、win-安装Delve三、使用Delve调试Go程序[命令行的方式]四、使用Golang调试程序 Golang开发工具系列&#xff1a;安装与配置Delve进行Go语言Debug调试 摘要&#xff1a; 开发环境中安装和配置Delve&#xff0c;一个强大的G…

黑马程序员——接口测试——day03——Postman断言、关联、参数化

目录&#xff1a; Potman断言 Postman断言简介Postman常用断言 断言响应状态码断言包含某字符串断言JSON数据Postman断言工作原理Postman关联 简介实现步骤核心代码创建环境案例1案例2Postman参数化 简介数据文件简介编写数据文件 CSV文件JSON文件导入数据文件到postman读取数…

C语言-数据结构-顺序表

&#x1f308;个人主页: 会编辑的果子君 &#x1f4ab;个人格言:“成为自己未来的主人~” 目录 数据结构相关概念 顺序表 顺序表的概念和结构 线性表 顺序表分类 顺序表和数组的区别 顺序表分类 静态顺序表 动态顺序表 头插和尾插 尾插 数据结构相关概念 数据结构…

逆向案例二:关键字密文解密,自定义的加密解密。基于企名片科技的爬取。

import requests import execjsfor i in range(4):i i1url https://vipapi.qimingpian.cn/Activity/channelInformationByChannelNamedata {channel_name: 24新声,page: f{i},num: 20,unionid: W9wLD4rHIZrB3GLTUncmHgbZcEepR78xJa5Zit6XTMtata86DehdxDt/fDbcHeeJWqqIs6k…

Golang Redis:构建高效和可扩展的应用程序

利用Redis的闪电般的数据存储和Golang的无缝集成解锁协同效应 在当前的应用程序开发中&#xff0c;高效的数据存储和检索的必要性已经变得至关重要。Redis&#xff0c;作为一个闪电般快速的开源内存数据结构存储方案&#xff0c;为各种应用场景提供了可靠的解决方案。在这份完…