当前位置: 首页 > 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分布式锁的…...

研扬EPIC-RPS9工控主板解析:4英寸板载13代酷睿,赋能边缘AI与机器视觉

1. 项目概述&#xff1a;当“小钢炮”遇上工业严苛环境在工业自动化、边缘计算和嵌入式视觉这些领域里&#xff0c;我们常常面临一个经典矛盾&#xff1a;既要强大的算力来处理海量数据、运行复杂算法&#xff0c;又要设备足够紧凑、坚固&#xff0c;能塞进各种空间受限、环境恶…...

基于规则引擎的自动化文件管理工具smartcat实战指南

1. 项目概述&#xff1a;一个智能化的文件分类与归档工具最近在整理个人电脑和服务器上的文件时&#xff0c;我又一次陷入了混乱。下载文件夹里塞满了各种格式的文档、图片、压缩包&#xff0c;项目目录下混杂着不同版本的代码、设计稿和会议记录。手动分类不仅耗时&#xff0c…...

Blender MMD插件终极指南:三步实现专业级MMD模型制作

Blender MMD插件终极指南&#xff1a;三步实现专业级MMD模型制作 【免费下载链接】blender_mmd_tools MMD Tools is a blender addon for importing/exporting Models and Motions of MikuMikuDance. 项目地址: https://gitcode.com/gh_mirrors/bl/blender_mmd_tools 想…...

GeoJSON世界地图数据实战指南:从数据获取到高级可视化

GeoJSON世界地图数据实战指南&#xff1a;从数据获取到高级可视化 【免费下载链接】world.geo.json Annotated geo-json geometry files for the world 项目地址: https://gitcode.com/gh_mirrors/wo/world.geo.json 想要构建专业级的地理信息可视化应用却苦于找不到高质…...

基于LLM的MUD游戏AI智能体框架:从感知-思考-行动循环到工程实践

1. 项目概述&#xff1a;一个面向MUD游戏的智能体框架最近在折腾AI智能体&#xff08;Agent&#xff09;相关的项目&#xff0c;发现了一个挺有意思的仓库&#xff1a;zn0nz/mud_agent。乍一看名字&#xff0c;可能很多朋友会有点懵&#xff0c;MUD是什么&#xff1f;Agent又怎…...

Linux内核构建自动化:jpoindexter/kern工具实战指南

1. 项目概述&#xff1a;一个被低估的Linux内核构建工具 如果你和我一样&#xff0c;长期在嵌入式开发、内核模块调试或者需要频繁定制Linux内核的岗位上工作&#xff0c;那么你一定对内核的配置、编译、打包这一套繁琐的流程感到又爱又恨。爱的是&#xff0c;这是深入理解操作…...

零中频接收机技术演进与动态范围优化方案

1. 零中频接收机技术演进与核心挑战零中频架构&#xff08;Zero-IF&#xff09;在移动通信领域已发展超过二十年&#xff0c;最早可追溯至1990年代的GSM手机设计。这种直接将射频信号下变频至基带的技术&#xff0c;相比传统超外差架构省去了中频处理环节&#xff0c;理论上具有…...

未来是神经-符号的:AI 推理是如何演变的

原文&#xff1a;towardsdatascience.com/the-future-is-neuro-symbolic-how-ai-reasoning-is-evolving-143ce6485b4f 人工智能软件被用于增强本文文本的语法、流畅性和可读性。 一个名为AlphaGeometry的显著新 AI 系统最近解决了大多数人类都难以解决的困难高中水平数学问题。…...

开源机械爪资源库指南:从入门到ROS集成与自主抓取

1. 项目概述&#xff1a;一个开源“机械爪”的宝藏资源库如果你对机器人、自动化或者DIY硬件感兴趣&#xff0c;最近又在琢磨着给自己的项目加一个“手”&#xff0c;那么你很可能已经听说过“机械爪”这个概念。无论是想做一个自动抓取小物件的桌面机器人&#xff0c;还是为你…...

为什么顶尖考古团队已弃用传统文献管理?NotebookLM实现遗址报告生成效率提升300%的底层逻辑

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;NotebookLM考古学研究辅助的范式革命 NotebookLM 作为 Google 推出的基于文档理解的 AI 助手&#xff0c;正悄然重塑考古学研究的信息处理范式。传统考古工作依赖大量手写笔记、田野报告、碳十四测年数…...