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

2713. 矩阵中严格递增的单元格数

题目

给定一个 m x n 的整数矩阵 mat,我们需要找出从某个单元格出发可以访问的最大单元格数量。移动规则是可以从当前单元格移动到同一行或同一列的任何其他单元格,但目标单元格的值必须严格大于当前单元格的值。需要返回最大可访问的单元格数量。

示例

示例 1:

示例1

输入:mat = [[3,1],[3,4]]

输出:2

解释:从第 1 行、第 2 列的单元格开始,可以访问 2 个单元格。

示例 2:

示例2

输入:mat = [[1,1],[1,1]]

输出:1

解释:由于目标单元格必须严格大于当前单元格,只能访问 1 个单元格。

示例 3:

示例3

输入:mat = [[3,1,6],[-9,5,7]]

输出:4

解释:从第 2 行、第 1 列的单元格开始,可以访问 4 个单元格。

提示

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 10^5
  • 1 <= m * n <= 10^5
  • -10^5 <= mat[i][j] <= 10^5

解决方案

采用深度优先搜索(DFS)结合动态规划(DP)来解决此问题。用 dp[i][j] 表示从位置 (i, j) 出发可以访问的最大单元格数。

代码

#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>#define MAX(a,b) ((a) > (b) ? (a) : (b))int matSize, matColSize;
int **mat, **dp;bool isValid(int x, int y) {return x >= 0 && x < matSize && y >= 0 && y < matColSize;
}int dfs(int x, int y) {if (dp[x][y] != 0) return dp[x][y];int maxLen = 1;for (int col = 0; col < matColSize; col++) {if (col != y && mat[x][col] > mat[x][y]) {maxLen = MAX(maxLen, 1 + dfs(x, col));}}for (int row = 0; row < matSize; row++) {if (row != x && mat[row][y] > mat[x][y]) {maxLen = MAX(maxLen, 1 + dfs(row, y));}}dp[x][y] = maxLen;return maxLen;
}int maxIncreasingCells(int** matrix, int matrixSize, int* matrixColSize){mat = matrix;matSize = matrixSize;matColSize = *matrixColSize;dp = (int**)calloc(matSize, sizeof(int*));for (int i = 0; i < matSize; i++) {dp[i] = (int*)calloc(matColSize, sizeof(int));}int maxCells = 0;for (int i = 0; i < matSize; i++) {for (int j = 0; j < matColSize; j++) {maxCells = MAX(maxCells, dfs(i, j));}}for (int i = 0; i < matSize; i++) {free(dp[i]);}free(dp);return maxCells;
}

实现步骤

1. 初始化和输入处理

读取输入矩阵,并初始化 dp 数组。dp[i][j] 用于存储从位置 (i, j) 出发可以访问的最大单元格数。

int matSize, matColSize;
int **mat, **dp;dp = (int**)calloc(matSize, sizeof(int*));
for (int i = 0; i < matSize; i++) {dp[i] = (int*)calloc(matColSize, sizeof(int));
}

2. 定义有效移动检查函数

检查从当前单元格移动到目标单元格是否合法,即目标单元格的值必须严格大于当前单元格的值。

bool isValid(int x, int y) {return x >= 0 && x < matSize && y >= 0 && y < matColSize;
}

3. 深度优先搜索(DFS)

  • dp[x][y] 已计算,直接返回。
  • 遍历同一行和同一列中的单元格,若满足条件,递归计算并更新 dp[x][y]
int dfs(int x, int y) {if (dp[x][y] != 0) return dp[x][y];int maxLen = 1;// 遍历同一行中的其他单元格for (int col = 0; col < matColSize; col++) {if (col != y && mat[x][col] > mat[x][y]) {maxLen = MAX(maxLen, 1 + dfs(x, col));}}// 遍历同一列中的其他单元格for (int row = 0; row < matSize; row++) {if (row != x && mat[row][y] > mat[x][y]) {maxLen = MAX(maxLen, 1 + dfs(row, y));}}dp[x][y] = maxLen;return maxLen;
}

4. 主逻辑

  • 遍历矩阵每个单元格,计算从每个单元格出发可以访问的最大单元格数。
  • 更新并返回全局最大值。
