Massive Algorithms: LeetCode 562 - Longest Line of Consecutive One in Matrix

LeetCode 562 - Longest Line of Consecutive One in Matrix

http://bookshadow.com/weblog/2017/04/23/leetcode-longest-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.

给定01矩阵M，计算矩阵中一条线上连续1的最大长度。一条线可以为横向、纵向、主对角线、反对角线。

提示：给定矩阵元素个数不超过10,000

X.
https://segmentfault.com/a/1190000017237619

    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;
    }

http://www.cnblogs.com/grandyang/p/6900866.html

如果上面的解法的坐标转换不好想的话，我们也可以考虑用DP解法来做，我们建立一个三维dp数组，其中dp[i][j][k]表示从开头遍历到数字nums[i][j]为止，第k种情况的连续1的个数，k的值为0，1，2，3，分别对应水平，竖直，对角线和逆对角线这四种情况。之后就是更新dp数组的过程了，如果如果数字为0的情况直接跳过，然后水平方向就加上前一个的dp值，竖直方向加上上面一个数字的dp值，对角线方向就加上右上方数字的dp值，逆对角线就加上左上方数字的dp值，然后每个值都用来更新结果res

https://www.jianshu.com/p/6bdf7b29b752

dp[i][j][k]表示从开头遍历到数字nums[i][j]为止，第k种情况的连续1的个数.
k的值为0，1，2，3，分别对应水平，竖直，对角线和逆对角线这四种情况。
更新dp数组过程:
如果如果数字为0的情况直接跳过，然后水平方向就加上前一个的dp值，竖直方向加上上面一个数字的dp值，对角线方向就加上右上方数字的dp值，逆对角线就加上左上方数字的dp值，然后每个值都用来更新结果res.

https://discuss.leetcode.com/topic/87197/java-o-nm-time-dp-solution

public int longestLine(int[][] M) {
    int n = M.length, max = 0;
    if (n == 0) return max;
    int m = M[0].length;
    int[][][] dp = new int[n][m][4];
    for (int i=0;i<n;i++) 
        for (int j=0;j<m;j++) {
            if (M[i][j] == 0) continue;
            for (int k=0;k<4;k++) dp[i][j][k] = 1;
            if (j > 0 && M[i][j-1] == 1) dp[i][j][0] += dp[i][j-1][0]; // horizontal line
            if (j > 0 && i > 0 &&  M[i-1][j-1] == 1) dp[i][j][1] += dp[i-1][j-1][1]; // diagonal line
            if (i > 0 && M[i-1][j] == 1) dp[i][j][2] += dp[i-1][j][2]; // vertical line
            if (j < m-1 && i > 0 &&  M[i-1][j+1] == 1) dp[i][j][3] += dp[i-1][j+1][3]; // anti-diagonal line
            max = Math.max(max, Math.max(dp[i][j][0], dp[i][j][1]));
            max = Math.max(max, Math.max(dp[i][j][2], dp[i][j][3]));
        }
    return max;

动态规划（Dynamic Programming）

分表用二维数组h[x][y], v[x][y], d[x][y], a[x][y]表示以元素M[x][y]结尾，横向、纵向、主对角线、反对角线连续1的最大长度

状态转移方程如下：

h[x][y] = M[x][y] * (h[x - 1][y]  + 1)

v[x][y] = M[x][y] * (v[x][y - 1]  + 1)

d[x][y] = M[x][y] * (d[x - 1][y - 1]  + 1)

a[x][y] = M[x][y] * (a[x + 1][y - 1]  + 1)

https://discuss.leetcode.com/topic/87204/verbose-java-solution-hashset-only-search-later-cells

For each unvisited direction of each 1, we search length of adjacent 1s and mark those 1s as visited in that direction. And we only need to search 4 directions: right, down, down-right, down-left. We only access each cell at max 4 times, so time complexity is O(mn). m = number of rows, n = number of columns.

    public int longestLine(int[][] M) {
        int m = M.length;
        if (m <= 0) return 0;
        int n = M[0].length;
        if (n <= 0) return 0;
        
        int max = 0;
        int[][] dirs = {{0, 1}, {1, 0}, {1, 1}, {1, -1}};
        List<Set<String>> memo = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            memo.add(new HashSet<String>());
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (M[i][j] == 0) continue;
                String pos = i + "," + j;
                for (int k = 0; k < 4; k++) {
                    if (!memo.get(k).contains(pos)) {
                        int count = 0;
                        for (int r = i, c = j; r < m && r >= 0 && c < n && c >= 0; r += dirs[k][0], c += dirs[k][1]) {
                            if (M[r][c] == 1) {
                                count++;
                                memo.get(k).add(r + "," + c);
                            }
                            else break;
                        }
                        max = Math.max(max, count);
                    }
                }
            }
        }
        
        return max;
    }

