java - 有没有办法做我在这里所做的事情,用 2 个循环而不是一个循环
问题描述
这是问题 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 个。我认为这会提高效率。
解决方案
如果您想将相邻数字的数量作为参数给出,则可能需要三个嵌套循环。
请参阅下面的实现,这对我来说看起来更清楚。
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 命名约定:Answer
answer
混合大小写,首字母小写
推荐阅读
- ruby - 在 Postgres 中将带有 UTC 的时间戳转换为毫秒
- node.js - nodejs从会话中删除变量
- javascript - 如何从 JavaScript 中的 Set 中删除对象
- mysql - 无法重新启动 mysql(有关详细信息,请参阅“systemctl status mysql.service”和“journalctl -xe”。)
- jquery - 从 jquery-1.11.1.js 迁移到 jquery-1.12.4.js
- google-chrome-extension - 如何在不打开空选项卡的情况下从扩展程序启动自定义 URI?
- spring-boot - 使用 JpaRepository 将 protobuf 直接保存为实体
- php - 使用 ajax 序列化文件(图像)并插入查询
- c# - 在数据网格上插入 PersianDate 时出错:无法评估表达式,因为当前线程处于堆栈溢出状态
- c# - 用于显示图像管理器对话框的 Enterprise Architect API