c++ - 为什么我在 leetcode 上收到 AddressSanitizer: heap-buffer-overflow on address 0x602000000058 错误？

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;

   }

标签： c++buffer-overflow

Answer 1

您也可以使用 Fib 数公式（黄金比例）来解决这个问题，将被接受：

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;
    }
};

---

参考

• 有关其他详细信息，您可以查看讨论板。有很多公认的解决方案，其中包含多种语言和解释、高效算法以及渐近时间/空间复杂度分析^1、2。

如果你正在准备面试：

• 我们希望根据标准和约定（例如c ^{1 , 2} , c++ ^{1 , 2} , java ^{1 , 2} , c# ^{1 , 2} , python ¹ , javascript ¹ , go ¹ , rust ¹ ）编写无错误和干净的代码）。