LeetCode 的 Triangle 题，提交提示 Runtime Error，是二维数组访问效率太低么？ 求指点

[Ryse]

题目地址： https://leetcode.com/problems/triangle/
修改了几次，但提交一直提示Runtime Error

int minimumTotal(int **triangle, int numRows) {

int row = 0;
int col = 0;
int current = 0;
int *Min = malloc((numRows + 1) * sizeof(int));

for (row = 0; row <= numRows; row++)
{
/* code */
Min[row] = 0;
}

for (row = numRows - 1; row >= 0; row--)
{
/* code */
for (col = 0; col <= row; col++)
{
/* code */
current = *((int *)triangle + row * numRows + col);

Min[col] = ((Min[col] > Min[col + 1]) ? Min[col + 1] : Min[col]) + current;
}
}

return Min[0];
}

问题已解决，自身代码存在问题，没有考虑到梯形数组。
在此特别感谢@theFool

[chchwy]

Runtime Error 就是跑到一半 crash 了. 通常是非法指針或數組越界了. 檢查一下你的內存使用吧.

[theFool]

数组越界了。

而且算法本身也有问题。

[Ryse]

@chchwy @theFool
1. 二维数组triangle[numRows][numRows], 两层for循环，0 <= row < numRows && 0 <= col <= row numRows，不会出现访问triangle数组越界
2. Min数组申请的长度为numRows+1，可访问数组下标访问为 [0, numRows], 其中col <= row, 而row最大值为numRows-1，访问Min数组也没越界
3. 算法思想是 bottom-to-up,
triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]) ，可缩减使用一个一维数组Min存贮状态

还望指点，想了半天还是想不通，多谢

[zonyitoo]

RTE跟效率没有关系，是你程序跑挂了

[theFool]

@Ryse
current = *((int *)triangle + row * numRows + col);
参数是二维指针，并不一定和你想象的二维数组一样。
比如triangle分配的时候是用梯形数组而不是矩形数组，那就越界了。
改为current = *(*(triangle+row)+col);或者current = triangle[row][col];


算法没问题，扫一眼没认出缩减了，不好意思啦。

[fszaer]

@theFool +1
按题目来讲
triangle
应该是
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
row并不是定长数组
so......

[CHEATBEATER]

RE和访问效率无关…
效率低的话是TLE (time limit exceed)
目测 数组越界了，可以尝试把数组开的大一点

[proudzhu]

Triangle 没说是二维数组啥，你这么访问就可能越界了

[catro]

@theFool +2
可以用这段测试代码
int main(int argc, const char *argv[])
{
int triangle_0[] = {2};
int triangle_1[] = {3, 4};
int triangle_2[] = {6, 5, 7};
int triangle_3[] = {4, 1, 8, 3};
int *triangle[] = {triangle_0, triangle_1, triangle_2, triangle_3};
printf("Minimum is: %d\n", minimumTotal((int **)triangle, 4));
return 0;
}

[Ryse]

@theFool @catro @proudzhu @fszaer
多谢各位，恩，确实是没考虑到梯形数组，想当然的以为是二维数组，修改后可以通过