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

【LeetCode: 2684. 矩阵中移动的最大次数 + dfs】

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨
🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯

🚀 算法题 🚀

在这里插入图片描述

在这里插入图片描述

🍔 目录

    • 🚩 题目链接
    • ⛲ 题目描述
    • 🌟 求解思路&实现代码&运行结果
      • ⚡ dfs
        • 🥦 求解思路
        • 🥦 实现代码
        • 🥦 运行结果
    • 💬 共勉

🚩 题目链接

  • 2684. 矩阵中移动的最大次数

⛲ 题目描述

给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ,矩阵由若干 正 整数组成。

你可以从矩阵第一列中的 任一 单元格出发,按以下方式遍历 grid :

从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。
返回你在矩阵中能够 移动 的 最大 次数。

示例 1:
在这里插入图片描述

输入:grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
输出:3
解释:可以从单元格 (0, 0) 开始并且按下面的路径移动:

  • (0, 0) -> (0, 1).
  • (0, 1) -> (1, 2).
  • (1, 2) -> (2, 3).
    可以证明这是能够移动的最大次数。
    示例 2:

在这里插入图片描述

输入:grid = [[3,2,4],[2,1,9],[1,1,7]]
输出:0
解释:从第一列的任一单元格开始都无法移动。

提示:

m == grid.length
n == grid[i].length
2 <= m, n <= 1000
4 <= m * n <= 105
1 <= grid[i][j] <= 106

🌟 求解思路&实现代码&运行结果


⚡ dfs

🥦 求解思路
  1. 该题目可以通过dfs,也可以通过bfs来求解,我们就用dfs来做,感兴趣的同学可以使用bfs。我们从第一列的任一单元格开始,递归右上/右侧/右下三个方向,如果走一步后,没有出界,且格子值大于当前的位置,继续向前走,继续递归过程。在递归的时候,记录每次可以走的最大次数,最后更新答案并返回。
  2. 需要注意的是,通过dfs我们会有很多重复计算的过程,所以,我们需要对其进行一个优化的过程,怎么优化呢?首先就必须要明白,重复计算的过程是什么。如果第一行第一列的数值可以想右侧和右下侧移动,并且,第二行第一列的数值和第一行第一列的元素相同,那么它会重复右上和右侧的位置,这个就是重复计算过程。
  3. 为了避免这个过程,我们可以将每次递归走过的位置都标记为0,这样就可以保证下次再走的时候不会重复走,避免了重复计算的过程。
  4. 有了基本的思路,接下来我们就来通过代码来实现一下。
🥦 实现代码
class Solution {public int maxMoves(int[][] grid) {int m = grid.length, n = grid[0].length;int max = 0;for (int i = 0; i < m; i++) {max = Math.max(max, dfs(i, 0, m, n, grid));}return max;}public int dfs(int i, int j, int m, int n, int[][] grid) {int p1 = 0, p2 = 0, p3 = 0;if (i >= 1 && i <= m && j < n - 1 && grid[i - 1][j + 1] > grid[i][j]) {p1 = dfs(i - 1, j + 1, m, n, grid) + 1;}if (i <= m - 1 && j < n - 1 && grid[i][j + 1] > grid[i][j]) {p2 = dfs(i, j + 1, m, n, grid) + 1;}if (i < m - 1 && j < n - 1 && grid[i + 1][j + 1] > grid[i][j]) {p3 = dfs(i + 1, j + 1, m, n, grid) + 1;}grid[i][j] = 0;return Math.max(p1, Math.max(p2, p3));}
}
🥦 运行结果

在这里插入图片描述


💬 共勉

最后,我想和大家分享一句一直激励我的座右铭,希望可以与大家共勉!

在这里插入图片描述

在这里插入图片描述

相关文章:

【LeetCode: 2684. 矩阵中移动的最大次数 + dfs】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…...

第五节:使用SMB开发WebSocket通信

一、概述 本节主要讲解在SMB中如何进行websocket快速开发&#xff0c;实现客户端连接、关闭、消息通讯等功能。 示例下载&#xff1a;https://download.csdn.net/download/lllllllllluoyi/88949743 二、创建WebSocket服务器 1、在csdnProject工程中新建一个消息流。 添加W…...

