【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
《博主简介》
小伙伴们好,我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。
✌更多学习资源,可关注公-仲-hao:【阿旭算法与机器学习】,共同学习交流~
👍感谢小伙伴们点赞、关注!
《------往期经典推荐------》
一、AI应用软件开发实战专栏【链接】
二、机器学习实战专栏【链接】,已更新31期,欢迎关注,持续更新中~~
三、深度学习【Pytorch】专栏【链接】
四、【Stable Diffusion绘画系列】专栏【链接】
DFS
括号生成

| DFS class Solution: def generateParenthesis(self, n: int) -> List[str]: def DFS(left, right, s): if left == n and right == n: res.append(s) return if left < n: DFS(left+1,right,s+'(') if right < left: DFS(left,right + 1,s+')') res = [] DFS(0,0,'') return res BFS class Node: def __init__(self, left, right, s): self.left = left self.right = right self.s = s class Solution: def generateParenthesis(self, n: int) -> List[str]: # BFS写法 res = [] if n == 0: return res queue = [Node(n,n,'')] while queue: node = queue.pop(0) if node.left == 0 and node.right == 0: res.append(node.s) if node.left > 0: queue.append(Node(node.left-1, node.right, node.s+'(')) if node.right > 0 and node.right > node.left: queue.append(Node(node.left, node.right-1, node.s+')')) return res # 写法2: class Solution: def generateParenthesis(self, n: int) -> List[str]: # BFS写法 res = [] if n == 0: return res queue = [(n,n,'')] while queue: node = queue.pop(0) if node[0] == 0 and node[1] == 0: res.append(node[2]) if node[0] > 0: queue.append((node[0]-1, node[1], node[2]+'(')) if node[1] > 0 and node[1] > node[0]: queue.append((node[0], node[1]-1, node[2]+')')) return res |
通常搜索几乎都是用深度优先遍历(回溯算法)。
广度优先遍历,得自己编写结点类,显示使用队列这个数据结构。深度优先遍历的时候,就可以直接使用系统栈,在递归方法执行完成的时候,系统栈顶就把我们所需要的状态信息直接弹出,而无须编写结点类和显示使用栈。
将BFS写法中的pop(0)改为pop()即为深度优先的迭代形式。
对比迭代的BFS写法与递归的DFS写法,可以看到,BFS其实是将DFS的参数当做队列中的一个元素来进行处理罢了,其他的与DFS没有什么区别。
并查集
岛屿问题

| class Solution: def numIslands(self, grid: List[List[str]]) -> int: self.m = len(grid) self.n = len(grid[0]) res = 0 for i in range(self.m): for j in range(self.n): if grid[i][j] == '1': self.sink(i,j,grid) res += 1 return res
def sink(self, i, j, grid): grid[i][j] = '0' for ni,nj in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]: if 0<=ni<self.m and 0<=nj<self.n and grid[ni][nj] == '1': self.sink(ni,nj,grid) |
扫雷游戏

