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

【经典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与并查集:括号生成、岛屿问题、扫雷游戏

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推荐--…...

字符设备驱动开发-注册-设备文件创建

一、字符设备驱动 linux系统中一切皆文件 1、应用层&#xff1a; APP1 APP2 ... fd open("led驱动的文件"&#xff0c;O_RDWR); read(fd); write(); close(); 2、内核层&#xff1a; 对灯写一个驱动 led_driver.c driver_open(); driver_read(); driver_write(…...

TrustZone之可信操作系统

有许多可信内核&#xff0c;包括商业和开源的。一个例子是OP-TEE&#xff0c;最初由ST-Ericsson开发&#xff0c;但现在是由Linaro托管的开源项目。OP-TEE提供了一个功能齐全的可信执行环境&#xff0c;您可以在OP-TEE项目网站上找到详细的描述。 OP-TEE的结构如下图所示&…...

java定义三套场景接口方案

一、背景 在前后端分离开发的背景下&#xff0c;后端java开发人员现在只需要编写接口接口。特别是使用微服务开发的接口。resful风格接口。那么一般后端接口被调用有下面三种场景。一、不需要用户登录的接口调用&#xff0c;第二、后端管理系统接口调用&#xff08;需要账号密…...

idea连接数据库,idea连接MySQL,数据库驱动下载与安装

文章目录 普通Java工程先创建JAVA工程JDBC连接数据库测试连接 可视化连接数据库数据库驱动下载与安装常用的数据库驱动下载MySQL数据库Oracle数据库SQL Server 数据库PostgreSQL数据库 下载MySQL数据库驱动JDBC连接各种数据库的连接语句MySQL数据库Oracle数据库DB2数据库sybase…...

Redis-实践知识

转自极客时间Redis 亚风 原文视频&#xff1a;https://u.geekbang.org/lesson/535?article681062 Redis最佳实践 普通KEY Redis 的key虽然可以自定义&#xff0c;但是最好遵循下面几个实践的约定&#xff1a; 格式&#xff1a;[业务名称]:[数据名]:[id] 长度不超过44字节 不…...

多维时序 | MATLAB实现SSA-CNN-SVM麻雀算法优化卷积神经网络-支持向量机多变量时间序列预测

多维时序 | MATLAB实现SSA-CNN-SVM麻雀算法优化卷积神经网络-支持向量机多变量时间序列预测 目录 多维时序 | MATLAB实现SSA-CNN-SVM麻雀算法优化卷积神经网络-支持向量机多变量时间序列预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 多维时序 | MATLAB实现…...

leetcode160相交链表思路解析

分别让tmp1以及tmp2的结点分别先指向headA以及headB&#xff0c;当遍历完成后&#xff0c;再让tmp1以及tmp2分别指向haedB和headA反转 此处有个问题&#xff1a;为什么if判断句中写tmp1&#xff01;&#xff1d;nullptr&#xff0c;能够编译通过&#xff0c;但是写tmp1->ne…...

在线分析工具-日志优化

一、概述 针对于大日志文件&#xff0c;统计分析出日志文件的相关指标&#xff0c;帮助开发测试人员&#xff0c;优化日志打印。减少存储成本 二、日志分析指标 重复打印日志&#xff1a;统一请求reqId的重复打印日志打印最多的方法&#xff1a;检测出打印日志最多的方法…...

硬核实战!mysql 错误操作整个表全部数据后如何恢复?附解决过程、思路(百万行SQL,通过binlog日志恢复)

mysql 错误操作整个表全部数据后如何恢复&#xff1f;&#xff08;百万行SQL&#xff0c;通过binlog日志恢复&#xff09; 事件起因 事情起因&#xff1a;以为某个表里的数据都是系统配置的数据&#xff0c;没有用户数据&#xff0c;一个字段需要覆盖替换为新的url链接&#x…...

【什么是反射机制?为什么反射慢?】

✅ 什么是反射机制&#xff1f;为什么反射慢&#xff1f; ✅典型解析✅拓展知识仓✅反射常见的应用场景✅反射和Class的关系 ✅典型解析 反射机制指的是程序在运行时能够获取自身的信息。在iava中&#xff0c;只要给定类的名字&#xff0c;那么就可以通过反射机制来获得类的所有…...

PostGreSQL:货币类型

货币类型&#xff1a;money money类型存储固定小数精度的货币数字&#xff0c;小数的精度由数据库的lc_monetary设置决定。windows系统下&#xff0c;该配置项位于/data/postgresql.conf文件中&#xff0c;默认配置如下&#xff0c; lc_monetary Chinese (Simplified)_Chi…...

ESP8266网络相框采用TFT_eSPI库TJpg_Decoder库mixly库UDP库实现图片传送

用ESP8266和TFT_ESPI模块来显示图片数据。具体来说&#xff0c;我们将使用ILI9431显示器作为显示设备&#xff0c;并通过UDP协议将图片数据从发送端传输到ESP8266。最后&#xff0c;我们将解析这些数据并在TFT屏幕上显示出来。在这个过程中&#xff0c;我们将面临一些编程挑战&…...

Go 泛型发展史与基本介绍

Go 泛型发展史与基本介绍 Go 1.18版本增加了对泛型的支持&#xff0c;泛型也是自 Go 语言开源以来所做的最大改变。 文章目录 Go 泛型发展史与基本介绍一、为什么要加入泛型&#xff1f;二、什么是泛型三、泛型的来源四、为什么需要泛型五、Go 泛型设计的简史六、泛型语法6.1 …...

python 解决手机拍的书籍图片发灰的问题

老师给发的作业经常是手机拍的&#xff0c;而不是扫描&#xff0c;背景发灰&#xff0c;如果二次打印就没有看了&#xff0c;象这样&#xff1a; 如果使用photoshop 处理&#xff0c;有些地方还是扣不干净&#xff0c;不如python 做的好&#xff0c;处理后如下&#xff1a; 具体…...

【prompt一】Domain Adaptation via Prompt Learning

1.Motivation 当前的UDA方法通过对齐源和目标特征空间来学习域不变特征。这种对齐是由诸如统计差异最小化或对抗性训练等约束施加的。然而&#xff0c;这些约束可能导致语义特征结构的扭曲和类可辨别性的丧失。 在本文中&#xff0c;引入了一种新的UDA提示学习范式&#xff0…...

视频编辑与制作,添加视频封面的软件

如今&#xff0c;视频已经成为了我们生活中不可或缺的一部分&#xff0c;无论是社交媒体上的短视频&#xff0c;还是电影、电视剧&#xff0c;视频都以其独特的魅力吸引着我们的目光。而在这背后&#xff0c;视频剪辑软件功不可没。今天&#xff0c;我就为大家揭秘一款新一代的…...

Deepin更换仿Mac主题

上一篇博客说了要写一篇deepin系统的美化教程 先看效果图&#xff1a; 准备工作&#xff1a; 1.你自己 嘻嘻嘻 2.能上网的deepin15.11电脑 首先去下载主题 本次需要系统美化3部分&#xff1a;1.图标 2.光标 3.壁纸 开始之前&#xff0c;请先把你的窗口特效打开&#xff0c;…...

【Flink-Kafka-To-ClickHouse】使用 Flink 实现 Kafka 数据写入 ClickHouse

【Flink-Kafka-To-ClickHouse】使用 Flink 实现 Kafka 数据写入 ClickHouse 1&#xff09;导入相关依赖2&#xff09;代码实现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分布式锁(下)

作者简介&#xff1a;大家好&#xff0c;我是smart哥&#xff0c;前中兴通讯、美团架构师&#xff0c;现某互联网公司CTO 联系qq&#xff1a;184480602&#xff0c;加我进群&#xff0c;大家一起学习&#xff0c;一起进步&#xff0c;一起对抗互联网寒冬 自定义Redis分布式锁的…...

6541616

56465651...

使用git filter-repo删除已提交到git中的敏感信息,api key,配置文件等

