LeetCode——矩阵中移动的最大次数

news/2024/10/30 11:28:58/

目录

1、题目

 2、题目解读

 3、代码


1、题目

2684. 矩阵中移动的最大次数 - 力扣(Leetcode)

给你一个下标从 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

 2、题目解读

题目第二个示例,第一列中的3的左边还有左下角都比3小,不能移动。2和1也是如此,所以无法移动

理解题目意思,然后就是dfs,每一轮向右搜索一列。注意不要重复搜索!

 3、代码

class Solution {//dfsprivate int n;private int m;private int max=0;//保存 当前最大移动次数public int maxMoves(int[][] grid) {n=grid.length;m=grid[0].length;//vis用于剪枝操作boolean[][] vis = new boolean[n][m];for(int i=0;i<n;i++){dfs(i,0,grid, vis);//如果max为m-1,已经是能达到的最大值了,无须再考虑后面的情况了if(max==m-1)break;}return max;}public void dfs(int i, int j, int[][] grid, boolean[][] vis){//如果j达到最大值,说明可以移动到最后一列,此时就可以退出递归了if(j==m-1){max=m-1;return;}//符合移动条件,且目标单元格还没有搜索过if(grid[i][j+1]>grid[i][j] && !vis[i][j + 1]){//继续搜索dfs(i,j+1,grid,vis);//并标记目标单元格已经搜索,避免重复搜索vis[i][j+1]=true;}//下面同理if(i>0 && grid[i-1][j+1]>grid[i][j] && !vis[i - 1][j + 1]){dfs(i-1,j+1,grid,vis);vis[i-1][j+1]=true;}if(i<n-1 && grid[i+1][j+1]>grid[i][j] && !vis[i + 1][j + 1]){dfs(i+1,j+1,grid,vis);vis[i+1][j+1]=true;}//全部搜索完毕后,若j值比max大,则保留该j值为最大值max=Math.max(max,j);}
}


http://www.ppmy.cn/news/78499.html

相关文章

【HackTheBox Bagel】打靶记录

一、namp扫描到5000 8000 22 端口 二、访问8000端口&#xff0c;看到跳转到域名bagel.htb&#xff0c;加入到hosts 看到该url 像文件包含&#xff0c;尝试fuzz一波 尝试找公私钥均未果&#xff0c;找到了cmdline 进一步对其包含 HTTP/1.1 200 OK Server: Werkzeug/2.2.2 …

How to use RestTemplate in Spring boot, part II

How to use RestTemplate in Spring boot, part II Consumer ServicepomControllerBusinessConsumerBusinessConsumerBusinessImpl ResultMaoResultMaoResultCode Request Configapplication.ymlJurongConfigknife4jConfig Summary 考虑到篇幅问题&#xff0c;这里将一篇文章切…

Smartbi电子表格故事之用数据进行销售问题分析

天津小麦商贸有限公司&#xff08;X&M&#xff09;成立于2012年11月&#xff0c;主营业务是商贸流通业&#xff0c;主要是日用商品的批发销售。 2012年前&#xff0c;公司创始人&#xff08;总经理和销售总监&#xff09;一直从事外贸的生意&#xff0c;自从2008年金融危机…

FreeRTOS学习之路,以STM32F103C8T6为实验MCU(序章——浅谈单片机以及FreeRTOS)

学习之路主要为FreeRTOS操作系统在STM32F103&#xff08;STM32F103C8T6&#xff09;上的运用&#xff0c;采用的是标准库编程的方式&#xff0c;使用的IDE为KEIL5。 注意&#xff01;&#xff01;&#xff01;本学习之路可以通过购买STM32最小系统板以及部分配件的方式进行学习…

kubelet源码分析 添加 /删除pod (SyncPod、SyncTerminatingPod、SyncTerminatedPod)篇

kubelet源码分析 添加 /删除pod (SyncPod、SyncTerminatingPod、SyncTerminatedPod) kubelet版本v1.27.1 前面讲过删除pod和添加pod&#xff0c;都是在kubelet文件的的HandlePodAdditions函数和pod_workers.go文件中主要流程。 这篇文章是当pod_workers.go流程结束后&#xf…

智慧档案馆一体化监控系统设计所需要的10条依据

1.科学性 本项目目标定位为&#xff1a;以科学技术为基础&#xff0c;依靠先进的设备和优越的设计理念、科学客观的管理&#xff0c;利用信息化管理及相关最新技术&#xff0c;将库房实际环境与存储技术、计算机技术、无线自动控制技术、通讯与信息处理技术等先进技术相结合&a…

论文阅读_语音合成_Spear-TTS

论文信息 number headings: auto, first-level 2, max 4, _.1.1 name_en: Speak, Read and Prompt: High-Fidelity Text-to-Speech with Minimal Supervision name_ch: 说话、阅读和提示&#xff1a;少量监督实现高保真文本转语音 paper_addr: http://arxiv.org/abs/2302.0354…

Vue3 權限路由

最近接觸到關於role 能夠查看相關頁面的功能 最初的作法是全部的路由使用動態加載&#xff0c;考慮到 跟權限有關係 &#xff0c;就有可能各種頁面都需要調用&#xff0c;因此這裡的role狀態會儲存在全局狀態管理中&#xff08;pinia&#xff09; 1.首先區隔出需要權限才能瀏覽…