我在 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];
};