如何表示整数的三角形？

Question

这解决了On-Topic的 "特定编程问题"

我正在处理来自亚马逊软件访谈的访谈
问题问题是"给定一个三角形的整数,找到最大值的路径而不跳过."

我的问题是你如何表示整数三角形？

我在Triangle of Integers上查看了这个,看到一个整数的三角形看起来像

1
2      3
4      5      6
7      8      9      10
11     12     13     14     15

表示此类内容的最佳方式(数据结构)是什么？我的想法是有类似的东西

int[] r1 = {1};
int[] r2 = {2, 3};
int[] r3 = {4, 5, 6};
int[] r4 = {7, 8, 9, 10};
int[] r5 = {11, 12, 13, 14, 15};

这是表示此三角形整数结构的最佳方式吗？我想过使用二维矩阵结构,但那些必须具有相同大小的数组.

Answer 1

您应该将它们放入线性内存中并按如下方式访问它们：

int triangular(int row){
 return row * (row + 1) / 2 + 1;
}

int[] r = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
for(int i=0; i<n_rows; i++){
 for(int j=0; j<=i; j++){
  System.out.print(r[triangular(i)+j]+" ");
 }System.out.println("");
}

row, column
if row>column:
 index=triangular(row)+column

由于它是一个可预测的结构，因此有一个表示每行开头的偏移量的表达式。这将是最有效的方法。