Почему я получаю ошибку AddressSanitizer: heap-buffer-overflow по адресу 0x602000000058 в leetcode?

Question

Я прочитал несколько других ответов и проверил блог на codeforces. Все предполагают, что это должно быть какое-то возможное переполнение. Я протестировал его для всех тестов от n = 1 до n = 45. Я не вижу этого переполнения.

class Solution {
public:
    int checkSteps(int n, vector<int>&cache){
       if(n <= 0)
         return cache[0];
       else if(n == 1){
           return cache[1];
       }
       else if(n == 2){
           return cache[2];
       }
       if(cache[n] > 0) return cache[n];
       cache[n] = checkSteps(n-1, cache) + checkSteps(n-2, cache);
        return cache[n];
    }

   int climbStairs(int n){
           vector<int> cache(n+1, 0);
           cache[0] = 0;
           cache[1] = 1;
           cache[2] = 2;
          int result = checkSteps(n, cache);
           return result;

   }

Answer 1

Вы также можете использовать формулу числа Фибоначчи ( Золотое сечение ) для этой задачи, будет принято:

struct Solution {
    static const inline int climbStairs(const int n) {
        double ways = 1 / pow(5, 0.5) * (pow((1 + pow(5, 0.5)) / 2, -~n) - pow((1 - pow(5, 0.5)) / 2, -~n));
        return (int) ways;
    }
};

• -~n просто (n + 1 ), немного короче

или, исходя из вашего подхода, мы просто будем повторять:

struct Solution {
    static const inline int climbStairs(const int n) {
        int first = 1;
        int second = 0;
        int ways = 0;

        for (int iter = 0; iter < n; iter++) {
            ways = first + second;
            second = first;
            first = ways;
        }

        return ways;
    }
};

Ссылки

• Дополнительные сведения см. На Доске обсуждения . Есть множество принятых решений с множеством языков и объяснений, эффективных алгоритмов, а также асимптот c время / пространство анализ сложности ^{1 , 2} там.

Если вы готовитесь к собеседованию :

• Мы хотели бы написать коды без ошибок и чистые на основе стандартов и соглашений (например, c ^{1 , 2} , c ++ ^{1 , 2} , java ^{1 , 2} , c# ^{1 , 2} , python ¹ , javascript ¹ , go ¹ , ржавчина ¹ ).