Java算法问题

Question

问题陈述::在Java中,给定一个整数数组,是否可以选择一组整数的组,使得该组与给定目标相加,并具有以下附加约束:如果数组中有数字,则相邻且相同的值,它们必须全部被选中,或者都不被选择.例如,对于数组{1,2,2,2,5,2},必须选择或不选择中间的所有三个2,所有都作为一个组.(一个循环可用于查找相同值的范围).

 groupSumClump(0, {2, 4, 8}, 10) ? true      
 groupSumClump(0, {1, 2, 4, 8, 1}, 14) ? true                   
 groupSumClump(0, {2, 4, 4, 8}, 14) ? false --> Failing Test Case               
 groupSumClump(0, {8, 2, 2, 1}, 9) ? true   --> Failing Test Case      
 groupSumClump(0, {8, 2, 2, 1}, 11) ? false --> NegativeArraySizeException 

我做了一些初步分析,部分代码如下.

  public boolean groupSumClump(int start, int[] nums, int target) {
    start = 0;
    boolean flag = false;

    // get the highest int from the list of array we have
    int highestInteger = getTheBiggest(nums);
    if (highestInteger > target) {
        flag = false;
    } else {
        int variable = 0;
        for (int i = 0; i < nums.length; i++) {
            variable += nums[i];
        }
        if (variable == target) {
            flag = true;
        } else {
            if (variable < target) {
                flag = false;
            } else {
                // here goes ur grouping logic here
                flag = summate(highestInteger, target, nums);
            }
        }
    }

    return flag;
}

private  boolean summate(int highestInteger, int target, int[] nums) {
    boolean val = false;
    if (highestInteger == target) {
        val = true;
    } else {
        int[] temp = new int[nums.length - 1];
        int var = 0;            

        if ((target - highestInteger) > 0) {
                 for (int j = 0; j < nums.length-1; j++) {
                   if (nums[j] != highestInteger) {
                     temp[var] = nums[j];
                     if (temp[var] == (target - highestInteger)) {
                        val = true;
                        return val;
                     }
                     var++;
                   }
                 }
             val = summate(getTheBiggest(temp), target - highestInteger,
                     temp);  

         }                                      
     }      
    return val;
}

private int getTheBiggest(int[] nums) {
    int biggestInteger = 0;
    for (int i = 0; i < nums.length; i++) {
        if (biggestInteger < nums[i]) {
            biggestInteger = nums[i];
        }
    }
    return biggestInteger;
}

请注意:我不知道如何处理下面的问题陈述的逻辑:有一个Additional Constraint问题,如果数组中有相邻的数字和相同的值,它们必须全部被选中,或者都不是选择.例如,对于数组{1,2,2,2,5,2},必须选择或不选择中间的所有三个2,所有都作为一个组.(一个循环可用于查找相同值的范围).

我应该如何在上述问题中处理这部分逻辑.我一直在努力做到这一点,不知道.提供的建议将不胜感激.Culd你让我知道代码有什么问题/如何处理这个问题中的附加约束, - :((

附加约束表示你选择作为一个组而不选择作为一个组.所以我不知道如何继续.如果你能帮助我.我将不胜感激.

编辑用户 - > MISSINGNO:我已将下面的代码构造添加到上面的主代码中,它打印出错误的值.我错了.

groupSumClump(0,{2,4,4,8},14)→false再次失败2 8 4标志是 - > true这是错误的.

      for(int number=0;number<nums.length-1;number++){
      if(nums[number]==nums[number+1]){
          nums[number]=nums[number]+nums[number+1];                                
      }        
    }

Answer 1

我会将数组转换为一个更简单的数组,可以使用前面的方法解决,通过聚集相邻的值:

{1, 2, 2, 2, 5, 2} --> {1, 6, 5, 2}

您可能希望保留一些额外的簿记信息,以便能够从解决方案中找到原始解决方案.