Java算法问题
发布时间:2020-12-15 08:40:26 所属栏目:Java 来源:网络整理
导读:问题陈述::在 Java中,给定一个整数数组,是否可以选择一组整数的组,使得该组与给定目标相加,并具有以下附加约束:如果数组中有数字,则相邻且相同的值,它们必须全部被选中,或者都不被选择.例如,对于数组{1,2,5,2},必须选择或不选择中间的所有三个2,所有都作为
问题陈述::在
Java中,给定一个整数数组,是否可以选择一组整数的组,使得该组与给定目标相加,并具有以下附加约束:如果数组中有数字,则相邻且相同的值,它们必须全部被选中,或者都不被选择.例如,对于数组{1,2,5,2},必须选择或不选择中间的所有三个2,所有都作为一个组. (一个循环可用于查找相同值的范围).
groupSumClump(0,{2,4,8},10) → true groupSumClump(0,{1,8,1},14) → true groupSumClump(0,14) → false --> Failing Test Case groupSumClump(0,{8,9) → true --> Failing Test Case groupSumClump(0,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; } 请注意:我不知道如何处理以下问题陈述的逻辑: 我应该如何在上述问题中处理这部分逻辑. 附加约束表示你选择作为一个组而不选择作为一个组.所以我不知道如何继续.如果你能帮助我.我将不胜感激. 编辑用户 – > MISSINGNO:我已将下面的代码构造添加到上面的主代码中,它打印出错误的值.我错了. groupSumClump(0,14)→false再次失败 for(int number=0;number<nums.length-1;number++){ if(nums[number]==nums[number+1]){ nums[number]=nums[number]+nums[number+1]; } } 解决方法
我会将数组转换为一个更简单的数组,可以使用前面的方法解决,通过聚集相邻的值:
{1,2} --> {1,6,2} 您可能希望保留一些额外的簿记信息,以便能够从解决方案中找到原始解决方案. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |