Java算法问题

Question

Java算法问题

3

问题陈述：在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;
}

请注意：我不知道如何处理以下问题陈述的逻辑：问题有一个“附加约束条件”，即如果数组中有相邻且相同值的数字，则必须选择它们全部或不选。例如，对于数组{1，2，2，2，5，2}，必须选择或不选择中间的三个2，作为一组。（可以使用一个循环来查找相同值的范围）。

如何处理上述问题中这部分逻辑。我一直在努力尝试，但无法正确处理。欢迎提供建议。您能告诉我代码有什么问题/如何处理这个问题的附加约束条件吗，:-((

附加约束条件表示要么选择为一组，要么不选择为一组。所以我不知道该如何继续进行。如果您能帮忙，将不胜感激。

编辑用户->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];                                
      }        
    }

- deepakl.2000

7个回答

3

这个问题类似于在数组中找到一组整数，它们的总和等于给定的目标值。

此问题的提示为：

基本情况是当start≥nums.length时。在那种情况下，如果target==0，则返回true。否则考虑nums [start]处的元素。关键思想是只有两种可能性——选择nums [start]或不选择它。进行一个递归调用以查看是否可以选择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;
}

- user1229441

1

你解决这个问题的方式很冗长。尝试更多地递归思考。

对于基本情况，我们将检查起始位置是否大于或等于提供的数组(nums)的长度。如果是真的，我们将检查是否已经达到目标总和，即目标是否等于0。如果是，则返回true作为答案，否则返回false，因为我们已经遍历了整个数组，仍然没有达到我们的目标。

基本情况 -

if(start>=nums.length)
return target==0;`

现在，我们将使用一个计数器变量 int c=1;。我们将使用它来计算重复字符的数量（如果有的话）。我们将使用 while 循环并迭代直到nums[start]到nums[start+c]，并不断增加计数器。当此循环结束时，如果 c 的值为 1，则表示我们没有找到任何重复字符。否则，我们已经找到了 c 个重复的 nums[start] 字符。请确保在此 while 循环中不越界。

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

现在，您知道是否有重复字符。您必须包含所有或不包含任何重复字符。我们已经有了c，所以现在我们只需要调用函数，在其中包含c * nums [start]或不包含c * nums [start]。

现在，如果我们有重复项，则函数将跳过或获取所有相同的值。但是，如果我们没有重复项，仅因为c的值为1，函数调用在这种情况下也会起作用。尝试运行代码以获得更好的理解。

最后，如果所有函数调用都返回false，则我们知道没有答案，因此我们也将返回false。

public boolean groupSumClump(int start, int[] nums, int target) {

if(start>=nums.length)
return target==0;

int c=1;

while(start+c<nums.length&&nums[start]==nums[start+c])
c++;

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

return false;

}

- Aman Sharma

0

问题陈述含糊不清，不够明确：

加上这个额外的限制条件：如果数组中有相邻且相同值的数字，则它们必须全部选择或全部不选。例如，对于数组 {1, 2, 2, 2, 5, 2}，要么选择中间的三个 2，要么不选，作为一组

如果“连续数列”无法奏效，那么选择单个数字怎么样？ 同样的例子：{1,2,2,2,5,2}

在一个递归调用中，我们选择了答案中的 2 2 2 连续数列（从上面的答案中）*如果(groupSumClump(start+count, nums, target-count*nums[start])) return true*

在下一个递归调用中，为什么不能减去 nums[start] 的第一个单个数字：if(groupSumClump(start+count, nums, target)) return true;

我可以这样做吗：

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

这是不是意味着我们永远不能选择单个数字？

- ERJAN

0

一旦完成了missingno的预处理步骤（在线性时间内），你实际上拥有的是子集和问题。这是一个相当困难的问题，但是存在近似算法-根据您的序列长度，可能会变得实用。

- mbatchkarov

0

你的公共方法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;
    }

}

- GA1

-2

我的解决方案是使用HashMap。

public boolean groupSumClump(int start, int[] nums, int target) {
  Map<Integer, Integer> map = new HashMap<Integer, Integer>();

  Arrays.sort(nums);

  for (int i : nums) {
    if (!map.containsKey(i)) {
      map.put(i, 1);
    }

    else {
      map.put(i, map.get(i) + 1);
    }
  }

  return groupSumClumpHelper(start, nums, target, map);
}

private boolean groupSumClumpHelper(int start, int[] nums, int target, Map map) {
  if (start >= nums.length) {
    return target == 0;
  }

  if (!map.get(nums[start]).equals(1)) {
    return groupSumClumpHelper(start + Integer.parseInt(map.get(nums[start]).toString()), nums, target - Integer.parseInt(map.get(nums[start]).toString()) * nums[start], map) ||
           groupSumClumpHelper(start + Integer.parseInt(map.get(nums[start]).toString()), nums, target, map);
  }

  return groupSumClumpHelper(start + 1, nums, target - nums[start], map) || groupSumClumpHelper(start + 1, nums, target, map);
}

- eugli

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hugomg · Accepted Answer

我会将数组转换为更简单的数组，可以通过您之前的方法解决，方法是将相邻的值聚集在一起：

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

您可能希望保留一些额外的记账信息，以便能够从对修改后问题的解决方案找到原始解决方案。