这是一个创建于 3851 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目地址： 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 年 8 月 10 日
问题已解决，自身代码存在问题，没有考虑到梯形数组。
在此特别感谢@theFool
在此特别感谢@theFool
 | 1 chchwy 2015 年 8 月 9 日 Runtime Error 就是跑到一半 crash 了. 通常是非法指或越界了. 查一下你的存使用吧. |
 | 2 theFool 2015 年 8 月 9 日 数组越界了。 而且算法本身也有问题。 |
 | 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 年 8 月 9 日 RTE跟效率没有关系，是你程序跑挂了 |
| 5 theFool 2015 年 8 月 9 日 @Ryse current = *((int *)triangle + row * numRows + col); 参数是二维指针，并不一定和你想象的二维数组一样。 比如triangle分配的时候是用梯形数组而不是矩形数组，那就越界了。 改为current = *(*(triangle+row)+col);或者current = triangle[row][col]; 算法没问题，扫一眼没认出缩减了，不好意思啦。 |
 | 7 CHEATBEATER 2015 年 8 月 10 日 RE和访问效率无关… 效率低的话是TLE (time limit exceed) 目测 数组越界了，可以尝试把数组开的大一点 |
 | 8 proudzhu 2015 年 8 月 10 日 via Android Triangle 没说是二维数组啥，你这么访问就可能越界了 |
 | 9 catro 2015 年 8 月 10 日 @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