Redian新闻
>
关于leetcode的combinationSum题
avatar
关于leetcode的combinationSum题# JobHunting - 待字闺中
s*1
1
用java做了leetcode的combinationSum,其实就是DP,
我造了一个ArrayList> 的二维数组,假设数组名为 comb,
我从comb[0][0] 一直到 comb[input数组长度][target]开始DP,
我想算法没问题,但可能太耗空间了,一直是runtime error
我想请问版上是否有高人,给个这题的java版本,能够通过online的大小数据测试?谢
谢啦
c++版本我已经搜过了
avatar
s*1
2
Zai Ding yi xia!
avatar
g*y
3
为啥不在自己的机器上调试一下?
avatar
w*o
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);
}
}
}
avatar
s*1
5
hi,
谢谢大牛!
坦白说,没看懂什么逻辑,不过我再细细品尝~
谢谢啦~
avatar
j*e
6
哪一题?
avatar
l*o
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);
}
}
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。