V2EX › Ryse 的所有回复 › 第 1 页 / 共 1 页

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

2015-08-10 23:17:45 +08:00

回复了 Ryse 创建的主题 › 程序员 › LeetCode 的 Triangle 题，提交提示 Runtime Error，是二维数组访问效率太低么？求指点

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

2015-08-09 21:05:24 +08:00

回复了 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存贮状态

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