javascript - JS;简单数组中的最大路径和练习;结果无效
问题描述
我正在做欧拉“最大路径和”练习。
By starting at the top of the triangle below and moving to adjacent numbers on the row below,
the maximum total from top to bottom is 23.
3
7 4
2 4 6
8 5 9 3
That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom of the triangle.
我创建了一个简单的方法来计算行中每个位置的最大可能值。如果我们以前面的例子为例,它变成:
3
10 7
12 14 13
22 19 23 16
The maximum value in the last row is 23.
这是代码:
function maximumPathSumI(triangle) {
let columnSum = [];
for (let row=0; row<triangle.length; row++) {
let newColumnSum = [];
for (let column=0; column<triangle[row].length; column++) {
let maxPreviousValue = getMaxPreviousValueForPosition(column, columnSum);
newColumnSum[column] = maxPreviousValue + triangle[row][column];
}
columnSum = newColumnSum;
}
return Math.max(...columnSum);
}
function getMaxPreviousValueForPosition(position, previousValues) {
let maxValue = previousValues[position] || 0;
if (position > 0 && maxValue < previousValues[position-1]) maxValue = previousValues[position-1];
if (position < previousValues.length && maxValue < previousValues[position+1]) maxValue = previousValues[position+1];
return maxValue;
}
它适用于第一个测试,但似乎没有给出这个三角的正确结果
const testTriangle = [
[75,],
[95, 64,],
[17, 47, 82,],
[18, 35, 87, 10,],
[20, 04, 82, 47, 65],
[19, 01, 23, 75, 03, 34,],
[88, 02, 77, 73, 07, 63, 67,],
[99, 65, 04, 28, 06, 16, 70, 92,],
[41, 41, 26, 56, 83, 40, 80, 70, 33,],
[41, 48, 72, 33, 47, 32, 37, 16, 94, 29,],
[53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14,],
[70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57,],
[91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48,],
[63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31,],
[04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23,],
];
它返回1116
而不是1074
. 当我逐行查看结果时,对我来说一切都很好。
这是中间计算:
[ 75 ]
//[95, 64,],
[ 170, 139 ]
//[17, 47, 82,],
[ 187, 217, 221 ]
//[18, 35, 87, 10,],
[ 235, 256, 308, 231 ]
//[20, 04, 82, 47, 65],
[ 276, 312, 390, 355, 296 ]
//[19, 01, 23, 75, 03, 34,],
[ 331, 391, 413, 465, 358, 330 ]
//[88, 02, 77, 73, 07, 63, 67,],
[ 479, 415, 542, 538, 472, 421, 397 ]
//[99, 65, 04, 28, 06, 16, 70, 92,],
[ 578, 607, 546, 570, 544, 488, 491, 489 ]
//[41, 41, 26, 56, 83, 40, 80, 70, 33,],
[ 648, 648, 633, 626, 653, 584, 571, 561, 522 ]
//[41, 48, 72, 33, 47, 32, 37, 16, 94, 29,],
[ 689, 696, 720, 686, 700, 685, 621, 587, 655, 551 ]
//[53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14,],
[ 749, 791, 764, 785, 725, 743, 776, 707, 752, 706, 565 ]
//[70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57,],
[ 861, 802, 824, 813, 862, 849, 793, 854, 791, 820, 723, 622 ]
//[91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48,],
[ 952, 932, 876, 900, 879, 876, 945, 897, 912, 870, 847, 752, 670 ]
//[63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31,],
[ 1015, 1018, 936, 968, 989, 998, 1012, 975, 985, 928, 939, 934, 792, 701 ]
//[04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23,],
[ 1022, 1080, 1116, 1016, 1021, 1021, 1082, 1110, 1058, 1078, 977, 992, 994, 796, 724 ]
解决方案
你误解了挑战。您的代码中的错误在这一行:
maxValue = previousValues[position+1]
您的代码允许查看前一行的三个不同的总和,但它应该只查看两个(最多):一个 at position-1
(如果有效)和一个 at position
,但不是一个 at position+1
。
推荐阅读
- omnet++ - 如何在 Veins 中执行单播通信?
- ios - 世博会推送通知不起作用(iOS)?
- python - 我可以使用 MechanicalSoup 来检查未命名的复选框吗?
- d3.js - 为什么没有 parseInt 的 d3.extent 返回 Bob Ross 数据集上 num_colors 列的最大值“9”?
- xml - 将多个 tXMLMap 输出值组合到单个雪花表
- sql - UTC 和本地时间之间的时区转换 + 可能是夏令时
- c++ - Qt:显示弹出菜单,如果我点击它之外的任何地方就关闭
- java - Java 如何播放 .ogg 声音
- swiftui - SwiftUI:点击键盘的返回键会擦除所有表单数据
- go - 继续默认为什么其他情况没有被打印出来