Ryse 最近的时间轴更新 Ryse 最近的时间轴更新 |
RyseV2EX 第 77243 号会员，加入于 2014-10-15 16:32:05 +08:00 |
| LeetCode 的 Triangle 题，提交提示 Runtime Error，是二维数组访问效率太低么？ 求指点 程序员 • Ryse • 2015 年 8 月 10 日 • 最后回复来自 Ryse | 10 |
Ryse 最近回复了
2015 年 8 月 10 日 回复了 Ryse 创建的主题 › 程序员 › LeetCode 的 Triangle 题，提交提示 Runtime Error，是二维数组访问效率太低么？ 求指点 |
2015 年 8 月 9 日 回复了 Ryse 创建的主题 › 程序员 › LeetCode 的 Triangle 题，提交提示 Runtime Error，是二维数组访问效率太低么？ 求指点 |
@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存贮状态
还望指点，想了半天还是想不通，多谢
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存贮状态
还望指点，想了半天还是想不通，多谢
Select Language