使用git filter-repo删除已提交到git中的敏感信息&#xff0c;api key&#xff0c;配置文件等 前提条件 Python 3.5 git > 2.22.0通过 pip 安装&#xff1a;pip install git-filter-repo 注意事项 官方推荐在fresh clone上修改&#xff0c;即clone一份远程的再做修改 操作后…...

Cursor AI 代码助手规则引擎:定制化约束与团队协作实践

1. 项目概述&#xff1a;一个为 Cursor 编辑器量身定制的规则引擎如果你和我一样&#xff0c;深度依赖 Cursor 这款 AI 驱动的代码编辑器&#xff0c;那你一定遇到过这样的场景&#xff1a;面对一个复杂的重构任务&#xff0c;你向 Cursor 的 AI 助手&#xff08;无论是 Claude…...

打造极致氛围感编码环境:从视觉、听觉到工作流的全栈实践指南

1. 项目概述&#xff1a;当“氛围感”遇上“编码”&#xff0c;一个宝藏仓库的诞生如果你和我一样&#xff0c;是个对开发环境、工具流和“仪式感”有执念的程序员&#xff0c;那你肯定不止一次地折腾过自己的IDE主题、终端配色、字体&#xff0c;甚至桌面的壁纸和音乐。我们内…...

用Monster M4SK打造可穿戴互动眼睛:从硬件拆解到凯皮帽子制作

1. 项目概述&#xff1a;当马里奥的帽子“活”了过来如果你和我一样&#xff0c;既是任天堂游戏的粉丝&#xff0c;又对嵌入式硬件和可穿戴设备着迷&#xff0c;那么把游戏里的角色带到现实中来&#xff0c;绝对是一件充满乐趣的事。这次我们要“复活”的&#xff0c;是《超级马…...

书成紫微动,律定凤凰驯:海棠山铁哥,用两部作品走完了千年谶语的路

书成紫微动&#xff0c;律定凤凰驯。 ——千年谶语&#xff0c;今终圆满。一、悬在文脉上空的千年谶语“书成紫微动&#xff0c;律定凤凰驯”自诞生之日起&#xff0c;这句庙堂吉颂便高悬于华夏文脉之上&#xff0c;无人可触、无人能落。 文人墨客解其字&#xff0c;玄学爱好者…...

data-prep-kit:Python数据预处理工具包,自动化清洗、特征工程与流水线构建

1. 项目概述与核心价值最近在数据科学和机器学习社区里&#xff0c;一个名为data-prep-kit的项目开始引起不少同行的注意。如果你经常和数据打交道&#xff0c;无论是做数据分析、构建模型&#xff0c;还是搭建数据管道&#xff0c;你肯定对“数据准备”这个环节又爱又恨。爱的…...

量子计算中的辛基理论与MBQC实现

1. 量子计算中的辛基基础概念在量子计算领域&#xff0c;辛基&#xff08;Symplectic Basis&#xff09;是描述多量子比特系统的重要数学工具。它本质上是一个满足特定对易关系的基组&#xff0c;能够简洁地表示量子态和量子操作。理解辛基需要从有限域上的向量空间开始——具体…...

MongoDB避坑指南:电脑名含中文导致 Invalid UTF-8 string 报错的完美解决

前言最近在配置 MongoDB 本地环境时&#xff0c;遇到了一个非常“玄学”的报错。明明按照教程一步步安装&#xff0c;环境变量也配好了&#xff0c;但无论是启动服务&#xff0c;还是使用 MongoDB Compass 连接本地数据库&#xff0c;都会直接报错。排查了半天&#xff0c;最后…...

PP 蜂窝板生产线智能控制系统架构与 PLC 程序设计思路

PP 蜂窝板生产线智能控制系统架构与 PLC 程序设计思路摘要&#xff1a;针对 PP 蜂窝板产线多段速度同步、温度压力闭环、真空度稳定与定长裁切精度要求&#xff0c;本文介绍基于 PLCHMI 的智能控制系统整体架构&#xff0c;分模块阐述挤出温控、真空定型、牵引同步、在线测厚与…...