Java算法题-解析帕斯卡三角形问题
题目
给定一个非负整数 numRows
,生成帕斯卡三角形的前 numRows
行。
帕斯卡三角形如下所示:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
每个数字是前两个数字之和。帕斯卡三角形的第一行是 1
,第二行是 1 1
,以此类推。
引言
帕斯卡三角形是一个经典的数学问题,它的生成规律非常简单,每个数字都是上一行对应位置和前一个位置的数字之和。我们可以使用循环来生成帕斯卡三角形。
算法思路
- 初始化一个二维数组
triangle
,其中triangle[i][j]
表示帕斯卡三角形的第i
行第j
列的数字。 遍历每一行
i
,从第二行开始(第一行已知为1
):- 初始化
triangle[i][0] = 1
,表示每一行的第一个数字为1
。 遍历每一列
1
,从第二列开始(第一列已知为1
):- 计算
triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]
,表示当前数字是上一行相邻两数字之和。
- 计算
- 初始化
- 返回生成的帕斯卡三角形。
代码实现
以下是使用 Java 实现的解决方案:
import java.util.ArrayList;
import java.util.List;
public class PascalTriangle {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<>();
if (numRows <= 0) {
return triangle;
}
for (int i = 0; i < numRows; i++) {
List<Integer> row = new ArrayList<>();
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i) {
row.add(1);
} else {
int sum = triangle.get(i - 1).get(j - 1) + triangle.get(i - 1).get(j);
row.add(sum);
}
}
triangle.add(row);
}
return triangle;
}
public static void main(String[] args) {
PascalTriangle solution = new PascalTriangle();
int numRows = 5;
List<List<Integer>> result = solution.generate(numRows);
// 打印帕斯卡三角形
for (List<Integer> row : result) {
for (Integer num : row) {
System.out.print(num + " ");
}
System.out.println();
}
}
}
算法分析
- 时间复杂度:遍历每个数字一次,所以时间复杂度是O(numRows^2),其中numRows是生成的行数。
- 空间复杂度:使用了一个二维数组来存储帕斯卡三角形,所以空间复杂度是O(numRows^2)。
示例和测试
假设给定一个示例 numRows
为 5
,我们可以生成帕斯卡三角形的前 5
行。我们可以使用以下代码进行测试:
public class Main {
public static void main(String[] args) {
PascalTriangle solution = new PascalTriangle();
int numRows = 5;
List<List<Integer>> result = solution.generate(numRows);
// 打印帕斯卡三角形
for (List<Integer> row : result) {
for (Integer num : row) {
System.out.print(num + " ");
}
System.out.println();
}
}
}
总结
生成帕斯卡三角形是一个经典的数学问题,它的规律非常简单,每个数字都是上一行相邻两数字之和。我们使用循环来生成帕斯卡三角形,每一行的数字依赖于上一行的数字。这个问题的时间复杂度是O(numRows^2),空间复杂度是O(numRows^2)。解决这个问题有助于理解循环和二维数组的应用。