关于leetcode的combinationSum题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

关于leetcode的combinationSum题

关于leetcode的combinationSum题# JobHunting - 待字闺中

s*12012-11-06 08:11

1 楼

用java做了leetcode的combinationSum，其实就是DP，
我造了一个ArrayList> 的二维数组，假设数组名为 comb,
我从comb[0][0] 一直到 comb[input数组长度][target]开始DP，
我想算法没问题，但可能太耗空间了，一直是runtime error
我想请问版上是否有高人，给个这题的java版本，能够通过online的大小数据测试？谢
谢啦
c++版本我已经搜过了

s*12012-11-06 08:11

2 楼

Zai Ding yi xia!

g*y2012-11-06 08:11

3 楼

为啥不在自己的机器上调试一下？

w*o2012-11-06 08:11

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*12012-11-06 08:11

5 楼

hi,
谢谢大牛！
坦白说，没看懂什么逻辑，不过我再细细品尝~
谢谢啦~

j*e2012-11-06 08:11

6 楼

哪一题？

l*o2012-11-06 08:11

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 ArrayListInteger>>();
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);
}
}