Java的算法问题 [英] Java Algorithm Question
问题描述
问题描述::在Java中，给定int数组，是否有可能选择一个组的一些整数，例如，该集团款项给定的目标，这个额外的约束：如果有号码的阵列相邻并相同的值，就必须要么全部被选择，或者其中没有选择。例如，与阵列{1，2，2，2，5,2}，或者所有三个2的中间必须选择与否，各为一组。 （一个环可以被用来找到相同值的程度）。
groupSumClump（0，{2，4，8}，10）→真
groupSumClump（0，{1，2，4，8，1}，14）→真
groupSumClump（0，{2，4，4，8}，14）→假 - ＆GT;失败的测试案例
groupSumClump（0，{8,2，2，1}，9）→真 - ＆GT;失败的测试案例
groupSumClump（0，{8,2，2，1}，11）→假 - ＆GT; NegativeArraySizeException
我已经做了一些初步的分析和部分code是如下。
公共布尔groupSumClump（INT开始，INT [] NUMS，INT目标）{
开始= 0;
布尔标志= FALSE;
//从数组列表中我们得到最高INT
INT highestInteger = getTheBiggest（NUMS）;
如果（highestInteger＆GT;目标）{
标志= FALSE;
} 其他 {
int变量= 0;
的for（int i = 0; I＆LT; nums.length;我++）{
变量+ = NUMS [I]
}
如果（变量==目标）{
标志=真正的;
} 其他 {
如果（变量＆lt;目标）{
标志= FALSE;
} 其他 {
//这里去乌拉圭回合分组逻辑这里
标志= summate（highestInteger，目标，NUMS）;
}
}
}
返回标志;
}
私人布尔summate（INT highestInteger，诠释目标，INT [] NUMS）{
布尔VAL = FALSE;
如果（highestInteger ==目标）{
VAL = TRUE;
} 其他 {
INT []临时=新的INT [nums.length - 1];
INT变种= 0;
如果（（靶 - highestInteger）大于0）{
对于（INT J = 0; J＆LT; nums.length-1，J ++）{
如果（NUMS [J]！= highestInteger）{
临时[VAR] = NUMS [J]。
如果（临时[VAR] ==（目标 - highestInteger））{
VAL = TRUE;
返回VAL;
}
VAR ++;
}
}
VAL = summate（getTheBiggest（临时），目标 - highestInteger，
温度）;
}
}
返回VAL;
}
私人诠释getTheBiggest（INT [] NUMS）{
INT biggestInteger = 0;
的for（int i = 0; I＆LT; nums.length;我++）{
如果（biggestInteger＆LT; NUMS [I]）{
biggestInteger = NUMS [I]
}
}
返回biggestInteger;
}
请注意：我不知道如何处理逻辑如下问题陈述：
有一个附加约束来的问题，即，如果有在阵列中是相邻的和相同的值的数字，它们必须要么全部被选择，或者其中没有选择。例如，与阵列{1，2，2，2，5,2}，或者所有三个2的中间必须选择与否，各为一组。 （一个环可以被用来找到相同值的程度）。
我应该如何处理这部分逻辑在上述问题。 我一直在努力得到这个权利，没有想法。 提供建议，将AP preciated。 Culd你让我知道什么是与code中的问题/如何处理额外的限制在这个问题上，： - （（
附加约束或者说U选择作为一个群体，而不是选择一个group.so我不知道如何proceed.if u能请帮me.it将AP preciated。
编辑USER-> MISSINGNO：我已经添加了以下code构建以上述主要code和它打印我的错values.where我已经错了。
groupSumClump（0，{2，4，4，8}，14）→假是再次失败 2 8 4 该标志是 - >真正的这是不对的。
的（INT数= 0;数＆LT; nums.length-1;数++）{
如果（NUMS [数字] == NUMS [数字+ 1]）{
NUMS [数字] = NUMS [数字] + NUMS [数字+ 1];
}
}
我会转换数组一个简单的阵列，可以与你的previous的方法来解决，由丛生的相邻值：
{1，2，2，2，5，2} - ＆GT; {1，6,5，2}
您可能希望保留一些额外的簿记信息虽然是能够找到的一个解决问题，改变原来的解决方案。
Problem Statement :: In Java ,Given an array of ints, is it possible to choose a group of some of the ints, such that the group sums to the given target, with this additional constraint: if there are numbers in the array that are adjacent and the identical value, they must either all be chosen, or none of them chosen. For example, with the array {1, 2, 2, 2, 5, 2}, either all three 2's in the middle must be chosen or not, all as a group. (one loop can be used to find the extent of the identical values).
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
I have done some initial Analysis and the partial code is as below.
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;
}
Please Note: I dont know how to handle the logic for below problem statement :
There is an Additional Constraint to the problem such that if there are numbers in the array that are adjacent and the identical value, they must either all be chosen, or none of them chosen. For example, with the array {1, 2, 2, 2, 5, 2}, either all three 2's in the middle must be chosen or not, all as a group. (one loop can be used to find the extent of the identical values).
how should i handle this part of logic in above problem. I have been struggling to get this right with no idea. Suggestions provided will be appreciated. Culd you let me know what is the problem with the code/how to handle the additional constraint in this problem, :-((
Additional constraint says either u select as a group and not select as a group.so i dont know how to proceed.if u can PLEASE help me.it will be appreciated.
EDIT FOR USER->MISSINGNO: I have added the below code construct to above main code and it prints me wrong values.where have i gone wrong.
groupSumClump(0, {2, 4, 4, 8}, 14) → false is failing again 2 8 4 The flag is -->true which is wrong.
for(int number=0;number<nums.length-1;number++){
if(nums[number]==nums[number+1]){
nums[number]=nums[number]+nums[number+1];
}
}
I would convert the array to a simpler array that can be solved with your previous method, by clumping the adjacent values:
{1, 2, 2, 2, 5, 2} --> {1, 6, 5, 2}
You might want to keep some extra bookkeeping info though to be able to find the original solution from a solution to the altered problem.
这篇关于Java的算法问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
