Java算法问题

Question

问题陈述::在Java中，给定一个int数组，是否可以选择一组int值，从而使得该组与给定的目标相加，并附加这个约束：如果存在数组中相邻且相同值的数字，它们必须全选或全选。例如，对于数组{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必须被选择或不被选择，全部作为一个组。 （一个循环可用于查找相同值的范围）。

我应该如何处理上述问题中的这部分逻辑。 我一直在努力争取这个权利，不知道。 提供的建议将不胜感激。 你让我知道什么是代码问题/如何处理这个问题的附加约束： - （（

其他约束说，你选择作为一个组，而不是选择作为一个group.so我不知道如何proceed.if u能请帮me.it可以理解

编辑USER-> MISSINGNO：我已经添加了下面的代码结构，以上述主要代码，并打印我的错values.where我错了

groupSumClump（0，{2,4,4,8}，14）→false再次失败该标志是 - > 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} 

你可能想保留一些额外的簿记信息虽然是能够从解决方案中找到原来的解决方案。

Answer 2

此问题类似于在数组中总结给定目标的整数组。

提示针对此问题是：

基础案例是当开始> = nums.length。在这种情况下，如果目标== 0，则返回true。否则，请考虑nums [start]处的元素。关键的想法是只有两种可能性 - 选择nums [开始]或不选择。如果选择nums [start]（在该调用中从目标中减去nums [start]），则进行一次递归调用以查看解决方案是否可行。如果没有选择nums [start]，则进行另一次递归调用以查看解决方案是否可行。如果两个递归调用中的任何一个返回true，则返回true。

您可以使用相同的提示，但其中有一个循环来找出数组中重复数字的总和。如果总和被选择，则进行调用以查看解决方案是否可能，如果总和未被选择则进行另一个调用。如果两个递归调用中的任何一个返回true，则返回true。

我认为这会有所帮助。

public boolean groupSumClump(int start, int[] nums, int target) 
{ 
if(start >= nums.length) return target == 0; 

int count = 1; 
while(start+count < nums.length && nums[start] == nums[start+count]) 
count++; 

if(groupSumClump(start+count, nums, target-count*nums[start])) return true; 
if(groupSumClump(start+count, nums, target)) return true; 

return false; 
} 

Answer 3

一旦你这样做missingno的预处理步骤（线性时间），你有什么本质上是subset sum problem。这是一个相当困难的问题，但存在近似算法 - 最终可能取决于序列的长度。

Answer 4

问题陈述是ambigious和不明确：

与此附加约束：如果有阵列 在相邻且相同的值的数字，它们必须要么全部是 选择，或无他们选择了。例如，与阵列{1，2，2， 2，5,2}，或者所有三个2点的中间必须选择与否， 所有作为一组

怎么样如果“条纹”没有解决，选择单个数字？ 同样的例子：{1,2,2,2,5,2}

在一个递归调用，我们选择的2 2 2连胜（从上面的回答） *如果（groupSumClump（启动+计数，NUMS ，target-count * nums [start]））return true *

在下一个rec。 （groupSumClump（start + count，nums，target））返回true;如果（groupSumClump（start + count，nums，target））返回true，则调用为什么我们不能在nums [start]处减去第一个单个数字：

我可以做到这一点：

如果（groupSumClump（开始+ ，NUMS，靶 - NUMS [开始]））返回true;

是否意味着我们不能选择单一数字？

Answer 5

方法groupSumClump的公共方法参数列表不应该公开start参数，特别是如果您有一个覆盖它的内部变量。

看看这个实现。 solve方法的时间复杂度为O(2^N)，因为在最坏的情况下，您必须检查所有可能的nums子集。那么除非有人证明NP = P。

我希望它能帮助。

import java.util.*; 

public class SubsetSumSolver { 

    public boolean solve(int[] nums, int target) { 
     return solve(0, 0, target, mergeSameNumbers(nums)); 
    } 

    private boolean solve(int start, int tempSum, int sum, ArrayList<Integer> nums) { 
     if (start == nums.size()) 
      return sum == tempSum; 
     return solve(start + 1, tempSum + nums.get(start),sum, nums) || solve(start + 1, tempSum, sum, nums); 
    } 

    private ArrayList<Integer> mergeSameNumbers(int[] nums) { 
     if (nums.length == 0) 
      return toArrayList(nums); 
     LinkedList<Integer> merged = new LinkedList<>(); 
     int tempSum = nums[0]; 
     for (int i = 1; i < nums.length; i++) { 
      if (nums[i - 1] == nums[i]) 
       tempSum += nums[i]; 
      else { 
       merged.add(tempSum); 
       tempSum = nums[i]; 
      } 
     } 
     merged.add(tempSum); 
     return new ArrayList(merged); 
    } 

    private ArrayList<Integer> toArrayList(int[] nums) { 
     ArrayList<Integer> result = new ArrayList(); 
     for (int index = 0; index < nums.length; index++) 
      result.add(nums[index]); 
     return result; 
    } 

}