关于Problem8的改善
关于Problem8的改进
问题描述
Find the greatest product of five consecutive digits in the 1000-digit number.
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
得到连续的五个数的最大乘积
思考:
每当我们得到当前五个数的乘积时,当挪动到下一个数,我们可以将保存的乘积乘以新的数除以之前五个数的第一个数。
如下
下标:0 1 2 3 4 5 6
数值:1 2 3 4 5 6 7
前五个数的乘积 result = 1*2*3*4*5
乘积中的第一个数first = 1
则求新的五个数的乘积 newResutl = result*6/first;
当然,实际运算时,我们还可以判断当前result和first是否为0
通过这样的运算,效率提高了很多~
自己逐步优化,写了四个方法
如下:
运算结果如下:
40824 count_for1:4975
40824 count_for2:2495
40824 count_for2:2305
40824 count_for2:820
效率提高的不是一般的多啊~
问题描述
Find the greatest product of five consecutive digits in the 1000-digit number.
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
得到连续的五个数的最大乘积
思考:
每当我们得到当前五个数的乘积时,当挪动到下一个数,我们可以将保存的乘积乘以新的数除以之前五个数的第一个数。
如下
下标:0 1 2 3 4 5 6
数值:1 2 3 4 5 6 7
前五个数的乘积 result = 1*2*3*4*5
乘积中的第一个数first = 1
则求新的五个数的乘积 newResutl = result*6/first;
当然,实际运算时,我们还可以判断当前result和first是否为0
通过这样的运算,效率提高了很多~
自己逐步优化,写了四个方法
如下:
public static int find_five_consecutive1() { int result = 1; int max = 0; String str = read(); int begin = 0; int end = str.length(); int step = 5; for (int i = begin; i < end - step; i++) { result = 1; for (int j = 0; j < step; j++) { result = result * Integer.parseInt(str.charAt(i + j) + ""); count_for1++; } if (result > max) { max = result; } } return max; } public static int find_five_consecutive2() { int result = 1; int max = 0; String str = read(); int begin = 0; int end = str.length(); int step = 5; for (int i = begin; i < end - step; i++) { result = 1; for (int j = 0; j < step; j++) { if (str.charAt(i + j) == '0') { i = i + step + step - j; break; } else { int number = Integer.parseInt(str.charAt(i + j) + ""); result = result * number; count_for2++; } } if (result > max) { max = result; } } return max; } public static int find_five_consecutive3() { int result = 0; String str = read(); int step = 5; for (int i = 0; i < str.length(); i++) { if (str.charAt(i) == '0') { i = i + 5; count_for3++; } else { int multi = 1; for (int j = 0; j < step; j++) { count_for3++; char c = str.charAt(i + j); if (c == '0') { i = i + j + step; break; } else { multi *= Integer.valueOf(c + ""); if (multi > result) { result = multi; } } } } } return result; } public static int find_five_consecutive4() { int result = 1; int max = 1; String str = read(); int step = 5; int first = Integer.valueOf(str.charAt(0) + ""); for (int i = 0; i < step; i++) { count_for4++; char c = str.charAt(i); result *= Integer.valueOf(c + ""); } max = result; for (int i = 5; i < str.length(); i++) { if (result == 0) { // 重新计算 result = 1; first = Integer.valueOf(str.charAt(i) + ""); for (int j = 0; j < step; j++) { count_for4++; result *= Integer.valueOf(str.charAt(i + j) + ""); } if(result>max){ max = result; } i = i+step-1; } else{ count_for4++; if(str.charAt(i)=='0'){ result = 0; i = i+4; continue; }else{ result = (result*Integer.valueOf(str.charAt(i)+""))/first; first = Integer.valueOf(str.charAt(i-4)+""); if(result>max){ max = result; } } } } return max; }
运算结果如下:
40824 count_for1:4975
40824 count_for2:2495
40824 count_for2:2305
40824 count_for2:820
效率提高的不是一般的多啊~