这里是leetcode问题,用于组合和问题。
有一个答案是java(或见下文)
public class Solution {
public List<List<Integer>> combinationSum(int[] cands, int t) {
Arrays.sort(cands); // sort candidates to try them in asc order
List<List<List<Integer>>> dp = new ArrayList<>();
for (int i = 1; i <= t; i++) { // run through all targets from 1 to t
List<List<Integer>> newList = new ArrayList(); // combs for curr i
// run through all candidates <= i
for (int j = 0; j < cands.length && cands[j] <= i; j++) {
// special case when curr target is equal to curr candidate
if (i == cands[j]) newList.add(Arrays.asList(cands[j]));
// if current candidate is less than the target use prev results
else for (List<Integer> l : dp.get(i-cands[j]-1)) {
if (cands[j] <= l.get(0)) {
List cl = new ArrayList<>();
cl.add(cands[j]); cl.addAll(l);
newList.add(cl);
}
}
}
dp.add(newList);
}
return dp.get(t-1);
}
}
我需要用javascript转换它。
这是我的尝试。
function sortFunc(a, b) {
return a-b;
}
function combinationSum(cands, t) {
cands.sort(sortFunc);
let dp = []; //[[[]]];
for (let i = 1; i <= t; i++) {
console.log('-- i --');
console.log(i);
let newList = []; // [[]];
for (let j = 0; j < cands.length && cands[j] <= i; j++)
{
console.log('-- j --');
console.log(j);
if (i === cands[j]) {
console.log('-- push --');
console.log(i);
newList.push([cands[j]]);
}
else {
// list of int
let myListList = dp[i-cands[j]-1];
for(let k=0; k<myListList.length; k++) {
let myList = myListList;
if(cands[j] <= myList[0]) {
myListList.unshift([cands[j]]);
newList.push(myListList);
}
}
}
}
dp.push(newList);
}
return dp[t-1];
}
let arr = [2, 3, 5];
let t = 15;
let out = combinationSum(arr, t);
console.log(out);
我对代码有些了解,但不是很多目前,我的javascript处于无限循环中。
有人知道为什么吗?
或者你对“组合和”有更好的解决方案?
最佳答案
在最后一个for循环中,您偏离了轨道,并根据循环的长度不断添加到循环中的myNewList
,这样循环就不会结束。
这是一个非常接近原版的版本:
function sortFunc(a, b) {
return a - b;
}
function combinationSum(cands, t) {
cands.sort(sortFunc);
let dp = []; //[[[]]];
for (let i = 1; i <= t; i++) {
let newList = []; // [[]];
for (let j = 0; j < cands.length && cands[j] <= i; j++) {
if (i === cands[j]) {
newList.push([cands[j]]);
} else {
for (l of dp[i - cands[j] - 1]) { // for of is similar to `for (List<Integer> l : dp.get(i-cands[j]-1))`
if (cands[j] <= l[0]) {
let cl = [cands[j], ...l] // use spread ...l to get ArrayList.addall() behavior
newList.push(cl)
}
}
}
}
dp.push(newList);
}
return dp[t - 1];
}
let arr = [2, 3, 5, 4];
let t = 7;
let out = combinationSum(arr, t);
console.log(out);