| # DFS class Solution: def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]: # DFS i, j = click row, col = len(board), len(board[0]) if board[i][j] == "M": board[i][j] = "X" return board # 计算空白快周围的雷数量 def cal(i, j): res = 0 for x in [1, -1, 0]: for y in [1, -1, 0]: if x == 0 and y == 0: continue if 0 <= i + x < row and 0 <= j + y < col and board[i + x][j + y] == "M": res += 1 return res def dfs(i, j): num = cal(i, j) if num > 0: board[i][j] = str(num) return board[i][j] = "B" for x in [1, -1, 0]: for y in [1, -1, 0]: if x == 0 and y == 0: continue nxt_i, nxt_j = i + x, j + y if 0 <= nxt_i < row and 0 <= nxt_j < col and board[nxt_i][nxt_j] == "E": dfs(nxt_i, nxt_j) dfs(i, j) return board # BFS class Solution: def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]: i, j = click row, col = len(board), len(board[0]) if board[i][j] == "M": board[i][j] = "X" return board # 计算空白块周围的雷数目 def cal(i, j): res = 0 for x in [1, -1, 0]: for y in [1, -1, 0]: if x == 0 and y == 0: continue if 0 <= i + x < row and 0 <= j + y < col and board[i + x][j + y] == "M": res += 1 return res def bfs(i, j): queue = [(i,j)] while queue: i, j = queue.pop(0) num = cal(i, j) if num > 0: board[i][j] = str(num) continue board[i][j] = "B" for x in [1, -1, 0]: for y in [1, -1, 0]: if x == 0 and y == 0: continue nxt_i, nxt_j = i + x, j + y if nxt_i < 0 or nxt_i >= row or nxt_j < 0 or nxt_j >= col: continue if board[nxt_i][nxt_j] == "E": queue.append((nxt_i, nxt_j)) board[nxt_i][nxt_j] = "B" # 主要是用于标识该点已经被访问过,防止后续重复的添加相同的‘E’点 bfs(i, j) return board |
关于本篇文章大家有任何建议或意见,欢迎在评论区留言交流!
觉得不错的小伙伴,感谢点赞、关注加收藏哦!
欢迎关注下方GZH:阿旭算法与机器学习,共同学习交流~
相关文章:
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
《博主简介》 小伙伴们好,我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。 ✌更多学习资源,可关注公-仲-hao:【阿旭算法与机器学习】,共同学习交流~ 👍感谢小伙伴们点赞、关注! 《------往期经典推荐--…...
字符设备驱动开发-注册-设备文件创建
一、字符设备驱动 linux系统中一切皆文件 1、应用层: APP1 APP2 ... fd open("led驱动的文件",O_RDWR); read(fd); write(); close(); 2、内核层: 对灯写一个驱动 led_driver.c driver_open(); driver_read(); driver_write(…...
TrustZone之可信操作系统
有许多可信内核,包括商业和开源的。一个例子是OP-TEE,最初由ST-Ericsson开发,但现在是由Linaro托管的开源项目。OP-TEE提供了一个功能齐全的可信执行环境,您可以在OP-TEE项目网站上找到详细的描述。 OP-TEE的结构如下图所示&…...
java定义三套场景接口方案
一、背景 在前后端分离开发的背景下,后端java开发人员现在只需要编写接口接口。特别是使用微服务开发的接口。resful风格接口。那么一般后端接口被调用有下面三种场景。一、不需要用户登录的接口调用,第二、后端管理系统接口调用(需要账号密…...
idea连接数据库,idea连接MySQL,数据库驱动下载与安装
文章目录 普通Java工程先创建JAVA工程JDBC连接数据库测试连接 可视化连接数据库数据库驱动下载与安装常用的数据库驱动下载MySQL数据库Oracle数据库SQL Server 数据库PostgreSQL数据库 下载MySQL数据库驱动JDBC连接各种数据库的连接语句MySQL数据库Oracle数据库DB2数据库sybase…...
Redis-实践知识
转自极客时间Redis 亚风 原文视频:https://u.geekbang.org/lesson/535?article681062 Redis最佳实践 普通KEY Redis 的key虽然可以自定义,但是最好遵循下面几个实践的约定: 格式:[业务名称]:[数据名]:[id] 长度不超过44字节 不…...
多维时序 | MATLAB实现SSA-CNN-SVM麻雀算法优化卷积神经网络-支持向量机多变量时间序列预测
多维时序 | MATLAB实现SSA-CNN-SVM麻雀算法优化卷积神经网络-支持向量机多变量时间序列预测 目录 多维时序 | MATLAB实现SSA-CNN-SVM麻雀算法优化卷积神经网络-支持向量机多变量时间序列预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 多维时序 | MATLAB实现…...
leetcode160相交链表思路解析
分别让tmp1以及tmp2的结点分别先指向headA以及headB,当遍历完成后,再让tmp1以及tmp2分别指向haedB和headA反转 此处有个问题:为什么if判断句中写tmp1!=nullptr,能够编译通过,但是写tmp1->ne…...
在线分析工具-日志优化
一、概述 针对于大日志文件,统计分析出日志文件的相关指标,帮助开发测试人员,优化日志打印。减少存储成本 二、日志分析指标 重复打印日志:统一请求reqId的重复打印日志打印最多的方法:检测出打印日志最多的方法…...
硬核实战!mysql 错误操作整个表全部数据后如何恢复?附解决过程、思路(百万行SQL,通过binlog日志恢复)
mysql 错误操作整个表全部数据后如何恢复?(百万行SQL,通过binlog日志恢复) 事件起因 事情起因:以为某个表里的数据都是系统配置的数据,没有用户数据,一个字段需要覆盖替换为新的url链接&#x…...
【什么是反射机制?为什么反射慢?】
✅ 什么是反射机制?为什么反射慢? ✅典型解析✅拓展知识仓✅反射常见的应用场景✅反射和Class的关系 ✅典型解析 反射机制指的是程序在运行时能够获取自身的信息。在iava中,只要给定类的名字,那么就可以通过反射机制来获得类的所有…...
PostGreSQL:货币类型
货币类型:money money类型存储固定小数精度的货币数字,小数的精度由数据库的lc_monetary设置决定。windows系统下,该配置项位于/data/postgresql.conf文件中,默认配置如下, lc_monetary Chinese (Simplified)_Chi…...
ESP8266网络相框采用TFT_eSPI库TJpg_Decoder库mixly库UDP库实现图片传送
用ESP8266和TFT_ESPI模块来显示图片数据。具体来说,我们将使用ILI9431显示器作为显示设备,并通过UDP协议将图片数据从发送端传输到ESP8266。最后,我们将解析这些数据并在TFT屏幕上显示出来。在这个过程中,我们将面临一些编程挑战&…...
Go 泛型发展史与基本介绍
Go 泛型发展史与基本介绍 Go 1.18版本增加了对泛型的支持,泛型也是自 Go 语言开源以来所做的最大改变。 文章目录 Go 泛型发展史与基本介绍一、为什么要加入泛型?二、什么是泛型三、泛型的来源四、为什么需要泛型五、Go 泛型设计的简史六、泛型语法6.1 …...
python 解决手机拍的书籍图片发灰的问题
老师给发的作业经常是手机拍的,而不是扫描,背景发灰,如果二次打印就没有看了,象这样: 如果使用photoshop 处理,有些地方还是扣不干净,不如python 做的好,处理后如下: 具体…...
【prompt一】Domain Adaptation via Prompt Learning
1.Motivation 当前的UDA方法通过对齐源和目标特征空间来学习域不变特征。这种对齐是由诸如统计差异最小化或对抗性训练等约束施加的。然而,这些约束可能导致语义特征结构的扭曲和类可辨别性的丧失。 在本文中,引入了一种新的UDA提示学习范式࿰…...
视频编辑与制作,添加视频封面的软件
如今,视频已经成为了我们生活中不可或缺的一部分,无论是社交媒体上的短视频,还是电影、电视剧,视频都以其独特的魅力吸引着我们的目光。而在这背后,视频剪辑软件功不可没。今天,我就为大家揭秘一款新一代的…...
Deepin更换仿Mac主题
上一篇博客说了要写一篇deepin系统的美化教程 先看效果图: 准备工作: 1.你自己 嘻嘻嘻 2.能上网的deepin15.11电脑 首先去下载主题 本次需要系统美化3部分:1.图标 2.光标 3.壁纸 开始之前,请先把你的窗口特效打开,…...
【Flink-Kafka-To-ClickHouse】使用 Flink 实现 Kafka 数据写入 ClickHouse
【Flink-Kafka-To-ClickHouse】使用 Flink 实现 Kafka 数据写入 ClickHouse 1)导入相关依赖2)代码实现2.1.resources2.1.1.appconfig.yml2.1.2.log4j.properties2.1.3.log4j2.xml2.1.4.flink_backup_local.yml 2.2.utils2.2.1.DBConn2.2.2.CommonUtils2.…...
浅谈Redis分布式锁(下)
作者简介:大家好,我是smart哥,前中兴通讯、美团架构师,现某互联网公司CTO 联系qq:184480602,加我进群,大家一起学习,一起进步,一起对抗互联网寒冬 自定义Redis分布式锁的…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
淘宝扭蛋机小程序系统开发:打造互动性强的购物平台
淘宝扭蛋机小程序系统的开发,旨在打造一个互动性强的购物平台,让用户在购物的同时,能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机,实现旋转、抽拉等动作,增…...
