p****o
发帖数: 46 | 1 41 / 43 test cases passed.
Status: Wrong Answer
Input: [[-9],[-8,0],[-3,2,5],[6,3,0,-4],[-2,-9,-5,-8,6],[0,-5,0,-2,-1,5]
,[0,6,-1,-5,-8,6,-5],[-8,-5,-9,-8,-4,-3,-5,7]]
Output: -1217805963
Expected: -41
code:
class Solution {
public:
int minimumTotal(vector > &triangle) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int n = triangle.size();
vector vmin(n, 0);
while (n--){
for (int i=0; i<=n; i++){
vmin[i]=triangle[n][i]+min(vmin[i], vmin[i+1]);}
}
return vmin[0];
}
};
但我自己算出来的是-41.
int main(){
// [[-9],[-8,0],[-3,2,5],[6,3,0,-4],[-2,-9,-5,-8,6],[0,-5,0,-2,-1,5],[0,
6,-1,-5,-8,6,-5],[-8,-5,-9,-8,-4,-3,-5,7]]
int x1[1] = { -9 };
int x2[2] = { -8,0 };
int x3[3] = { -3,2,5 };
int x4[4] = { 6,3,0,-4 };
int x5[5] = { -2,-9,-5,-8,6 };
int x6[6] = { 0,-5,0,-2,-1,5 };
int x7[7] = { 0,6,-1,-5,-8,6,-5 };
int x8[8] = { -8,-5,-9,-8,-4,-3,-5,7};
VI v1(x1, x1 + sizeof x1 / sizeof x1[0]);
VI v2(x2, x2 + sizeof x2 / sizeof x2[0]);
VI v3(x3, x3 + sizeof x3 / sizeof x3[0]);
VI v4(x4, x4 + sizeof x4 / sizeof x4[0]);
VI v5(x5, x5 + sizeof x5 / sizeof x5[0]);
VI v6(x6, x6 + sizeof x6 / sizeof x6[0]);
VI v7(x7, x7 + sizeof x7 / sizeof x7[0]);
VI v8(x8, x8 + sizeof x8 / sizeof x8[0]);
VVI vvi;
vvi.push_back(v1);
vvi.push_back(v2);
vvi.push_back(v3);
vvi.push_back(v4);
vvi.push_back(v5);
vvi.push_back(v6);
vvi.push_back(v7);
vvi.push_back(v8);
Solution s;
int i = s.minimumTotal(vvi);
// print out -41 as expected
printf("min total is %dn", i);
} | h****g
发帖数: 105 | | p****o
发帖数: 46 | 3 恩， 的确是越界了。 我如果把下面的改成
vector vmin(n+1, 0);
就全通过了。
但是好奇怪，越界的话， 为什么我本地机器跑没问题？
而且在leetcode上小的测试集全过了，大的测试集过了41个(out of 43).
如果越界的话，应该segmentation fault，一个都过不了啊。
请牛人指点。
【在 h****g 的大作中提到】
: i<=n
: vmin[n+1] 越界了吧？
| b**m
发帖数: 1466 | 4 Undefined behavior,不一定是segmentation fault吧。
【在 p****o 的大作中提到】
: 恩， 的确是越界了。 我如果把下面的改成
: vector vmin(n+1, 0);
: 就全通过了。
: 但是好奇怪，越界的话， 为什么我本地机器跑没问题？
: 而且在leetcode上小的测试集全过了，大的测试集过了41个(out of 43).
: 如果越界的话，应该segmentation fault，一个都过不了啊。
: 请牛人指点。
| h****g
发帖数: 105 | 5 C++并不检查数组越界，程序员可以访问数组之外的内存, 如果这个内存是合法的，编
译运行都不会报错，这属于undefined behavior，这种错误很难发现。有的时候这个数
组之外的内存是受保护的或者是非法的，那就会引起segmentation fault。 因此C++数
组越界 在不同的机器上可能会有不同的结果。
【在 p****o 的大作中提到】
: 恩， 的确是越界了。 我如果把下面的改成
: vector vmin(n+1, 0);
: 就全通过了。
: 但是好奇怪，越界的话， 为什么我本地机器跑没问题？
: 而且在leetcode上小的测试集全过了，大的测试集过了41个(out of 43).
: 如果越界的话，应该segmentation fault，一个都过不了啊。
: 请牛人指点。
|
|
