免费建设网站制作,设计工作室网站源码,半成品网站,班级优化大师网页版登录文章目录1. 题目2. 解题1. 题目
给定一个01矩阵 M#xff0c;找到矩阵中最长的连续1线段。 这条线段可以是水平的、垂直的、对角线的或者反对角线的。
示例:
输入:
[[0,1,1,0],[0,1,1,0],[0,0,0,1]]
输出: 3
提示: 给定矩阵中的元素数量不会超过 10,000。来源#xff1a;力…
文章目录1. 题目2. 解题1. 题目
给定一个01矩阵 M找到矩阵中最长的连续1线段。 这条线段可以是水平的、垂直的、对角线的或者反对角线的。
示例:
输入:
[[0,1,1,0],[0,1,1,0],[0,0,0,1]]
输出: 3
提示: 给定矩阵中的元素数量不会超过 10,000。来源力扣LeetCode 链接https://leetcode-cn.com/problems/longest-line-of-consecutive-one-in-matrix 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
建立四个方向的DP数组即可求各方向的前缀和遇到0从新开始累计
class Solution {
public:int longestLine(vectorvectorint M) {if(M.empty() || M[0].empty())return 0;int m M.size(), n M[0].size(), i, j;vectorvectorint h(m,vectorint(n,0)),v(m,vectorint(n,0)), p_45(m,vectorint(n,0)),n_45(m,vectorint(n,0));int maxlen 0;for(i 0; i m; i) {for(j 0; j n; j){if(M[i][j] 0)continue;h[i][j] i-10 ? h[i-1][j]1 : 1;v[i][j] j-10 ? v[i][j-1]1 : 1;p_45[i][j] (i0 j1 n) ? p_45[i-1][j1]1 : 1;n_45[i][j] (i0 j0) ? n_45[i-1][j-1]1 : 1;maxlen max(maxlen,h[i][j]);maxlen max(maxlen,v[i][j]);maxlen max(maxlen,p_45[i][j]);maxlen max(maxlen,n_45[i][j]);}}return maxlen;}
};120 ms 28.3 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
