java - 有没有一种方法可以完成我在这里所做的事情，用 2 个循环而不是一个循环

Question

这是第 11 题，欧拉计划。代码运行良好，运行时间不到 5 秒，但时间复杂度很差。它有 3 个嵌套循环。

背景:我的目标是，给定一个二维整数方形数组，我们能否找到对角线上和一行中 x 个相邻数字的最大乘积。

public static long leftD(int[][] square,int x){
    /*This method finds the largest product of x numbers
    on any given left diagonal in a square
    */
    int rows=0,columns=0;
    int count=0;
    long product=1,largestProduct=0,Answer=0;
    int index=0;
    for(int rowN=0,colN=square[rowN].length-1;rowN<square.length-1 && colN>0;colN--){
        /*Outer for loop controls inner for loop
        makes it move across/down after each downward
        diagonal is found. colN is the column we start on and
        rowN is the row we start on.
        */
        for(rows=rowN,columns=colN;rows<(square.length-x) && columns>=x-1;rows++,columns--){
            //Above for loop gets one full diagonal
            /*Also for clarity, the length of the column equals the row #.
            The length of the diagonal equals the length of the column aka row #.
            Thus "rows" also equals the length of a given diagonal.
            */
            for(int r=rows,c=columns;c>(columns-x);c--,r++){
                int num=square[r][c];
                product=product*num;
            }
            largestProduct=(product>largestProduct)? product:largestProduct;
            product=1;
        }
        count++;
        //System.out.printf("The largest product of left diagonal is %,d on diagonal %d\n",largestProduct,count);
        product=1;
        Answer=(largestProduct>Answer)? largestProduct:Answer;
        largestProduct=0;
        if(colN==1){
            /*so if you have iterated through all diagonals
            (a diagonal has at least to terms based on how this code is made)
            of a given row, then start back from the last column, colN,(left most column)
            and let the current row, rowN, go down by one.
            */
            colN=square[rowN].length;//cause loop will imediately update this value
            //to colN--;
            rowN++;
        }
    } 
    System.out.printf("The largest product in all left diagonals is %,d\n",Answer);
    return Answer;
}

public static long R(int[][] square,int x){
    /*This method finds the largest product of x numbers
    on any given row in a square
    */
    long product=1;
    long Answer=1,count=0;
    for(int rowN=0;rowN<square.length;rowN++){//for as many rows in square

        for(int col=0;col<square[rowN].length-(x-1);col++){//for length of each row
            //-x cause we go across by x terms
            for(int i=col;i<(col+x);i++){//for the user given # x
                int number=square[rowN][i];
                product=product*number;
            }
            Answer=(product>Answer)? product:Answer;
            product=1;
        }

    }
    System.out.printf("The largest product in rows is %,d\n",Answer);
    return Answer;
}

我得到了我所期望的。答案是正确的，但我真正的问题是:每个方法是否可以只有 2 个嵌套循环而不是 3 个？我认为这会提高效率。

Answer 1

如果您想将相邻数字的数量作为参数给出，也许需要三个嵌套循环。

请参阅下面的实现，对我来说看起来更清晰。

public static int eulerProblem11(int[][] mx, int n) {
    int max = 0, east, south, se, sw;
    for(int i = 0; i < mx.length - n + 1; i++) {
        int[] row0 = mx[i];                // subsquare, first row
        for(int j = 0; j < row0.length - n + 1; j++) {
            east = south = se = row0[j];   // subsquare, upper left corner
            sw = row0[j + n - 1];          // subsquare, upper right corner
            for(int k = 1; k < n; k++) {
                int[] rowX = mx[i + k];    // subsquare Nth row
                east *= row0[j + k];       // multiply with the neighbor on right side 
                south *= rowX[j];          // multiply with neighbor below
                se *= rowX[j + k];         // multiply with the neighbor on SE
                sw *= rowX[j + n - k - 1]; // multiply with the neighbor on SW
            }
            max = max(max, east, south, se, sw);
        }
    }
    return max;
}

public static int max(int max, int ... list) {
    for(int n : list) {
        if (n > max) {
            max = n;
        }
    }
    return max;
}

PS。您应该关注 Java Naming Conventions还可以使用变量 Answer (→ answer):

mixed case with a lowercase first letter