0

私は LeetCode #70 でこの問題の解決策を持っています。

サンクを利用するトランポリンを追加し、メモ化を追加しました。これをスピードアップして、コードが以下にあるこの問題の時間要件を実際に渡すために追加できるものは他にありません。事前に感謝します。

LeetCode の説明:

あなたは階段を上っています。頂点に到達するには n 歩かかります。

毎回、1 段または 2 段登ることができます。いくつの異なる方法で頂上に登ることができますか?

注: 与えられた n は正の整数になります。

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps


Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

LeetCode の問題へのリンク: https://leetcode.com/problems/climbing-stairs/


let cache = {};

const sumStairSteps = arr => arr.reduce((acc, cur) => acc + cur, 0);

const thunk = (fn, ...args) => {
    return () => fn(...args);
}

const climbStairsHelper2 = fn => {

    let thunk = fn();

    while (typeof thunk === "function") {
        thunk = thunk();
    }

    return thunk;
};

const climbStairs2 = (newStairSequence, ladderCount) => {
    const sum = sumStairSteps(newStairSequence);

    if (sum === ladderCount) {  cache[ladderCount] = cache[ladderCount] + 1; }


    if (1 + sum <= ladderCount) {
        climbStairsHelper2(thunk(climbStairs2, [ ...newStairSequence, 1 ], ladderCount));
    }

    if (2 + sum <= ladderCount) {
         climbStairsHelper2(thunk(climbStairs2, [ ...newStairSequence, 2 ], ladderCount));
    }
};

const climbStairs = n => {
        if (n in cache) return cache[n];
        cache[n] = 0;
        climbStairs2([], n);
        console.log(cache[n]);
        return cache[n];
};
4

2 に答える 2

1

では、ソリューションをより最適化する必要があります。

あなたが現在議論しているソリューションは、線形ランタイム、つまり O(N) を持ち、LeetCode で受け入れられています。 ここでは、スペースの複雑さについては触れません。

この問題とこれらの問題のカテゴリは、対数実行時間、つまり O(Log N) を持つ Matrix Exponentiation と呼ばれる方法で解決できます。

行列指数は、このリンクで非常によく説明されています

https://discuss.codechef.com/t/building-up-the-recurrence-matrix-to-compute-recurrences-in-o-logn-time/570

于 2020-06-13T09:03:54.540 に答える
1

ここで使用しているアプローチには完全に従っていません。問題は実際には非常に簡単です。単純な再帰的なソリューションをコーディングし、結果をメモします。つまり、キャッシュ内の階段にアクセスした場合はそれを返し、それ以外の場合は計算します。ランタイムは線形です。

const climbStairs = (goal, curr=0, memo={}) => {
  if (goal < curr) {
    return 0;
  }
  else if (goal === curr) {
    return 1;
  }
  else if (curr in memo) {
    return memo[curr];
  }
  
  return memo[curr] = climbStairs(goal, curr + 1, memo) +
                      climbStairs(goal, curr + 2, memo);
};

console.log(climbStairs(50));

于 2020-05-05T06:43:15.363 に答える