1

问题是“给定一个整数数组，是否可以将整数分成两组，使得一组的和是 10 的倍数，而另一组的和是奇数。每个 int 必须在一个组或其他。编写一个递归帮助器方法，它接受你喜欢的任何参数，并从 splitOdd10() 对你的递归帮助器进行初始调用。（不需要循环。）“

我在下面有一个正确的解决方案，但我所有的返回值都与正确的相反。解决它的hacky方法只是在最后切换布尔值，但我想知道我在概念上犯了什么错误。

public  boolean splitOdd10(int[] nums) { 
    if (nums.length==0) return false;

    //Should not have the ! operator
    return (!splitOdd10(nums,0,1));

}
public  Boolean splitOdd10(int[] nums, int lowerBound,int upperBound) {
    int split10Sum=getSum(nums,lowerBound,upperBound);
    int splitOddSum=getSum(nums)-split10Sum;
    if (split10Sum % 10 == 0 && splitOddSum % 2 == 0)   return true;

    if (upperBound < nums.length)   {
        if (splitOdd10(nums,lowerBound,upperBound+1)) return true;
        if (splitOdd10(nums,lowerBound+1,upperBound+1)) return true;
    }
    if (lowerBound < upperBound) 
        if (splitOdd10(nums,lowerBound+1,upperBound)) return true;
    return false;
}


public  int getSum(int[] nums)    {
return getSum(nums,0,nums.length);
}
public  int getSum(int[] nums, int lowerBound, int upperBound) {
    if (lowerBound == upperBound)   return 0;
return nums[lowerBound]+getSum(nums,lowerBound+1,upperBound);
}
4

1 回答 1

3

回答中需要注意两点：

  1. splitOdd10(new int[] {10, 1, 10, })将返回 false，而不是 true。
  2. splitOdd10(int[] nums, int lowerBound,int upperBound)如果当前分组10Sum可以被 10 整除，并且可以被 2 整除，则您的方法返回 true rest，也就是说，如果它是偶数，而不是奇数。

具体来说。对于第二点：

if (split10Sum % 10 == 0 && splitOddSum % 2 == 0)   return true;

应该

if (split10Sum % 10 == 0 && splitOddSum % 2 == 1)   return true;

第一点可能没问题，这取决于您要解决的问题，也就是说，如果您需要将数组“拆分”成两部分，那么它会起作用，但可能会产生太多误报。具体来说，您需要考虑以下数组的答案应该是什么：

[10, 10, 1]
[1, 10, 10]
[1, 10, 2]
[1, 2, 10]
[10, 1, 10]
[10, 1, 2]
于 2013-10-14T19:39:06.820 回答