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

(补)算法刷题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 矩阵最长递增路径

题目链接 思路 方法一&#xff1a;dfs暴力回溯 使用原始used数组4个方向遍历框架 &#xff0c; 全局添加一个最大值判断最大的路径长度。 方法二&#xff1a;加上dp数组记忆的优雅回溯 抛弃掉used数组&#xff0c;使用dp数组来记忆遍历过的节点的最长递增路径长度。每遍历到已…...

探索 Bokeh:轻松创建交互式数据可视化的强大工具

探索 Bokeh&#xff1a;轻松创建交互式数据可视化的强大工具 在数据科学和数据分析领域&#xff0c;交互式数据可视化是一项不可或缺的技能。Bokeh 是一个强大的 Python 库&#xff0c;它可以帮助我们快速构建高质量的交互式图表和仪表盘&#xff0c;同时兼具高性能和灵活性。…...

【Rust自学】6.1. 定义枚举

喜欢的话别忘了点赞、收藏加关注哦&#xff0c;对接下来的教程有兴趣的可以关注专栏。谢谢喵&#xff01;(&#xff65;ω&#xff65;) 6.1.1. 什么是枚举 枚举允许我们列举所有可能的值来定义一个类型。这与其他编程语言中的枚举类似&#xff0c;但 Rust 的枚举更加灵活和强…...

【Java基础面试题035】什么是Java泛型的上下界限定符?

回答重点 Java泛型的上下界限定符用于对泛型类型参数进行范围限制&#xff0c;主要有上界限定符和下届限定符。 1&#xff09;上界限定符 (? extends T)&#xff1a; 定义&#xff1a;通配符?的类型必须是T或者T的子类&#xff0c;保证集合元素一定是T或者T的子类作用&…...

0基础学前端系列 -- 深入理解 HTML 布局

在现代网页设计中&#xff0c;布局是至关重要的一环。良好的布局不仅能提升用户体验&#xff0c;还能使内容更具可读性和美观性。HTML&#xff08;超文本标记语言&#xff09;结合 CSS&#xff08;层叠样式表&#xff09;为我们提供了多种布局方式。本文将详细介绍流式布局、Fl…...

【python高级】342-TCP服务器开发流程

CS模式&#xff1a;客户端-服务端模式 TCP客户端开发流程介绍&#xff08;五步&#xff09;&#xff08;C端&#xff09; 1.创建客户端套接字对象 2.和服务端套接字建立连接 3.发送数据 4.接收数据 5.关闭客户端套接字 TCP服务端开发流程&#xff08;七步&#xff09;&#xf…...

《计算机组成及汇编语言原理》阅读笔记:p48-p81

《计算机组成及汇编语言原理》学习第 4 天&#xff0c;p48-p81 总结&#xff0c;总计 34 页。 一、技术总结 1.CISC vs RISC p49&#xff0c; complex instruction set computing For example, a complex instruction set computing (CISC) chip may be able to move a lar…...

AI在传统周公解梦中的技术实践与应用

本文深入探讨了人工智能在传统周公解梦领域的技术实践与应用。首先介绍了传统周公解梦的背景与局限性&#xff0c;随后详细阐述了 AI 技术如何应用于梦境数据的采集、整理与分析&#xff0c;包括自然语言处理技术对梦境描述的理解&#xff0c;机器学习算法构建解梦模型以及深度…...

GIS数据处理/程序/指导,街景百度热力图POI路网建筑物AOI等

简介其他数据处理/程序/指导&#xff01;&#xff01;&#xff01;&#xff08;1&#xff09;街景数据获取&#xff08;2&#xff09;街景语义分割后像素提取&#xff0c;指标计算代码&#xff08;绿视率&#xff0c;天空开阔度、视觉熵/景观多样性等&#xff09;&#xff08;3…...

ssr实现方案

目录 序言 一、流程 二、前端要做的事情 三、节点介绍 四、总结 序言 本文不是详细的实现过程&#xff0c;是让你最快最直接的理解ssr的真正实现方法&#xff0c;有前端经验的同学&#xff0c;能够很好的理解过程&#xff0c;细节根据具体项目实现 一、前端要做的事情 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仓库 如果没有注册账号的朋友&#xff0c;可以先去注册一个Gitee的账号&#xff0c;用于管理自己的代码特别好用&#xff01;&#xff01;&#xff01; 接下来就是在gitee上新建一个自己的仓库&#xff0c;如下图所示 二、右建 Git Bush Here删除.git文件…...

create-react-app 创建react项目报错 ERESOLVE unable to resolve dependency tree

会报下面这样一个错误&#xff0c;这个错误以前是没有的&#xff0c;最近才出现这个错误。这个非常的蛋疼&#xff0c;意思是testing-library这个库的版本需要react18&#xff0c;但现在安装的是react19。 create-react-app的github是有这个issue的&#xff0c;但官方好像没给…...

从git上下载的项目不完整,关于git lfs

文章目录 问题一、git lfs是什么&#xff1f;二、如何获取git lfs中的文件1.安装 Git LFS2.下载文件 问题 在git上下载的项目无法执行,打开相关文件后发现如下内容: git lfs pull version https://git-lfs.github.com/spec/v1 oid sha256:00920b6723bb39321eea748fd96279f8a…...

sqlite3,一个轻量级的 C++ 数据库库!

宝子们&#xff0c;今天咱来唠唠 sqlite3 这个超棒的轻量级 C 数据库库。它就像是一个小巧但功能齐全的“数据仓库”&#xff0c;能帮咱们轻松地存储、查询和管理数据&#xff0c;无论是开发小型的桌面应用&#xff0c;还是做一些简单的数据处理程序&#xff0c;它都能派上大用…...

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 结合深度学习进行机器视觉开发时&#xff0c;有许多现成的模型可以使用。以下是一些常用的深度学习模型&#xff0c;适用于不同的机器视觉任务&#xff0c;包括物体检测、图像分类和分割等。 使用示例 在 OpenCvSharp 中加载和使用这些模型的基本示例&…...

什么样的LabVIEW控制算自动控制?

自动控制是指系统通过预先设计的算法和逻辑&#xff0c;在无人工干预的情况下对被控对象的状态进行实时监测、决策和调整&#xff0c;达到预期目标的过程。LabVIEW作为一种图形化编程工具&#xff0c;非常适合开发自动控制系统。那么&#xff0c;什么样的LabVIEW控制算作“自动…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

密码学基础——SM4算法

博客主页&#xff1a;christine-rr-CSDN博客 ​​​​专栏主页&#xff1a;密码学 &#x1f4cc; 【今日更新】&#x1f4cc; 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 ​编辑…...

写一个shell脚本,把局域网内,把能ping通的IP和不能ping通的IP分类,并保存到两个文本文件里

写一个shell脚本&#xff0c;把局域网内&#xff0c;把能ping通的IP和不能ping通的IP分类&#xff0c;并保存到两个文本文件里 脚本1 #!/bin/bash #定义变量 ip10.1.1 #循环去ping主机的IP for ((i1;i<10;i)) doping -c1 $ip.$i &>/dev/null[ $? -eq 0 ] &&am…...

【QT控件】显示类控件

目录 一、Label 二、LCD Number 三、ProgressBar 四、Calendar Widget QT专栏&#xff1a;QT_uyeonashi的博客-CSDN博客 一、Label QLabel 可以用来显示文本和图片. 核心属性如下 代码示例: 显示不同格式的文本 1) 在界面上创建三个 QLabel 尺寸放大一些. objectName 分别…...

P10909 [蓝桥杯 2024 国 B] 立定跳远

# P10909 [蓝桥杯 2024 国 B] 立定跳远 ## 题目描述 在运动会上&#xff0c;小明从数轴的原点开始向正方向立定跳远。项目设置了 $n$ 个检查点 $a_1, a_2, \cdots , a_n$ 且 $a_i \ge a_{i−1} > 0$。小明必须先后跳跃到每个检查点上且只能跳跃到检查点上。同时&#xff0…...

【Zephyr 系列 16】构建 BLE + LoRa 协同通信系统:网关转发与混合调度实战

🧠关键词:Zephyr、BLE、LoRa、混合通信、事件驱动、网关中继、低功耗调度 📌面向读者:希望将 BLE 和 LoRa 结合应用于资产追踪、环境监测、远程数据采集等场景的开发者 📊篇幅预计:5300+ 字 🧭 背景与需求 在许多 IoT 项目中,单一通信方式往往难以兼顾近场数据采集…...

linux设备重启后时间与网络时间不同步怎么解决?

linux设备重启后时间与网络时间不同步怎么解决&#xff1f; 设备只要一重启&#xff0c;时间又错了/偏了&#xff0c;明明刚刚对时还是对的&#xff01; 这在物联网、嵌入式开发环境特别常见&#xff0c;尤其是开发板、树莓派、rk3588 这类设备。 解决方法&#xff1a; 加硬件…...