Nginx和Ribbon实现负载均衡的区别

Nginx和Ribbon的区别 1. Nginx服务器端负载均衡&#xff1a; 1、Nginx是客户端所有请求统一交给nginx&#xff0c;由nginx进行实现负载均衡请求转发&#xff0c;属于服务器端负载均衡。即请求有nginx服务器端进行转发。 3、Nginx是服务端的负载均衡&#xff0c;Ribbon是客户端…...

流畅的Python(十九)-动态属性和特性

一、核心要义 在Python中,数据的属性和处理数据的方法,统称属性。方法&#xff0c;只是可调用的属性。除了这两者之外,我们还可以创建特性(property),在不改变类接口的前提下,使用存取方法(即读值方法和设值方法)修改数据属性。 二、代码示例 0、相关知识点 #!/usr/bin/env…...

确保云原生部署中的网络安全

数字环境正在以惊人的速度发展&#xff0c;组织正在迅速采用云原生部署和现代化使用微服务和容器构建的应用程序&#xff08;通常运行在 Kubernetes 等平台上&#xff09;&#xff0c;以推动增长。 无论我们谈论可扩展性、效率还是灵活性&#xff0c;对于努力提供无与伦比的用…...

【分布式websocket 】前端vuex管理客户端消息crud!使用localStorage来存储【第19期】

前言 聊天系统客户端是要存储消息的&#xff0c;因为所有所有的历史消息都从服务器拉的话一方面服务器压力大&#xff0c;另一方面也耗费用户流量。所以客户端存储消息是势在必行的。如何存储呢上一篇文章也写了&#xff0c;大概就是浏览器的话是localStorage或者IndexedDB。然…...

venv uvicorn python 虚拟服务器外网无法访问

python -m venv .venv source ./.venv/bin/activate pip install -r requirements.txt ./run.sh source ./.venv/bin/activate uvicorn main:app --reload 虚拟web服务器外网访问控制台启动命令用以下代码启动 uvicorn main:app --host 0.0.0.0 --port 8501 --reload 启动到后…...

一款博客网站源码

一款博客网站源码 源码软件库 为大家内置了主题 清爽又强大真正的永久可用的一条源码&#xff0c;该版本为整合版本&#xff0c;内置了Joe主题&#xff0c;搭建后直接启用即可~ 安装环境要求&#xff1a; PHP 7.2 以上 MySQL, PostgreSQL, SQLite 任意一种数据库支持&#xff…...

Mr-Robot1靶场练习靶场推荐小白入门练习靶场渗透靶场bp爆破wordpress

下载链接&#xff1a; Mr-Robot: 1 ~ VulnHub 安装&#xff1a; 打开vxbox&#xff0c;菜单栏----管理----导入虚拟电脑 选择下载完的ova文件&#xff0c;并修改想要保存的位置&#xff08;也可以保持默认位置&#xff09; 导入完成后可以根据自己的情况去配置网络链接方式 完成…...

数据仓库的设计开发应用(三)

目录 五、数据仓库的实施&#xff08;一&#xff09;数据仓库的创建&#xff08;二&#xff09;数据抽取转换加载 六、数据仓库系统的开发&#xff08;一&#xff09;开发任务&#xff08;二&#xff09;开发方法&#xff08;三&#xff09;系统测试 七、数据仓库系统的应用&am…...

【04】WebAPI

WebAPI 和标准库不同,WebAPI 是浏览器提供的一套 API,用于操作浏览器窗口和界面 WebAPI 中包含两个部分: BOM:Browser Object Model,浏览器模型,提供和浏览器相关的操作DOM:Document Object Model,文档模型,提供和页面相关的操作BOM BOM 提供了一系列的对象和函数,…...

数据预处理在数据挖掘中的重要性

数据挖掘作为从大量数据中提取有用信息和知识的过程&#xff0c;其结果的准确性和可靠性直接受到数据质量的影响。因此&#xff0c;数据预处理在数据挖掘中扮演着至关重要的角色。让我们探讨数据质量对数据挖掘结果的影响&#xff0c;并介绍常见的数据预处理方法以及它们如何提…...

Java并发编程—JUC线程池架构

