<matrix> 73 329
2024-09-05 07:25:03
73. Set Matrix Zeroes
- 先扫描第一行第一列,如果有0,则将各自的flag设置为true
- 然后扫描除去第一行第一列的整个数组,如果有0,则将对应的第一行和第一列的数字赋0
- 再次遍历除去第一行第一列的整个数组,如果对应的第一行和第一列的数字有一个为0,则将当前值赋0
- 最后根据第一行第一列的flag来更新第一行第一列
class Solution {
public void setZeroes(int[][] matrix) {
boolean isZeroCol = false;
boolean isZeroRow = false; for(int i = 0; i < matrix.length; i++){//check first Col
if(matrix[i][0] == 0){
isZeroCol = true;
break;
}
}
for(int i = 0; i < matrix[0].length; i++){//check first row
if(matrix[0][i] == 0){
isZeroRow = true;
break;
}
}
for(int i = 1; i < matrix.length; i++){//check except first row and col
for(int j = 1; j < matrix[0].length; j++){
if(matrix[i][j] == 0){
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for(int i = 1; i < matrix.length; i++){//process except first row and col
for(int j = 1; j < matrix[0].length; j++){
if(matrix[i][0] == 0 || matrix[0][j] == 0)
matrix[i][j] = 0;
}
}
if(isZeroCol){
for(int i = 0; i < matrix.length; i++){
matrix[i][0] = 0;
}
}
if(isZeroRow){
for(int j = 0; j < matrix[0].length; j++){
matrix[0][j] = 0;
}
}
}
}
329. Longest Increasing Path in a Matrix
我们需要维护一个二维动态数组dp,其中dp[i][j]表示数组中以(i,j)为起点的最长递增路径的长度,初始将dp数组都赋为0,当我们用递归调用时,遇到某个位置(x, y), 如果dp[x][y]不为0的话,我们直接返回dp[x][y]即可,不需要重复计算。我们需要以数组中每个位置都为起点调用递归来做,比较找出最大值。在以一个位置为起点用DFS搜索时,对其四个相邻位置进行判断,如果相邻位置的值大于上一个位置,则对相邻位置继续调用递归,并更新一个最大值,搜素完成后返回即可,参见代码如下:
class Solution {
public int longestIncreasingPath(int[][] matrix) {
if (matrix == null || matrix.length == 0) return 0;
int rows = matrix.length, cols = matrix[0].length;
int[][] dp = new int[rows][cols];
int res = 0;
for(int i = 0; i < matrix.length; i++){
for(int j = 0; j < matrix[0].length; j++){
if(dp[i][j] == 0){
dfs(matrix, i, j, dp, Integer.MIN_VALUE);
res = Math.max(res, dp[i][j]);
}
}
} return res;
} private int dfs(int[][] matrix, int row, int col, int[][] dp, int prev){
if(row > matrix.length - 1 || row < 0 ||
col > matrix[0].length - 1 || col < 0 ||
matrix[row][col] <= prev) return 0;
if(dp[row][col] != 0) return dp[row][col]; int left = dfs(matrix, row, col - 1, dp, matrix[row][col]);
int right = dfs(matrix, row, col + 1, dp, matrix[row][col]);
int up = dfs(matrix, row - 1, col, dp, matrix[row][col]);
int down = dfs(matrix, row + 1, col, dp, matrix[row][col]); dp[row][col] = Math.max(left, Math.max(right, Math.max(up, down))) + 1;
return dp[row][col];
}
}
最新文章
- 一缕阳光:DDD(领域驱动设计)应对具体业务场景,如何聚焦 Domain Model(领域模型)?
- Content-Type 之 application/json 与 text/javascript
- JavaWeb:实现文件上传
- boostrap折叠,jquery ui accordion同时打开多个标签
- 解决 NDP40-KB2468871不能安装
- HDU2490 parade
- JSONP实例
- 给自己加油,一定要学会MFC!
- SpringMVC对ServletAPI的支持和JSON格式的转换
- java jvm heap dump及 thread dump分析
- ASP.Net Core中使用jquery-ajax-unobtrusive替换Ajax.BeginForm
- hdu多校第3场C. Dynamic Graph Matching
- oracle分区分表
- 2018.11.24 spoj New Distinct Substrings(后缀数组)
- Disruptor的伪共享解决方案
- iOS动画的逻辑结构:动画的定义--动画是采用连续播放静止图像的方法产生物体运动的效果。
- Struts2的Convention插件
- 使用TryParse()来执行数值转换
- 【hdoj_2152】Fruit(母函数)
- 在CentOs6.5下安装Python2.7.6和Scrapy
热门文章
- 《一起学mysql》4
- 【shell脚本】将三个数字进行升序排序===numSort.sh
- HTML+CSS基础 权重的计算 权重计算规则
- gperf heap profiler
- Prism——Window 必须是树的根目录。不能将 Window 添加为 Visual 的子目录。
- c# Equal函数 and 运算符&#39;==&#39; (原发布 csdn 2017年10月15日 20:39:26)
- Java多线程——ThreadLocal类的原理和使用
- Lambda(一)lambda表达式初体验
- springmvc在使用@ModelAttribute注解获取Request和Response会产生线程并发不安全问题(转)
- CTF必备技能丨Linux Pwn入门教程——stack canary与绕过的思路