给定一个整数数组,是否可以选择一组整数,这样该组就可以与给定的目标相加,并带有这个额外的约束条件:如果数组中有相邻的数字和相同的价值,他们必须全部被选中,或者他们没有选择。例如,对于数组{1,2,2,2,5,2},中间的所有三个2必须被选择或不被选择,全部作为一个组。 (一个循环可用于查找相同值的范围)。Java分组算法
测试场景均低于
groupSumClump(0, {2, 4, 8}, 10) → true true OK
groupSumClump(0, {1, 2, 4, 8, 1}, 14) → true true OK
groupSumClump(0, {2, 4, 4, 8}, 14) → false false OK
groupSumClump(0, {8, 2, 2, 1}, 9) → true false X --->Failing
groupSumClump(0, {8, 2, 2, 1}, 11) → false false OK
groupSumClump(0, {1}, 1) → true false X --->Failing
groupSumClump(0, {9}, 1) → false false OK
other tests OK
片段是如下
private int sum(final Integer start, final Collection<Integer> list) {
int sum = start;
for (final int i : list) {
sum += i;
}
return sum;
}
public boolean groupSumClump(final int start, final int[] nums, final int target) {
for (int i = 0; i < nums.length-1; i++) {
if(nums[i] == nums[i+1]){//group selected logic
int sum = nums[i] + nums[i+1];//is this Ok ?
nums[i] =sum;
nums[i+1]=0;
}else{
//how to handle the logic for group not selected.
}
}
final List<Integer> fixed = new ArrayList();
final List<Integer> candidates = new ArrayList();
// fills candidates and fixed
for (int i = 0; i < nums.length; i++) {
final int cand = nums[i];
if (cand == 1 && i > 0) {
final int prev = nums[i - 1];
}else if (cand < target) {
candidates.add(cand);
}
}
// compute the sum of fixed
final int sumFixed = sum(0, fixed);
// if the sum of fixed is equals to target we don't need to do
//anything because we already know we need to return true.
if (sumFixed == target) {
return true;
}
if (sumFixed <= target && !candidates.isEmpty()) {
final Set<Set<Integer>> powerSets = powerSet(new HashSet(candidates));
for (final Set<Integer> set : powerSets) {
if (sumFixed + sum(0, set) == target) {
return true;
}
}
}
return false;
}
public <T> Set<Set<T>> powerSet(Set<T> originalSet) {
Set<Set<T>> sets = new HashSet<Set<T>>();
if(originalSet.isEmpty()) {
sets.add(new HashSet<T>());
return sets;
}
List<T> list = new ArrayList<T>(originalSet);
T head = list.get(0);
Set<T> rest = new HashSet<T>(list.subList(1, list.size()));
for (Set<T> set : powerSet(rest)) {
Set<T> newSet = new HashSet<T>();
newSet.add(head);
newSet.addAll(set);
sets.add(newSet);
sets.add(set);
}
return sets;
}
你能告诉我什么提到的代码的问题,为什么会失败的测试场景。
我想知道未选择组的逻辑是什么?
这功课吗?这也让我想起'NP!= P'问题... – Bobby 2011-05-18 09:44:08
另请参见用户的上一个问题http://stackoverflow.com/questions/6028256/groupsumclump-problem – Qwerky 2011-05-18 09:47:37
你能否提供我在java中的代码的实现以解决上述问题。同时我需要处理没有选中的组的逻辑。您可以在java中为这个提供完整的实现 – 2011-05-19 04:32:43