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

2024-06-20 05:36
文章标签 矩阵 递增 单元格 严格 2713

本文主要是介绍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. 矩阵中严格递增的单元格数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1077246。

相关文章

hdu 4565 推倒公式+矩阵快速幂

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值： Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中： 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令： An=(a+b√)n A_n = (a +
阅读更多...
POJ1631最长单调递增子序列

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ
阅读更多...
hdu 6198 dfs枚举找规律+矩阵乘法

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn
阅读更多...
线性代数|机器学习-P35距离矩阵和普鲁克问题

线性代数|机器学习-P35距离矩阵和普鲁克问题

文章目录 1. 距离矩阵2. 正交普鲁克问题3. 实例说明 1. 距离矩阵 假设有三个点 x 1 , x 2 , x 3 x_1,x_2,x_3 x1​,x2​,x3​,三个点距离如下： ∣ ∣ x 1 − x 2 ∣ ∣ 2 = 1 , ∣ ∣ x 2 − x 3 ∣ ∣ 2 = 1 , ∣ ∣ x 1 − x 3 ∣ ∣ 2 = 6 \begin{equation} ||x
阅读更多...
如何在Excel中根据单元格内容作MSnbsp;…

如何在Excel中根据单元格内容作MSnbsp;…

上篇文章，我们介绍了INDEX+SMALL+IF+ROW的数组公式组合，也就是说只要在IF中通过条件的构造，基本上就可以想提取什么条件的数据都可以，数据查询肯定得心应手。 但是，我们一起强调函数公式不是万能的，尤其是数组公式在海量数据面前，既是软肋也是硬伤，而且构造这个函数组合还需要你要具备或者能理解简单数组公式逻辑，对于在函数公式方面没有深究的人，自然是一头雾水。当然，就像“数据透视表”一样，
阅读更多...
jqgrid设置单元格可编辑

jqgrid设置单元格可编辑

1 在单元格的属性列设置为editable。 2 点击编辑按钮的时候，触发某一行设置为edit的状态。 jQuery("#rowed4").jqGrid({url:'server.php?q=2',datatype: "json",colNames:['Inv No','Date', 'Client', 'Amount','Tax','Total','Notes'],colModel
阅读更多...
【线性代数】正定矩阵，二次型函数

【线性代数】正定矩阵，二次型函数

本文主要介绍正定矩阵，二次型函数，及其相关的解析证明过程和各个过程的可视化几何解释（深蓝色字体）。 非常喜欢清华大学张颢老师说过的一段话：如果你不能用可视化的方式看到事情的结果，那么你就很难对这个事情有认知，认知就是直觉，解析的东西可以让你理解，但未必能让你形成直觉，因为他太反直觉了。 正定矩阵 定义 给定一个大小为 n×n 的实对称矩阵 A ，若对于任意长度为 n 的非零向量 ，有 恒成
阅读更多...
代码随想录刷题day25丨491.递增子序列 ，46.全排列 ，47.全排列 II

代码随想录刷题day25丨491.递增子序列 ，46.全排列 ，47.全排列 II

代码随想录刷题day25丨491.递增子序列 ，46.全排列 ，47.全排列 II 1.题目 1.1递增子序列 题目链接：491. 非递减子序列 - 力扣（LeetCode） 视频讲解：回溯算法精讲，树层去重与树枝去重 | LeetCode：491.递增子序列_哔哩哔哩_bilibili 文档讲解：https://programmercarl.com/0491.%E9%80%92%E
阅读更多...
PL/SQL工具创建Oracle数据库表，实现id字段的自动递增

PL/SQL工具创建Oracle数据库表，实现id字段的自动递增

通过PL/SQL工具，创建Oracle数据库表，如何实现字段ID自动递增； Oracle的自增需要依靠序列和触发器共同实现 比如：先创建一个表 create table test (id int primary key, name varchar2(10)); 创建一个序列 create sequence test_seq increment by 1 start with 1  min
阅读更多...
python科学计算：NumPy 线性代数与矩阵操作

python科学计算：NumPy 线性代数与矩阵操作

1 NumPy 中的矩阵与数组 在 NumPy 中，矩阵实际上是一种特殊的二维数组，因此几乎所有数组的操作都可以应用到矩阵上。不过，矩阵运算与一般的数组运算存在一定的区别，尤其是在点积、乘法等操作中。 1.1 创建矩阵 矩阵可以通过 NumPy 的 array() 函数创建。矩阵的形状可以通过 shape 属性来访问。 import numpy as np# 创建一个 2x3 矩阵mat
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2