Java并发编程&#xff08;JUC&#xff0c;Java Utilities Concurrency&#xff09;中的线程池架构是Java提供的一种用于管理和复用线程的机制。线程池的主要目标是减少线程创建和销毁的开销&#xff0c;提高系统的响应速度&#xff0c;并通过合理的线程管理和资源分配&#xff…...

Android input输入子系统

一.Android input输入子系统简介 Input系统是Android系统中负责处理用户输入操作的核心组件&#xff0c;它负责从各种输入设备&#xff08;如屏幕、键盘、鼠标等&#xff09;获取原始的输入事件&#xff08;如按键、触摸、滑动等&#xff09;&#xff0c;并将其转换为Android应…...

如何在webapp中于动发布一个应用

目录 第一步&#xff1a;在webapp文件夹内自定义文件夹第二步&#xff1a;生成一个文本&#xff0c;并把后缀改为 .html第三步&#xff1a;进入bin文件夹打开服务第四步&#xff1a;打开方式选择java第六步&#xff1a;输入你想输出的东西第七步&#xff1a;双击运行即可 第一步…...

部署一个本地的ChatGPT(Ollama)

一 下载Ollama Ollama下载地址&#xff1a;https://ollama.com/download 下载完后 二 安装运行 双击下载好的OllamaSetup.exe开发 安装Ollama: 安装完成后&#xff0c;多了一个Ollama的菜单如下图 &#xff1a; Ollama安装好默认是配置开机运行&#xff0c;如果没有运行可以在…...

Vue 3中的reactive:响应式状态的全面管理

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…...

【网络】详解HTTPS及探究加密过程

目录 一、什么是HTTPS1、加密解密是什么2、为什么要加密3、常见的加密方式1、对称加密2、非对称加密 二、探究HTTPS如何实现加密1、方案一----只使用对称加密2、方案二----只使用非对称加密3、方案三----双方都使用非对称加密4、方案四----非对称加密 对称加密5、中间人攻击6、…...

【C语言】字符与字符串---从入门到入土级详解

&#x1f984;个人主页:修修修也 &#x1f38f;所属专栏:C语言 ⚙️操作环境:Visual Studio 2022 目录 一.字符类型和字符数组&#xff08;串&#xff09;简介 1.ASCII 2.定义&#xff0c;初始化&#xff0c;使用 1>字符的定义及初始化 2>字符串的定义及初始化 二.…...

Github Copilot 工具,无需账号,一键激活

① 无需账号&#xff0c;100%认证成功&#xff01;0风险&#xff0c;可联网可更新&#xff0c;&#xff0c;支持copilot版本升级&#xff0c;支持chat ② 支持windows、mac、linux系统等设备 ③一号通用&#xff0c;支持所有IDE(AppCode,CLion,DataGrip,GoLand,IntelliJ IDEA …...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践

前言&#xff1a;本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中&#xff0c;跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南&#xff0c;你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案&#xff0c;并结合内网…...

[特殊字符] 手撸 Redis 互斥锁那些坑

&#x1f4d6; 手撸 Redis 互斥锁那些坑 最近搞业务遇到高并发下同一个 key 的互斥操作&#xff0c;想实现分布式环境下的互斥锁。于是私下顺手手撸了个基于 Redis 的简单互斥锁&#xff0c;也顺便跟 Redisson 的 RLock 机制对比了下&#xff0c;记录一波&#xff0c;别踩我踩过…...

大数据驱动企业决策智能化的路径与实践

&#x1f4dd;个人主页&#x1f339;&#xff1a;慌ZHANG-CSDN博客 &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; 一、引言&#xff1a;数据驱动的企业竞争力重构 在这个瞬息万变的商业时代&#xff0c;“快者胜”的竞争逻辑愈发明显。企业如何在复杂环…...

Qwen系列之Qwen3解读:最强开源模型的细节拆解

文章目录 1.1分钟快览2.模型架构2.1.Dense模型2.2.MoE模型 3.预训练阶段3.1.数据3.2.训练3.3.评估 4.后训练阶段S1: 长链思维冷启动S2: 推理强化学习S3: 思考模式融合S4: 通用强化学习 5.全家桶中的小模型训练评估评估数据集评估细节评估效果弱智评估和民间Arena 分析展望 如果…...