LeetCode # 70 Восхождение по лестнице, как ускорить мое решение? - PullRequest
Новая
       72

LeetCode # 70 Восхождение по лестнице, как ускорить мое решение?

0 голосов
/ 05 мая 2020

У меня есть решение этой проблемы на LeetCode # 70 Подъем по лестнице. Мое решение не проходит из-за медленной работы ...

Я добавил батут, использующий thunks, и я добавил Memoization , что еще я могу добавить, чтобы ускорить этот процесс, чтобы на самом деле сократить время, необходимое для решения этой проблемы, мой код приведен ниже, и заранее спасибо.

Описание на 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];
};

Ответы [ 2 ]

1 голос
/ 13 июня 2020

Хорошо, поэтому вы хотите, чтобы решение было более оптимизировано.

Решение, которое в настоящее время обсуждается вами, имеет линейное время выполнения, то есть O (N), и принимается в LeetCode. А пока не будем говорить о пространственной сложности.

Эта проблема и категория этих проблем могут быть решены методом матричного возведения в степень, который имеет логарифмическое c время выполнения, т.е. O (Log N)

Возведение в степень матрицы очень хорошо описано по этой ссылке

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

1 голос
/ 05 мая 2020

Я не совсем следую подходу, который вы здесь используете. Проблема на самом деле довольно проста: запрограммируйте наивное рекурсивное решение, а затем запомните результаты. То есть, если вы посетили ступеньку в кэше, верните ее, в противном случае вычислите ее. Время выполнения линейно. 

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));
...