草庐IT

java - 将 Array 划分为 2 个子数组并检查乘法是否相等

coder 2024-04-01 原文

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

答案必须是递归的，没有任何循环。

所以我想，如果有2个子数组，它们的乘积相等，这意味着整个数组的总乘数必须是一个平方根数。例如，在第一个数组中，它是 3600，即 60。

到目前为止，我还没有找到它不适用的任何情况，但仍然不能 100% 确定它是否涵盖所有可能的情况。

这是我的代码:

    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);
}

想听听您的想法!

最佳答案

您的解决方案给出了误报。例如，数组 {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] 对于大于等于 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

关于java - 将 Array 划分为 2 个子数组并检查乘法是否相等，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53898486/

个子ArraycodecanSplitsectionjavarecursionsqrt

有关java - 将 Array 划分为 2 个子数组并检查乘法是否相等的更多相关文章

  1. ruby-on-rails - 如何验证 update_all 是否实际在 Rails 中更新 - 2

    给定这段代码defcreate@upgrades=User.update_all(["role=?","upgraded"],:id=>params[:upgrade])redirect_toadmin_upgrades_path,:notice=>"Successfullyupgradeduser."end我如何在该操作中实际验证它们是否已保存或未重定向到适当的页面和消息？ 最佳答案 在Rails3中，update_all不返回任何有意义的信息，除了已更新的记录数(这可能取决于您的DBMS是否返回该信息)。http://ar.ru

  2. ruby - 在 Ruby 中实现 `call_user_func_array` - 2

    我怎样才能完成http://php.net/manual/en/function.call-user-func-array.php在ruby中？所以我可以这样做:classAppdeffoo(a,b)putsa+benddefbarargs=[1,2]App.send(:foo,args)#doesn'tworkApp.send(:foo,args[0],args[1])#doeswork,butdoesnotscaleendend 最佳答案 尝试分解数组App.send(:foo,*args)

  3. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  4. ruby - 如何以所有可能的方式将字符串拆分为长度最多为 3 的连续子字符串？ - 2

    我试图获取一个长度在1到10之间的字符串，并输出将字符串分解为大小为1、2或3的连续子字符串的所有可能方式。例如:输入:123456将整数分割成单个字符，然后继续查找组合。该代码将返回以下所有数组。[1,2,3,4,5,6][12,3,4,5,6][1,23,4,5,6][1,2,34,5,6][1,2,3,45,6][1,2,3,4,56][12,34,5,6][12,3,45,6][12,3,4,56][1,23,45,6][1,2,34,56][1,23,4,56][12,34,56][123,4,5,6][1,234,5,6][1,2,345,6][1,2,3,456][123

  5. ruby - 多次弹出/移动 ruby​​ 数组 - 2

    我的代码目前看起来像这样numbers=[1,2,3,4,5]defpop_threepop=[]3.times{pop有没有办法在一行中完成pop_three方法中的内容？我基本上想做类似numbers.slice(0,3)的事情，但要删除切片中的数组项。嗯...嗯，我想我刚刚意识到我可以试试slice! 最佳答案 是numbers.pop(3)或者numbers.shift(3)如果你想要另一边。 关于ruby-多次弹出/移动ruby​​数组，我们在StackOverflow上找到一

  6. ruby - 将数组的内容转换为 int - 2

    我需要读入一个包含数字列表的文件。此代码读取文件并将其放入二维数组中。现在我需要获取数组中所有数字的平均值，但我需要将数组的内容更改为int。有什么想法可以将to_i方法放在哪里吗？ClassTerraindefinitializefile_name@input=IO.readlines(file_name)#readinfile@size=@input[0].to_i@land=[@size]x=1whilex 最佳答案 只需将数组映射为整数:@land边注如果你想得到一条线的平均值，你可以这样做:values=@input[x]

  7. ruby - 检查 "command"的输出应该包含 NilClass 的意外崩溃 - 2

    为了将Cucumber用于命令行脚本，我按照提供的说明安装了arubagem。它在我的Gemfile中，我可以验证是否安装了正确的版本并且我已经包含了require'aruba/cucumber'在'features/env.rb'中为了确保它能正常工作，我写了以下场景:@announceScenario:Testingcucumber/arubaGivenablankslateThentheoutputfrom"ls-la"shouldcontain"drw"假设事情应该失败。它确实失败了，但失败的原因是错误的:@announceScenario:Testingcucumber/ar

  8. ruby - Ruby 的 Hash 在比较键时使用哪种相等性测试？ - 2

    我有一个围绕一些对象的包装类，我想将这些对象用作散列中的键。包装对象和解包装对象应映射到相同的键。一个简单的例子是这样的:classAattr_reader:xdefinitialize(inner)@inner=innerenddefx;@inner.x;enddef==(other)@inner.x==other.xendenda=A.new(o)#oisjustanyobjectthatallowso.xb=A.new(o)h={a=>5}ph[a]#5ph[b]#nil,shouldbe5ph[o]#nil,shouldbe5我试过==、===、eq?并散列所有无济于事。

  9. ruby - 通过 erb 模板输出 ruby​​ 数组 - 2

    我正在使用puppet为ruby​​程序提供一组常量。我需要提供一组主机名，我的程序将对其进行迭代。在我之前使用的bash脚本中，我只是将它作为一个puppet变量hosts=>"host1,host2"我将其提供给bash脚本作为HOSTS=显然这对ruby​​不太适用——我需要它的格式hosts=["host1","host2"]自从phosts和putsmy_array.inspect提供输出["host1","host2"]我希望使用其中之一。不幸的是，我终其一生都无法弄清楚如何让它发挥作用。我尝试了以下各项:我发现某处他们指出我需要在函数调用前放置“function_”……这

  10. Ruby Koans about_array_assignment - 非平行与平行分配歧视 - 2

    通过ruby​​koans.com，我在about_array_assignment.rb中遇到了这两段代码你怎么知道第一个是非并行赋值，第二个是一个变量的并行赋值？在我看来，除了命名差异之外，代码几乎完全相同。4deftest_non_parallel_assignment5names=["John","Smith"]6assert_equal["John","Smith"],names7end45deftest_parallel_assignment_with_one_variable46first_name,=["John","Smith"]47assert_equal'John

随机推荐