給定一個整數數組,是否可以選擇一組整數,這樣該組就可以與給定的目標相加,並帶有這個額外的約束條件:如果數組中有相鄰的數字和相同的價值,他們必須全部被選中,或者他們沒有選擇。例如,對於數組{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