为什么我在leetcode上收到AddressSanitizer:地址0x602000000058上的堆缓冲区溢出错误

Question

我读过其他一些答案，并查看了一篇关于代码部队的博客。所有这些都表明，这一定是某种潜在的溢出。我已经为从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;
}
};

---

参考文献

• 有关更多详细信息，请参阅讨论板。有很多公认的解决方案，包括各种语言和解释，有效的算法，以及渐近时间/空间复杂性分析^1，2

如果您正在准备面试：

• 我们希望根据标准和约定编写无错误和干净的代码(例如，c^1，2，c++<sup]1，2>^{，java1，2，c#1,2、python1、javascript1、go1[/sup>、rust1<1(}