0

我在 LeetCode #70 爬楼梯上有这个问题的解决方案,我的解决方案没有通过,因为它很慢......

我已经添加了一个使用 thunk 的蹦床,并且我已经添加了记忆,我还可以添加什么来加速它以实际通过这个问题的时间要求,我的代码如下,并提前感谢。

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

我不太遵循您在此处使用的方法。这个问题实际上非常简单:编写简单的递归解决方案,然后记住结果。也就是说,如果您访问缓存中的楼梯,则返回它,否则计算它。运行时是线性的。

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 回答
1

好的,所以您希望解决方案更加优化。

您当前正在讨论的解决方案具有线性运行时间,即 O(N),并且在 LeetCode 上被接受。 现在让我们先不讨论空间复杂度。

这个问题和这些问题的一个类别可以通过一种称为矩阵求幂的方法来解决,该方法具有对数运行时间,即 O(Log N)

这个链接很好地描述了矩阵求幂

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

于 2020-06-13T09:03:54.540 回答