如何表示整数的三角形?
How to represent a triangle of integers?
此地址来自 On-Topic
"a specific programming problem"
我正在处理来自 Amazon Software Interview
的面试问题
问题是“给定一个整数三角形,不跳过就找到最大和的路径。”
我的问题是你如何表示整数三角形?
我在 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};
这是表示三角形整数结构的最佳方式吗?我考虑过使用二维矩阵结构,但它们必须具有相同大小的数组。
您应该将它们放在线性内存中并按以下方式访问它们:
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
由于它是一个可预测的结构,所以有一个表达式表示每行开头的偏移量。这将是最有效的方法。
你根本不需要代表它!行的起始编号 r
(从 0 开始)由表达式给出:
r * (r + 1) / 2 + 1
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}};
这是一个选项,但不一定是最方便的选项。
我会使用带保护带的二维阵列。在下面的示例中,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 }
};
此地址来自 On-Topic
"a specific programming problem"我正在处理来自 Amazon Software Interview
的面试问题
问题是“给定一个整数三角形,不跳过就找到最大和的路径。”
我的问题是你如何表示整数三角形?
我在 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};
这是表示三角形整数结构的最佳方式吗?我考虑过使用二维矩阵结构,但它们必须具有相同大小的数组。
您应该将它们放在线性内存中并按以下方式访问它们:
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
由于它是一个可预测的结构,所以有一个表达式表示每行开头的偏移量。这将是最有效的方法。
你根本不需要代表它!行的起始编号 r
(从 0 开始)由表达式给出:
r * (r + 1) / 2 + 1
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}};
这是一个选项,但不一定是最方便的选项。
我会使用带保护带的二维阵列。在下面的示例中,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 }
};