将Array除以2个子数组,并检查乘法是否相等

Question

我在Java练习考试.我今天面临的一个问题是:给定一个带有n个数字的数组,我需要检查是否有2个子数组(不必相等)它们的乘法等于 - 如果有,则返回true,否则为false.例如:如果数组为:{2,15,3,4,2,5} - 如果数组为:{2,4,6,2,3,4}将返回True - 将返回False.

答案必须是递归的,没有任何循环.

所以我认为如果有2个子数组,它们的乘法相等则意味着整个数组的总乘数必须是平方根数.例如,在第一个数组中,它是3600,即60.

到目前为止,我找不到任何不适用的情况,但仍然不能确定它将涵盖所有可能的情况.

这是我的代码:

    public static boolean splitEqualMult(int[] a) {
      double multi = isArrSqrt(a,0);

      if(Math.sqrt(multi) == Math.floor(Math.sqrt(multi))) {
          return true;
    }

    return false;
}

private static double isArrSqrt(int[] a, int i) {

    if(i == a.length) {
        return 1;
    }

    return a[i] * isArrSqrt(a,i+1);
}

希望听到你的想法!

Answer 1

您的解决方案给出了误报。例如，数组{2,8}不能分为两个积相等的子数组，但您将返回true，因为 2*8 的平方根是 4。

当您尝试解决此类递归问题时，您应该尝试思考如果将输入大小减少 1 会发生什么。

假设给定的数组arr有一个有效的分割（分成两个具有相同乘积的子组）。这意味着，如果删除第一个元素a[0]，则必须能够将数组的其余部分分成两个子组，这样p1 == p2 * a[0]或p1 == p2 / a[0]，其中p1是第一组元素的乘积，p2是第一个组元素的乘积第二组。

这表明递归方法应该检查输入数组的给定尾部（即 arr[from]...arr[arr.length-1] 对于某些 from >= 0）是否存在分成两组，例如第一组的乘积除以第二组的乘积（反之亦然）等于给定因子：

public static boolean canSplit(int[] arr, int from, double factor)
{
    if (from == arr.length - 1) {
        return arr[from] == factor;
    }
    return canSplit(arr, from + 1, factor * arr[from]) || canSplit(arr, from + 1, factor / arr[from]);
}

初始调用将是：

public static boolean canSplit(int[] arr)
{
    if (arr.length < 2) {
        return false;
    } else {
        return canSplit(arr, 0, 1); // the second parameter is 0, since the first recursive call
                                    // applies to the whole array
                                    // the third parameter is 1, since we want to check if there 
                                    // are two groups such that the product of the first divided
                                    // by the product of the second is 1 (i.e. the two products
                                    // are equal)
    }
}

测试：

System.out.println (canSplit(new int[]{2,15,3,4,2,5}));
System.out.println (canSplit(new int[]{2,4,6,2,3,4}));
System.out.println (canSplit(new int[]{2,2,4}));
System.out.println (canSplit(new int[]{2,8}));

输出：

true
false
true
false