Monday, November 12, 2018

562. Longest Line of Consecutive One in Matrix

562Longest Line of Consecutive One in Matrix
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.
---------------------------

暴解就可以了
class Solution {   
    
    public int longestLine(int[][] M) {
        if (M.length == 0) return 0;
        int m = M.length, n = M[0].length;
        int len = 0;
        for (int i = 0; i < m; i++) {
            len = Math.max(len, check(M, i, 0, new int[]{0, 1}));
        }    
        
        for (int i = 0; i < n; i++) {
            len = Math.max(len, check(M, 0, i, new int[]{1, 0}));
        }
        
        for (int i = 0; i < m; i++) {
            len = Math.max(len, check(M, i, 0, new int[]{1, 1}));
            len = Math.max(len, check(M, i, n - 1, new int[]{1, -1}));
        }
        
        for (int i = 1; i < n; i++) {
            len = Math.max(len, check(M, 0, i, new int[]{1, 1}));
            len = Math.max(len, check(M, 0, n - i - 1, new int[]{1, -1}));
        }
        
        return len;
    }
    
    private int check(int[][] matrix, int row, int col, int[] dir) {
        int len = 0, count = 0;
        
        for (; row >= 0 && col >= 0 && row < matrix.length && col < matrix[0].length; row += dir[0], col += dir[1]) {
            if (matrix[row][col] == 1) {
                count++;
                len = Math.max(len, count);
            }else {
                count = 0;
            }
        }
        
        return len;
    }
}

No comments:

Post a Comment