(补)算法刷题Day24: BM61 矩阵最长递增路径
题目链接
思路
方法一:dfs暴力回溯
使用原始used数组+4个方向遍历框架 =, 全局添加一个最大值判断最大的路径长度。
方法二:加上dp数组记忆的优雅回溯
抛弃掉used数组,使用dp数组来记忆遍历过的节点的最长递增路径长度。每遍历到已经记录过的坐标,就直接返回即可。
方法一代码
import copy
max_result_len = -1
result = []
direct = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def dfs(matrix, used, row_n, col_m, x, y, path):# 判断是否合法global max_result_lenglobal resultif len(path) > max_result_len:max_result_len = len(path)print(max_result_len)print(path)result = copy.deepcopy(path)if x < 0 or y < 0 or x >= row_n or y >= col_m:returnif used[x][y]:return# 如果当前节点值是小于前一个,则passif matrix[x][y] <= path[-1]:returnused[x][y] = Truepath.append(matrix[x][y])for dx, dy in direct:nx = x + dxny = y + dydfs(matrix, used, row_n, col_m, nx, ny, path)used[x][y] = Falsepath.pop()
class Solution:def solve(self, matrix: List[List[int]]) -> int:# write code hererow = len(matrix)col = len(matrix[0])used = [[False for _ in range(row)] for _ in range(col)]for i in range (row):for j in range (col):dfs(matrix, used, row, col, i, j, [-1])return max_result_len-1
方法二代码
direct = [(-1, 0), (1, 0), (0, -1), (0, 1)]def dfs(matrix, row_n, col_m, x, y, path,dp):# 判断是否合法if x < 0 or y < 0 or x >= row_n or y >= col_m:return 0# 如果当前节点值是小于前一个,则passif matrix[x][y] <= path[-1]:return 0# 如果 dp 记录过就直接加上if dp[x][y] != -1:return dp[x][y]path.append(matrix[x][y])my_max = -1for dx, dy in direct:nx = x + dxny = y + dysub_max = dfs(matrix, row_n, col_m, nx, ny, path,dp)my_max = max(sub_max,my_max)path.pop()dp[x][y] = my_max+1return my_max+1
class Solution:def solve(self, matrix: List[List[int]]) -> int:row = len(matrix)col = len(matrix[0])dp = [[-1 for _ in range(row)]for _ in range(col)]max_result_len = -1for i in range(row):for j in range(col):m = dfs(matrix,row, col, i, j, [-1],dp)max_result_len = max(max_result_len, m)return max_result_len
这道题的dp卡了我很久。让我好几天都没有刷题的欲望。在需要机械化完成的任务面前,情绪更多时候真的是没用的东西。反正都要做的,早做晚做都是要做,开心也要做不开心也要做,倒不如不怀情绪地认真做。别急~
相关文章:
(补)算法刷题Day24: BM61 矩阵最长递增路径
题目链接 思路 方法一:dfs暴力回溯 使用原始used数组4个方向遍历框架 , 全局添加一个最大值判断最大的路径长度。 方法二:加上dp数组记忆的优雅回溯 抛弃掉used数组,使用dp数组来记忆遍历过的节点的最长递增路径长度。每遍历到已…...
探索 Bokeh:轻松创建交互式数据可视化的强大工具
探索 Bokeh:轻松创建交互式数据可视化的强大工具 在数据科学和数据分析领域,交互式数据可视化是一项不可或缺的技能。Bokeh 是一个强大的 Python 库,它可以帮助我们快速构建高质量的交互式图表和仪表盘,同时兼具高性能和灵活性。…...
【Rust自学】6.1. 定义枚举
喜欢的话别忘了点赞、收藏加关注哦,对接下来的教程有兴趣的可以关注专栏。谢谢喵!(・ω・) 6.1.1. 什么是枚举 枚举允许我们列举所有可能的值来定义一个类型。这与其他编程语言中的枚举类似,但 Rust 的枚举更加灵活和强…...
【Java基础面试题035】什么是Java泛型的上下界限定符?
回答重点 Java泛型的上下界限定符用于对泛型类型参数进行范围限制,主要有上界限定符和下届限定符。 1)上界限定符 (? extends T): 定义:通配符?的类型必须是T或者T的子类,保证集合元素一定是T或者T的子类作用&…...
0基础学前端系列 -- 深入理解 HTML 布局
在现代网页设计中,布局是至关重要的一环。良好的布局不仅能提升用户体验,还能使内容更具可读性和美观性。HTML(超文本标记语言)结合 CSS(层叠样式表)为我们提供了多种布局方式。本文将详细介绍流式布局、Fl…...
【python高级】342-TCP服务器开发流程
CS模式:客户端-服务端模式 TCP客户端开发流程介绍(五步)(C端) 1.创建客户端套接字对象 2.和服务端套接字建立连接 3.发送数据 4.接收数据 5.关闭客户端套接字 TCP服务端开发流程(七步)…...
《计算机组成及汇编语言原理》阅读笔记:p48-p81
《计算机组成及汇编语言原理》学习第 4 天,p48-p81 总结,总计 34 页。 一、技术总结 1.CISC vs RISC p49, complex instruction set computing For example, a complex instruction set computing (CISC) chip may be able to move a lar…...
AI在传统周公解梦中的技术实践与应用
本文深入探讨了人工智能在传统周公解梦领域的技术实践与应用。首先介绍了传统周公解梦的背景与局限性,随后详细阐述了 AI 技术如何应用于梦境数据的采集、整理与分析,包括自然语言处理技术对梦境描述的理解,机器学习算法构建解梦模型以及深度…...
GIS数据处理/程序/指导,街景百度热力图POI路网建筑物AOI等
简介其他数据处理/程序/指导!!!(1)街景数据获取(2)街景语义分割后像素提取,指标计算代码(绿视率,天空开阔度、视觉熵/景观多样性等)(3…...
ssr实现方案
目录 序言 一、流程 二、前端要做的事情 三、节点介绍 四、总结 序言 本文不是详细的实现过程,是让你最快最直接的理解ssr的真正实现方法,有前端经验的同学,能够很好的理解过程,细节根据具体项目实现 一、前端要做的事情 1.…...
手动修改nginx-rtmp模块,让nginx-rtmp-module支持LLHLS
文章目录 1. 背景2. 开发环境搭建2.1 ffmpeg在ubuntu上安装2.2 nginx-rtmp-module在ubuntu上安装2.3 安装vscode环境2. 修改nginx-rtmp-module2.1 主要更新内容2.2 新增配置项2.3 代码更新3. LLHLS验证方法3.1 配置验证3.2 功能验证4. 注意事项5. 已知问题6. 后续计划1. 背景 …...
gitee别人仓库再上传自己仓库
一、新建一个自己的Git仓库 如果没有注册账号的朋友,可以先去注册一个Gitee的账号,用于管理自己的代码特别好用!!! 接下来就是在gitee上新建一个自己的仓库,如下图所示 二、右建 Git Bush Here删除.git文件…...
create-react-app 创建react项目报错 ERESOLVE unable to resolve dependency tree
会报下面这样一个错误,这个错误以前是没有的,最近才出现这个错误。这个非常的蛋疼,意思是testing-library这个库的版本需要react18,但现在安装的是react19。 create-react-app的github是有这个issue的,但官方好像没给…...
从git上下载的项目不完整,关于git lfs
文章目录 问题一、git lfs是什么?二、如何获取git lfs中的文件1.安装 Git LFS2.下载文件 问题 在git上下载的项目无法执行,打开相关文件后发现如下内容: git lfs pull version https://git-lfs.github.com/spec/v1 oid sha256:00920b6723bb39321eea748fd96279f8a…...
sqlite3,一个轻量级的 C++ 数据库库!
宝子们,今天咱来唠唠 sqlite3 这个超棒的轻量级 C 数据库库。它就像是一个小巧但功能齐全的“数据仓库”,能帮咱们轻松地存储、查询和管理数据,无论是开发小型的桌面应用,还是做一些简单的数据处理程序,它都能派上大用…...
Pytorch | 从零构建ParNet/Non-Deep Networks对CIFAR10进行分类
Pytorch | 从零构建ParNet/Non-Deep Networks对CIFAR10进行分类 CIFAR10数据集ParNet架构特点优势应用 ParNet结构代码详解结构代码代码详解SSEParNetBlock 类DownsamplingBlock 类FusionBlock 类ParNet 类 训练过程和测试结果代码汇总parnet.pytrain.pytest.py 前面文章我们构…...
验证 Dijkstra 算法程序输出的奥秘
一、引言 Dijkstra 算法作为解决图中单源最短路径问题的经典算法,在网络路由、交通规划、资源分配等众多领域有着广泛应用。其通过不断选择距离源节点最近的未访问节点,逐步更新邻居节点的最短路径信息,以求得从源节点到其他所有节点的最短路径。在实际应用中,确保 Dijkst…...
二叉树的最小深度
最小深度思路解析: 与求最大深度相比,求最小深度就要简单很多,从上向下访问,只要访问到一个叶节点,证明已经到达了与根节点距离最近的叶节点处,此叶节点的深度即为最小深度.借助队列,如果当前节点为叶节点,则返回该节点的深度为最终结果;如果当前节点不满足上述判断且不为空节…...
C#+OpenCv深度学习开发(常用模型汇总)
在使用 OpenCvSharp 结合深度学习进行机器视觉开发时,有许多现成的模型可以使用。以下是一些常用的深度学习模型,适用于不同的机器视觉任务,包括物体检测、图像分类和分割等。 使用示例 在 OpenCvSharp 中加载和使用这些模型的基本示例&…...
什么样的LabVIEW控制算自动控制?
自动控制是指系统通过预先设计的算法和逻辑,在无人工干预的情况下对被控对象的状态进行实时监测、决策和调整,达到预期目标的过程。LabVIEW作为一种图形化编程工具,非常适合开发自动控制系统。那么,什么样的LabVIEW控制算作“自动…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...
