この組み合わせ合計アルゴリズムをjavaからjavascriptに変換する方法

debugcn 投稿 Dev

kenpeter

これが、組み合わせ和問題のリートコードの質問です。

1つの回答コードはここ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);

この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。

侵害の場合は、連絡してください[email protected]