https://discuss.leetcode.com/topic/87389/simple-and-concise-java-solution-easy-to-understand-o-m-n-space

public int longestLine(int[][] M) {
    if (M.length == 0 || M[0].length == 0) {
        return 0;
    }
    int max = 0;
    int[] col = new int[M[0].length];
    int[] diag = new int[M.length + M[0].length];
    int[] antiD = new int[M.length + M[0].length];
    for (int i = 0; i < M.length; i++) {
        int row = 0;
        for (int j = 0; j < M[0].length; j++) {
            if (M[i][j] == 1) {
                row++;
                col[j]++;
                diag[j + i]++;
                antiD[j - i + M.length]++;
                max = Math.max(max, row);
                max = Math.max(max, col[j]);
                max = Math.max(max, diag[j + i]);
                max = Math.max(max, antiD[j - i + M.length]);
            } else {
                row = 0;
                col[j] = 0;
                diag[j + i] = 0;
                antiD[j - i + M.length] = 0;
            }
        }
    }
    return max;

X.
https://www.jianshu.com/p/60d9c17617b8

第一种方法是直接做搜索，LC现在感觉大数据的test case少了，所以繁琐一点也是能过的.
对于每一个点，朝8个方向进行搜索（其实朝前向的四个方向就可以）同时将扫过的点记录下来，以便不往回找.

https://blog.csdn.net/katrina95/article/details/79311355
递归的解法，同时maintain一个最大值，注意8个方向中只需要走4个方向即可。

下面我们来优化空间复杂度，用一种类似于DFS的思路来解决问题，我们在遍历到为1的点时，对其水平方向，竖直方向，对角线方向和逆对角线方向分别不停遍历，直到越界或者遇到为0的数字，同时用计数器来累计1的个数，这样就可以用来更新结果res了，就不用把每个中间结果都保存下来

    int longestLine(vector<vector<int>>& M) {
        if (M.empty() || M[0].empty()) return 0;
        int m = M.size(), n = M[0].size(), res = 0;
        vector<vector<int>> dirs{{1,0},{0,1},{-1,-1},{-1,1}};
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (M[i][j] == 0) continue;
                for (int k = 0; k < 4; ++k) {
                    int cnt = 0, x = i, y = j;
                    while (x >= 0 && x < m && y >= 0 && y < n && M[x][y] == 1) {
                        x += dirs[k][0];
                        y += dirs[k][1];
                        ++cnt;
                    }
                    res = max(res, cnt);
                }
            }
        }
        return res;
    }

https://discuss.leetcode.com/topic/87228/java-strightforward-solution

    public int longestLine(int[][] M) {
        if(M == null) return 0;
        int res = 0;
        for(int i =0;i<M.length;i++){
            for(int j = 0;j<M[0].length;j++){
                if(M[i][j] == 1){
                    res = Math.max(res,getMaxOneLine(M, i, j));
                }
            }
        }
        return res;
    }
    final int [][] dirs = new int[][]{{1,0},{0,1},{1,1},{1,-1}};
    private int getMaxOneLine(int [][] M, int x, int y){
        int res = 1;
        for(int [] dir:dirs){
            int i = x+dir[0];
            int j = y+dir[1];
            int count = 1;
            while(isValidPosition(M, i, j) && M[i][j] == 1){
                i+=dir[0];
                j+=dir[1];
                count++;
            }
            res = Math.max(count,res);
        }
        return res;
    }
    
    private boolean isValidPosition(int M[][], int i, int j){
        return (i<M.length && j<M[0].length && i>=0 && j>=0);
    }

lc solution：用三维数组压缩代码

public int longestLine(int[][] M) {

int rows = M.length;

if (rows == 0) return 0;

int cols = M[0].length;

int res = 0;

// 0 horizaental, 1 vertical, 2 diagonal, 3 anti-diagonal

int[][][] dp = new int[rows][cols][4];

for (int i = 0 ; i < rows ; i++) {

for (int j = 0 ; j < cols ; j++) {

if (M[i][j] == 1) {

dp[i][j][0] = j > 0 ? dp[i][j-1][0] + 1 : 1;

dp[i][j][1] = i > 0 ? dp[i-1][j][1] + 1 : 1;

dp[i][j][2] = (i > 0 && j > 0) ? dp[i-1][j-1][2] + 1 : 1;

dp[i][j][3] = (i > 0 && j < cols - 1) ? dp[i-1][j+1][3] + 1 : 1;

res = Math.max(dp[i][j][0], res);

res = Math.max(dp[i][j][1], res);

res = Math.max(dp[i][j][2], res);

res = Math.max(dp[i][j][3], res);

}

return res;

}

LeetCode 562 - Longest Line of Consecutive One in Matrix

Labels

Popular Posts