如何表示一个整数三角形？

Question

这解决了On-Topic中的“特定编程问题”

我正在处理一个来自Amazon Software Interview
问题是“给定一个三角形的整数，找到最大和的路径而不跳过。”在

我的问题是如何表示一个整数三角形？在

我在Triangle of Integers 上查了一下，发现一个三角形的整数看起来像

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

什么是最好的方法（数据结构）来表示这样的东西？我的想法是

^{pr2}$

这是表示这个三角形整数结构的最好方法吗？我曾考虑过使用二维矩阵结构，但它们必须有相同大小的数组。在

Answer 1

我会用带保护带的二维阵列。在下面的示例中，0表示数组中的无效项。最上面和最下面的行以及最左边和最右边的列都是保护带。其优点是，您的寻径算法可以在数组中漫游，而不必经常检查数组索引的越界。在

int[][] array =
{
    { 0, 0, 0, 0, 0, 0, 0 },
    { 0, 1, 0, 0, 0, 0, 0 },
    { 0, 2, 3, 0, 0, 0, 0 },
    { 0, 4, 5, 6, 0, 0, 0 },
    { 0, 7, 8, 9,10, 0, 0 },
    { 0,11,12,13,14,15, 0 },
    { 0, 0, 0, 0, 0, 0, 0 }
}; 

Answer 2

I thought about using a 2 dimensional matrix structure but those have to have arrays of the same size.

不正确。在

在Java中，可以使用数组来表示非矩形数据结构；例如

int[][] triangle = {{1}, 
                    {2, 3},
                    {4, 5, 6},
                    {7, 8, 9, 10},
                    {11, 12, 13, 14, 15}};

这是一种选择，尽管不一定是最方便的选择。在

Answer 3

你应该把它们放在线性存储器中，并以如下方式访问它们：

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

因为它是一个可预测的结构，所以每行开头的偏移量都有一个表达式。这将是最有效的方法。在