[LeetCode] 562. Longest Line of Consecutive One in

tomlingtm 发布于2019-08-16 13:54 / 3484人阅读

Problem

Given a 01 matrix M, find the longest line of consecutive one in the matrix. The line could be horizontal, vertical, diagonal or anti-diagonal.
Example:
Input:
[[0,1,1,0],
[0,1,1,0],
[0,0,0,1]]
Output: 3
Hint: The number of elements in the given matrix will not exceed 10,000.

Solution

class Solution {
    public int longestLine(int[][] M) {
        if (M == null || M.length == 0 || M[0].length == 0) return 0;
        int max = 0, m = M.length, n = M[0].length;
        int[] row = new int[m];
        int[] col = new int[n];
        int[] d = new int[m+n];
        int[] ad = new int[m+n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (M[i][j] == 1) {
                    row[i]++;
                    col[j]++;
                    d[i+j]++;
                    ad[j-i+m]++;
                    max = Math.max(max, Math.max(row[i], col[j]));
                    max = Math.max(max, Math.max(d[i+j], ad[j-i+m]));
                } else {
                    row[i] = 0;
                    col[j] = 0;
                    d[i+j] = 0;
                    ad[j-i+m] = 0;
                }
            }
        }
        return max;
    }
}

云服务器 GPU云服务器 Longest Consecutive LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72538.html

[LeetCode] 549. Binary Tree Longest Consecutive Se

Problem Given a binary tree, you need to find the length of Longest Consecutive Path in Binary Tree. Especially, this path can be either increasing or decreasing. For example, [1,2,3,4] and [4,3,2,1] ...

bingchen 2019-08-19 11:11 评论0 收藏0
[Leetcode] Binary Tree Longest Consecutive Sequenc

摘要：递归法复杂度时间空间思路因为要找最长的连续路径，我们在遍历树的时候需要两个信息，一是目前连起来的路径有多长，二是目前路径的上一个节点的值。代码判断当前是否连续返回当前长度，左子树长度，和右子树长度中较大的那个 Binary Tree Longest Consecutive Sequence Given a binary tree, find the length of the lon...

xi4oh4o 2019-08-14 16:16 评论0 收藏0
[Leetcode] Longest Consecutive Sequence 最长连续数列

摘要：集合法复杂度时间空间思路将所有数都加入集合中，然后再遍历这些数，因为我们能的判断某个数是否在集合中，所以我们可以一个个向上或者向下检查。时间复杂度仍是，因为我们不会检查不存在于数组的数，而存在于数组的数也只会检查一次。 Longest Consecutive Sequence Given an unsorted array of integers, find the length o...

lei___ 2019-08-14 12:38 评论0 收藏0
[LintCode/LeetCode] Longest Consecutive Sequence

摘要：先排序，然后用数组记录每一位上连续序列的长度，每次循环更新最大值存为。 Problem Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Clarification Your algorithm should run in O(n) com...

buildupchao 2019-08-14 16:25 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0