int maxIncreasingCells(int** matrix, int matrixSize, int* matrixColSize){mat = matrix;matSize = matrixSize;matColSize = *matrixColSize;dp = (int**)calloc(matSize, sizeof(int*));for (int i = 0; i < matSize; i++) {dp[i] = (int*)calloc(matColSize, sizeof(int));}int maxCells = 0;// 遍历每个单元格for (int i = 0; i < matSize; i++) {for (int j = 0; j < matColSize; j++) {maxCells = MAX(maxCells, dfs(i, j));}}for (int i = 0; i < matSize; i++) {free(dp[i]);}free(dp);return maxCells;
}

复杂度分析

  • 时间复杂度:O(m * n),每个单元格只被访问一次。
  • 空间复杂度:O(m * n),用于存储 dp 数组。

结果

我尽力了。。。不愧是困难提题目
在这里插入图片描述

贴一个优化前的代码

#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#define MAX(a,b) ((a) > (b) ? (a) : (b))
int gotoNext(int** dp, int matSize, int* matColSize, int** mat, int beginCol, int beginRow, int* tmpStepCnt, bool** isVisited)
{if(dp[beginCol][beginRow] != 0){(*tmpStepCnt) += dp[beginCol][beginRow];return (*tmpStepCnt);}(*tmpStepCnt)++;isVisited[beginCol][beginRow] = true;int tmp_left = 0, tmp_right = 0, tmp_up = 0, tmp_down = 0;int left = 0, right = 0, up = 0, down = 0;int cnt = 0;for (int i = 1; i < matSize; i++){if(beginCol + i <= matSize - 1 && !isVisited[beginCol + i][beginRow] && mat[beginCol + i][beginRow] > mat[beginCol][beginRow]) {tmp_right = gotoNext(dp, matSize, matColSize, mat, beginCol + i, beginRow, &cnt, isVisited);right = MAX(tmp_right, right);cnt = 0;// printf("right = %d\n",right);}else{// // printf("cant goto [%d][%d]\n",beginCol + i, beginRow);}if(beginCol - i >= 0 && !isVisited[beginCol - i][beginRow] && mat[beginCol - i][beginRow] > mat[beginCol][beginRow]) {tmp_left = gotoNext(dp, matSize, matColSize, mat, beginCol - i, beginRow, &cnt, isVisited);left = MAX(tmp_left, left);cnt = 0;// printf("left = %d\n",left);}else{// // printf("cant goto [%d][%d]\n",beginCol - i, beginRow);}}for (int i = 1; i < (*matColSize); i++){if(beginRow + i <= (*matColSize) - 1 && !isVisited[beginCol][beginRow + i] && mat[beginCol][beginRow + i] > mat[beginCol][beginRow]) {tmp_down = gotoNext(dp, matSize, matColSize, mat, beginCol, beginRow + i, &cnt, isVisited);down = MAX(tmp_down, down);cnt = 0;// printf("down = %d\n",down);}else{// // printf("cant goto [%d][%d]\n",beginCol, beginRow + i);}if(beginRow - i >= 0 && !isVisited[beginCol][beginRow - i] && mat[beginCol][beginRow - i] > mat[beginCol][beginRow]){tmp_up = gotoNext(dp, matSize, matColSize, mat, beginCol, beginRow - i, &cnt, isVisited);up = MAX(tmp_up, up);cnt = 0;// printf("up = %d\n",up);}else{// // printf("cant goto [%d][%d]\n",i, beginRow - i);}}isVisited[beginCol][beginRow] = false;(*tmpStepCnt) += MAX(MAX(left, right), MAX(up, down));return (*tmpStepCnt);
}int maxIncreasingCells(int** mat, int matSize, int* matColSize){int stepCnt = 0;int **dp = (int**)calloc(matSize, sizeof(int*)); // 记录从某个格子开始走,可以走多少个格子。bool **isVisited = (bool**)calloc(matSize, sizeof(bool*)); // 记录某个格子是否被访问,防止死循环。for (int i = 0; i < matSize; i++){dp[i] = (int*)calloc((*matColSize), sizeof(int)); // 记录从某个格子开始走,可以走多少个格子。isVisited[i] = (bool*)calloc((*matColSize), sizeof(bool)); // 记录某个格子是否被访问,防止死循环。}for (int i = 0; i < matSize; i++){for (int j = 0; j < (*matColSize); j++){int tmpStepCnt = 0;tmpStepCnt = gotoNext(dp, matSize, matColSize, mat, i, j, &tmpStepCnt, isVisited);stepCnt = MAX(tmpStepCnt, stepCnt);dp[i][j] = tmpStepCnt;// printf("dp[%d][%d] = %d\n", i,j,dp[i][j]);}}return stepCnt;
}

这个更惨,
在这里插入图片描述

相关文章:

2713. 矩阵中严格递增的单元格数

题目 给定一个 m x n 的整数矩阵 mat&#xff0c;我们需要找出从某个单元格出发可以访问的最大单元格数量。移动规则是可以从当前单元格移动到同一行或同一列的任何其他单元格&#xff0c;但目标单元格的值必须严格大于当前单元格的值。需要返回最大可访问的单元格数量。 示例…...

git创建子模块

有种情况我们经常会遇到&#xff1a;某个工作中的项目需要包含并使用另一个项目。 也许是第三方库&#xff0c;或者你独立开发的&#xff0c;用于多个父项目的库。 现在问题来了&#xff1a;你想要把它们当做两个独立的项目&#xff0c;同时又想在一个项目中使用另一个。 Git …...

把Deepin塞进U盘,即插即用!Deepin To Go来袭

前言 小伙伴之前在某篇文章下留言说&#xff1a;把Deepin塞进U盘的教程。 这不就来了吗&#xff1f; 事实是可以的。这时候你要先做点小准备&#xff1a; 一个大小为8GB或以上的普通U盘 一个至少64GB或以上的高速U盘 一个Deepin系统镜像文件 普通U盘的大概介绍&#xff1…...

​​给【AI硬件】创业者的论文、开源项目和产品整理

一、AI 硬件精选论文 《DrEureka: Language Model Guided Sim-To-Real Transfer》 瑜伽球上遛「狗」这项研究由宾夕法尼亚大学、 NVIDIA 、得克萨斯大学奥斯汀分校的研究者联合打造&#xff0c;并且完全开源。他们提出了 DrEureka&#xff08;域随机化 Eureka&#xff09;&am…...

模拟面试题卷二

1. 什么是JavaEE框架&#xff0c;你能列举一些常用的JavaEE框架吗&#xff1f; 答&#xff1a;JavaEE框架是一套用于开发企业级应用的技术规范和工具集合。常用的JavaEE框架有Spring、Hibernate、Struts、JSF等。 2. 请解释一下面向对象技术和设计原则是什么&#xff0c;你能…...

22种常用设计模式示例代码

文章目录 创建型模式结构型模式行为模式 仓库地址https://github.com/Xiamu-ssr/DesignPatternsPractice 参考教程 refactoringguru设计模式-目录 创建型模式 软件包复杂度流行度工厂方法factorymethod❄️⭐️⭐️⭐️抽象工厂abstractfactory❄️❄️⭐️⭐️⭐️生成器bui…...

Java面试题:对比ArrayList和LinkedList的内部实现,以及它们在不同场景下的适用性

ArrayList和LinkedList是Java中常用的两个List实现&#xff0c;它们在内部实现和适用场景上有很大差异。下面是详细的对比分析&#xff1a; 内部实现 ArrayList 数据结构&#xff1a;内部使用动态数组&#xff08;即一个可变长的数组&#xff09;实现。存储方式&#xff1a;…...

ping: www.baidu.com: 未知的名称或服务(IP号不匹配)

我用的是VMware上的Red Hat Enterprise Linux 9&#xff0c;出现了能联网但ping不通外网的情况。 问题描述&#xff1a;设置中显示正常连接&#xff0c;而且虚拟机右上角有联网的图标&#xff0c;但不能通外网。 按照网上教程修改了/etc/resolv.conf和/etc/sysconfig/network-…...

谷神前端组件增强:子列表

谷神Ag-Grid导出Excel // 谷神Ag-Grid导出Excel let allDiscolumns detailTable.getAllDisColumns() let columnColIds columns.map(column > column.colId) let columnKeys columnColIds.filter(item > ![select, "_OPT_FIELD_"].includes(item)) detailT…...

测试cudaStream队列的深度

测试cudaStream队列的深度 一.代码二.编译运行[得出队列深度为512] 以下代码片段用于测试cudaStream队列的深度 方法: 主线程一直发任务,启一个线程cudaEventQuery查询已完成的任务,二个计数器的值相减 一.代码 #include <iostream> #include <thread> #include …...

​海康威视 isecure center 综合安防管理平台任意文件上传漏洞

文章目录 前言声明一、漏洞描述二、影响版本三、漏洞复现四、修复方案 前言 海康威视是以视频为核心的智能物联网解决方案和大数据服务提供商,业务聚焦于综合安防、大数据服务和智慧业务。 海康威视其产品包括摄像机、多屏控制器、交通产品、传输产品、存储产品、门禁产品、消…...

shadertoy-安装和使用

一、安装vscode 安装vscode流程 二、安装插件 1.安装glsl编辑插件 2.安装shader toy插件 三、创建glsl文件 test.glsl文件 float Grid(float size, vec2 fragCoord) {vec2 r fragCoord / size;vec2 grid abs(fract(r - 0.5) - 0.5) / fwidth(r);float line min(grid…...

matlab线性多部法求常微分方程数值解

用Adamas内差二步方法&#xff0c;内差三步方法&#xff0c;外差二步方法&#xff0c;外差三步方法这四种方法计算。 中k为1和2. k为2和3 代码 function chap1_adams_methodu0 1; T 2; h 0.1; N T/h; t 0:h:T; solu exact1(t);f f1; u_inter_2s adams_inter_2steps(…...

前端页面实现【矩阵表格与列表】

实现页面&#xff1a; 1.动态表绘制&#xff08;可用于矩阵构建&#xff09; <template><div><h4><b>基于层次分析法的权重计算</b></h4><table table-layout"fixed"><thead><tr><th v-for"(_, colI…...

GPT4v和Gemini-Pro调用对比

要调用 GPT-4 Vision (GPT-4V) 和 Gemini-Pro&#xff0c;以下是详细的步骤分析&#xff0c;包括调用流程、API 使用方法和两者之间的区别&#xff0c;以及效果对比和示例。 GPT-4 Vision (GPT-4V) 调用步骤 GPT-4 Vision 主要通过 OpenAI 的 API 进行调用&#xff0c;用于处…...

破布叶(Microcos paniculata)单倍型染色体级别基因组-文献精读22

Haplotype-resolved chromosomal-level genome assembly of Buzhaye (Microcos paniculata) 破布叶、布渣叶&#xff08;Microcos paniculata&#xff09;单倍型解析染色体级别基因组组装 摘要 布渣叶&#xff08;Microcos paniculata&#xff09;是一种传统上用作民间药物和…...

浅谈RC4

一、什么叫RC4&#xff1f;优点和缺点 RC4是对称密码&#xff08;加密解密使用同一个密钥&#xff09;算法中的流密码&#xff08;一个字节一个字节的进行加密&#xff09;加密算法。 优点&#xff1a;简单、灵活、作用范围广&#xff0c;速度快 缺点&#xff1a;安全性能较差&…...

uniapp微信小程序开发物料

开发工具 HBuilder&#xff1a; HBuilderX-高效极客技巧 vscode 1、在vscode中新建一个项目npx degit dcloudio/uni-preset-vue#vite-ts 项目名称 2、在HBuilder中可以可视化进行新建项目 路由 在app.json文件中配置pages路由路径 路由跳转方法 uni.navigateTo(OBJECT)…...

大数据工程师如何做到数据可视化?

好的数据可视化作品都是通过不断的数据对比分析实战出来的。 今天给大家带来一篇大数据工程师干货&#xff0c;从多角度解析做数据可视化的重要性&#xff0c;并解读一些适用的应用场景。大数据工程师们刷到这篇文章时一定要进来看看&#xff0c;满满的干货。 目录 1. 什么是数…...

Java 序列化与反序列化

Java 序列化是一种将对象的状态转换为字节流的机制&#xff0c;以便可以将该对象的状态保存到文件、数据库或通过网络传输。在反序列化过程中&#xff0c;这些字节流可以被重新转换为对象。序列化主要用于以下几种情况&#xff1a; 持久化存储&#xff1a;将对象的状态保存到文…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...