s*****1
发帖数: 134 | 1 用java做了leetcode的combinationSum，其实就是DP，
我造了一个ArrayList> 的二维数组，假设数组名为 comb,
我从comb[0][0] 一直到 comb[input数组长度][target]开始DP，
我想算法没问题，但可能太耗空间了，一直是runtime error
我想请问版上是否有高人，给个这题的java版本，能够通过online的大小数据测试？谢
谢啦
c++版本我已经搜过了 | s*****1
发帖数: 134 | | g****y
发帖数: 240 | | w***o
发帖数: 109 | 4 这个能过OJ。
public class Solution {
public ArrayList> combinationSum(int[] candidates,
int target) {
// Start typing your Java solution below
// DO NOT write main() function
if(candidates == null || candidates.length == 0)
return new ArrayList>();
Arrays.sort(candidates);
ArrayList> ret = new ArrayList
>();
getCombination(candidates, 0, 0, target, new ArrayList(),
ret);
return ret;
}
private void getCombination(int[] A, int index, int sum, int target,
ArrayList list, ArrayList> ret) {
if(sum == target)
{
ret.add((ArrayList) list.clone());
return;
}
if(sum > target)
return;
for(int i = index; i < A.length; i++) {
int a = A[i];
list.add(a);
getCombination(A, i, sum + a, target, list, ret);
list.remove(list.size() - 1);
}
}
} | s*****1
发帖数: 134 | 5 hi,
谢谢大牛！
坦白说，没看懂什么逻辑，不过我再细细品尝~
谢谢啦~ | j*******e
发帖数: 1058 | | l****o
发帖数: 315 | 7 可过
public class Solution {
public ArrayList> combinationSum(int[] candidates,
int target) {
// Start typing your Java solution below
// DO NOT write main() function
Arrays.sort(candidates);
ArrayList>> f = new ArrayList
>>();
for (int i = 0; i <= target; i++) {
ArrayList> tmp = new ArrayList
Integer>>();
f.add(tmp);
}
ArrayList> keys = new ArrayList
>>();
for (int i = 0; i < candidates.length; i++) {
for (int j = 1; j <= target; j++) {
if (j - candidates[i] >= 0) {
keys = (ArrayList>) f.get(
j - candidates[i]).clone();
ArrayList> tmpkeys = (ArrayList<
ArrayList>) f
.get(j).clone();
if (keys.isEmpty() && candidates[i] == j) {
ArrayList tmp = new ArrayList();
tmp.add(candidates[i]);
tmpkeys.add(tmp);
} else if (!keys.isEmpty())
for (ArrayList e : keys) {
ArrayList tmp = (ArrayList) e
.clone();
tmp.add(candidates[i]);
tmpkeys.add(tmp);
}
f.set(j, tmpkeys);
}
}
}
return f.get(target);
}
} |
|
