java - 给定一个由 0 和 1 组成的二进制矩阵。找出最长的 1 序列，无论是行式还是列式。 JAVA

Question

给定一个由 0 和 1 组成的二进制矩阵。找出最长的 1 序列，无论是按行还是按列。

0 0 0 1 0 0 
0 0 1 1 0 0
0 0 0 1 0 0

它应该返回最高计数 - 3。请帮忙用 Java 编写这个程序。我写了一个简单的算法，但它没有考虑顺序。

public int columnMaxSequence(int[][] matrix) {

    int maxSequence = 0;
    int max = 0;

    for (int i = 0; i < matrix[0].length; i++) {
        for (int j = 0; j < matrix.length; j++) {
            if (matrix[j][i] == 1) {
                max++;
            }
        }
        if (max > maxSequence) {
            maxSequence = max;
        }
        max = 0;
    }
    return maxSequence;
}

public int rowMaxSequence(int[][] matrix) {

    int maxSequence = 0;
    int max = 0;

    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[i].length; j++) {
            if (matrix[i][j] == 1) {
                max++;
            }
        }
        if (max > maxSequence) {
            maxSequence = max;
        }
        max = 0;
    }
    return maxSequence;
}

/*
 Returns the maximum sequence of 1s in a matrix.
 */
public int maxSequence(int[][] matrix) {

    int rowMaxSequence = rowMaxSequence(matrix);
    int columnMaxSequence = columnMaxSequence(matrix);

    if (rowMaxSequence >= columnMaxSequence) {
        return rowMaxSequence;
    } else {
        return columnMaxSequence;
    }
}

Answer 1

你应该试试这个:

void main(int[][] matrix)
{
    System.out.println(Math.max(columnMaxSequence(matrix), rowMaxSequence(matrix)));
}

public int columnMaxSequence(int[][] matrix)
{
    int max = 0;

    for(int i = 0; i < matrix[0].length; i++) // Column Index
    {
        int tempMax = 0;
        for(int j = 0; j < matrix.length; j++) // Row Index
        {
            if(matrix[j][i] == 1)
            {
                tempMax = 1;
                for(int k = j+1; k < matrix.length; k++)
                {
                    if(matrix[k][i] == 1)
                        tempMax++;
                    else break;
                }
                if(max < tempMax)
                    max = tempMax;
            }
        }
    }

    return max;
}

public int rowMaxSequence(int[][] matrix)
{
    int max = 0;

    for(int i = 0; i < matrix.length; i++)
    {
        int tempMax = 0;
        for(int j = 0; j < matrix[0].length; j++)
        {
            if(matrix[i][j] == 1)
            {
                tempMax = 1;
                for(int k = j+1; k < matrix[0].length; k++)
                {
                    if(matrix[i][k] == 1)
                        tempMax++;
                    else break;
                }
                if(max < tempMax)
                    max = tempMax;
            }
        }
    }

    return max;
}

解释-

对于 rowMaxSequence():

循环沿着矩阵向下，i 存储每一行​​索引的值。 j 存储第i 行中每个元素的索引。在 (i, j) 处，如果矩阵找到 1，则它会计算该行中 1 的数量，直到找到 0 - 然后中断。它会以相同的方式不断检查该行，当 orw 完成时，它会转到下一行。

对于 columnMaxSequence():

循环向右穿过矩阵，i 是当前列的索引。 j 是该列中的元素。如果 (j, i) 是 1，那么它会计算它下面的 1，直到找到 0。然后它坏了。它以这种方式不断检查该列，然后移动到正确的列。