java - 30个连续数字的最大乘积

Question

一位 friend 向我提出了一道编程问题，其中给出了 1000 个字符的数字字符串。任务是找到 30 个连续数字的最大乘积。

虽然我的代码看起来是正确的，但答案似乎很低，这是为什么？

下面提供了该问题的相关代码。

  static String s = "2389748943892"; //... This number is actually 1000 characters.

  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int largest = 0;
    for(int i = 0; i < 970; i  ) {
      String cur = s.substring(i, i 30);
      int cur_val = 0;
      for(int x = 0; x < 30; x  ) {
        if(x == 0) {
          System.out.println(Integer.parseInt(cur.substring(0, 1)));
          cur_val = Integer.parseInt(cur.substring(x, 1)); 
        } else {
          cur_val = cur_val * Integer.parseInt(cur.substring(x, x 1));
        }

      }
      if(cur_val > largest) {
        largest = cur_val;
      }
      System.out.println("Largest: "   largest);
      // should be 8876473335152640000 but is 2013265920

    }
  }

Answer 1

编辑:啊，我读的是“慢”而不是“低”...好吧，忘记性能问题吧，我以为你在谈论。

但是，long 也对你没有帮助:计算 ln(9^30)/ln(2)，你得到的值略高于 95，因此你需要 96 位数字。那么尝试 Math.BigInteger!

<小时/>

这是由于过度使用了 substring(导致一直构造和销毁新的 String 对象)。由于您只对单个字符感兴趣，所以最好使用 s.charAt(n)。解析也很容易:只需从这样得到的字符中减去“0”即可。所以你得到:

for(int i = 0; i < 970; ++i)
{
    int cur_val = 0;
    for(int x = i; x < i + 30; ++x)
    {
        cur_val *= s.charAt(x) - '0';
    }
}
/* rest as you had already */

(好吧，我省略了打印子字符串)。

此外，在您发布的代码中，存在一些语法错误(substring i, i 30，显然缺少“+”)，并且您没有增加计数器变量(如果 < em>这也发生在你的代码中，你会以无限循环结束 - 但这样你就不会得到一个缓慢的结果，你根本不会得到任何结果。

您可能会包含一些捷径(例如，如果您在外循环中发现“0”，您就知道接下来 30 次迭代的结果将为 0，您可以跳过这些)，从而获得另一个加速。