LeetCode 的 Triangle 题，提交提示 Runtime Error，是二维数组访问效率太低么？ 求指点
Ryse · 2015-08-09 19:11:03 +08:00 · 3626 次点击这是一个创建于 3384 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目地址： 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];
}
修改了几次，但提交一直提示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];
}
第 1 条附言 · 2015-08-10 23:19:21 +08:00
问题已解决，自身代码存在问题，没有考虑到梯形数组。
在此特别感谢@theFool
在此特别感谢@theFool
 |
1
chchwy 2015-08-09 19:19:55 +08:00
Runtime Error 就是跑到一半 crash 了. 通常是非法指針或數組越界了. 檢查一下你的內存使用吧.
|
 |
2
theFool 2015-08-09 20:10:09 +08:00
数组越界了。
而且算法本身也有问题。 |
 |
3
Ryse OP @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存贮状态 还望指点，想了半天还是想不通，多谢 |
 |
4
zonyitoo 2015-08-09 22:04:37 +08:00
RTE跟效率没有关系，是你程序跑挂了
|
|
5
theFool 2015-08-09 22:34:44 +08:00
@Ryse
current = *((int *)triangle + row * numRows + col); 参数是二维指针，并不一定和你想象的二维数组一样。 比如triangle分配的时候是用梯形数组而不是矩形数组，那就越界了。 改为current = *(*(triangle+row)+col);或者current = triangle[row][col]; 算法没问题，扫一眼没认出缩减了，不好意思啦。 |
 |
6
fszaer 2015-08-10 01:07:47 +08:00
|
 |
7
CHEATBEATER 2015-08-10 02:01:04 +08:00
RE和访问效率无关…
效率低的话是TLE (time limit exceed) 目测 数组越界了，可以尝试把数组开的大一点 |
 |
8
proudzhu 2015-08-10 08:36:10 +08:00 via Android
Triangle 没说是二维数组啥，你这么访问就可能越界了
|
 |
9
catro 2015-08-10 12:32:19 +08:00
@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; } |
Select Language