java - Java中的Codility MaxPathFromTheLeftTopCorner练习

Question

我正在努力解决这个问题https://app.codility.com/programmers/custom_challenge/technetium2019/

这是练习的文本：

You are given a matrix A consisting of N rows and M columns, where each cell contains a digit. Your task is to find a continuous sequence of neighbouring cells, starting in the top-left corner and ending in the bottom-right corner (going only down and right), that creates the biggest possible integer by concatenation of digits on the path. By neighbouring cells we mean cells that have exactly one common side.

    Write a function:

    class Solution { public String solution(int[][] A); }

    that, given matrix A consisting of N rows and M columns, returns a string which represents the sequence of cells that we should pick to obtain the biggest possible integer.

    For example, given the following matrix A:

    [9 9 7] [9 7 2] [6 9 5] [9 1 2]

    the function should return "997952", because you can obtain such a sequence by choosing a path as shown below:

    [9 9 *] [* 7 *] [* 9 5] [* * 2]

    Write an efficient algorithm for the following assumptions:

            N and M are integers within the range [1..1,000];
            each element of matrix A is an integer within the range [1..9].

我无法达到 100%，因为我在矩阵的值都相同的情况下失败了。

我尝试按照练习中的要求从左到右并向下阅读矩阵，但我认为我误解了这个问题。

这是我的代码：

static String sol(int[][] A) {

    String st = "";

    int v = A.length - 1;
    int h = A[0].length - 1;
    if (h == 0) {
        for (int i = 0; i <= v; i++) {
            st = st.concat(String.valueOf(A[i][0]));
        }
    } else if (v == 0) {
        for (int i = 0; i <= h; i++) {
            st = st.concat(String.valueOf(A[0][i]));
        }

    } else {

        st = st.concat(String.valueOf(A[0][0]));

        int m = 0; //vertical
        int n = 0; // horizontal
        while(m<v && n<h) {
            if(A[m+1][n]>=A[m][n+1]){
                st = st.concat(String.valueOf(A[m+1][n]));
                m++;
            }else {
                st = st.concat(String.valueOf(A[m][n+1]));
                n++;
            }

        }

        st = st.concat(String.valueOf(A[v][h]));
    }


    return st;
}

我想我需要遍历矩阵来计算路径的权重，但我不知道如何进行。

在这里我找到了一个解决方案，但它似乎仅限于 3x3 矩阵。

标签： java

Answer 1

这是我对问题的解决方案，但它未能通过最后的速度测试（我得到 77%）。不知道我是否可以优化它甚至更多...

public static String solution(int[][] A) {
    // write your code in Java SE 8

    int al = A.length;
    int all = A[0].length;

    BigInteger[][] res = new BigInteger[al+1][];
    for(int i=0; i<al+1; i++){
        res[i] = new BigInteger[all+1];
        for(int j=0; j<all+1; j++){
            res[i][j] = BigInteger.valueOf(0);
        }
    }

    for(int i=1; i<al+1; i++){
        for(int j=1; j<all+1; j++){
            res[i][j] = res[i-1][j]
                    .max(res[i][j-1])
                    .multiply(BigInteger.valueOf(10))
                    .add(BigInteger.valueOf(A[i-1][j-1]));
        }
    }

    return res[al][all].toString();

}