求乘法后的最后2位数字

Question

我有一个整数数组，我的任务是将所有这些数字相乘后得到最后 2 位数字。我想出了下面的代码：static void process(int array[]) {    if (array.length <= 0) {        System.out.println("-1");        return;    }    int answer = array[0] % 100;    for (int i = 1; i < array.length; i++) {        answer = (answer * array[i] % 100) % 100;    }    System.out.println(answer);}我觉得这是一种更好的方法，但是当我在一次考试中使用它时，它只通过了四分之二的测试用例。由于性能问题，测试用例失败。失败的测试用例被隐藏，因此无法看到它们。我什至尝试了另一种方法，例如将 long 变量初始化为 1，然后使用 for 循环并将 long 变量与数组元素相乘。最终从 long 变量中获取最后两位数字，即使在 2 个测试用例中也失败了。有没有更好的方法来解决这个问题。

Answer 1

有一些潜在的捷径。乘以一个以 0 结尾的数字或两个分别以 2 和 5 结尾的数字将保证最后一位数字为 0。这样做两次会使最后两位数字为 00，您可以提前打印结果。您可以检查您的答案是否为 00，如果发生这种情况则跳出循环。

这会减慢针对针对此检查定制的数据的算法。然而，一个大的（>1000）随机数字集几乎可以保证提前以 00 结束，并且比您最初的方法更快。

示例代码：

static void process(int array[]) {

  if (array.length <= 0) {

      System.out.println("-1");

      return;

  }

  int answer = array[0] % 100;

  for (int i = 1; i < array.length; i++) {

    if(answer == 0) {

       break;

    }

    answer = (answer * array[i] % 100) % 100;

  }

  System.out.println(answer);

}

Answer 2

您确定这是由于性能问题吗？如果是，那么我认为这是一个愚蠢的问题，因为 O(n) 是你能得到的最好的。

我的猜测是因为你的答案不正确。例如，如果您的答案是“1”，那么它实际上可能是“01”。因此，正确的实施会考虑到这一点。

boolean atLeast10 = false;

int answer = 1;

int i = 0;

for (; i < array.length && !atLeast10; i++) {

    if (array[i] == 0) {

        System.out.println(0);

        return;

    }

    answer = answer * array[i];

    if (answer >= 10)

        atLeast10 = true;

}

answer = answer % 100;

for (; i < array.length; i++) {

    if (array[i] == 0) {

        System.out.println(0);

        return;

    }

    answer = (answer * array[i] % 100) % 100;

}

if (!atLeast10 || answer >= 10)

    System.out.println(answer);

else

    System.out.println("0" + answer);

顺便提一句。仅当元素为 0 时才可能使用快捷方式，这又是因为即使数字以“00”结尾，数组中也可能后面跟着一个 0，然后答案是“0”而不是“00”，尽管我喜欢这个想法。