Java算法题-解析帕斯卡三角形 II问题
题目
给定一个非负整数 rowIndex
,返回帕斯卡三角形的第 rowIndex
行。
帕斯卡三角形如下所示:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
每个数字是前两个数字之和。帕斯卡三角形的第一行是 1
,第二行是 1 1
,以此类推。
引言
帕斯卡三角形是一个经典的数学问题,它的生成规律非常简单,每个数字都是上一行对应位置和前一个位置的数字之和。我们可以使用递归来生成帕斯卡三角形的指定行。
算法思路
- 如果
rowIndex
等于0
,直接返回[1]
,因为第一行只有一个数字1
。 使用递归来生成帕斯卡三角形的第
rowIndex
行:- 首先生成上一行的数字数组
prevRow
,通过递归调用generateRow(rowIndex - 1)
来获得。 - 初始化一个当前行的数字数组
currentRow
,长度为rowIndex + 1
。 - 设置当前行的第一个数字
currentRow[0]
为1
,因为每一行的第一个数字都是1
。 遍历当前行的中间数字,从
1
到rowIndex - 1
:- 计算
currentRow[i]
为prevRow[i-1] + prevRow[i]
,表示当前数字是上一行相邻两数字之和。
- 计算
- 设置当前行的最后一个数字
currentRow[rowIndex]
为1
,因为每一行的最后一个数字也是1
。
- 首先生成上一行的数字数组
- 返回生成的第
rowIndex
行。
代码实现
以下是使用 Java 实现的解决方案:
import java.util.ArrayList;
import java.util.List;
public class PascalTriangleII {
public List<Integer> generateRow(int rowIndex) {
if (rowIndex == 0) {
List<Integer> row = new ArrayList<>();
row.add(1);
return row;
}
List<Integer> prevRow = generateRow(rowIndex - 1);
List<Integer> currentRow = new ArrayList<>();
currentRow.add(1);
for (int i = 1; i < rowIndex; i++) {
int num = prevRow.get(i - 1) + prevRow.get(i);
currentRow.add(num);
}
currentRow.add(1);
return currentRow;
}
public static void main(String[] args) {
PascalTriangleII solution = new PascalTriangleII();
int rowIndex = 4;
List<Integer> result = solution.generateRow(rowIndex);
// 打印帕斯卡三角形的第 rowIndex 行
System.out.println(result);
}
}
算法分析
- 时间复杂度:生成第
rowIndex
行需要递归调用generateRow
方法,每次递归的时间复杂度为O(rowIndex),总共需要递归 rowIndex 次,所以总的时间复杂度是O(rowIndex^2)。 - 空间复杂度:递归调用栈的深度最多为 rowIndex,每次递归需要存储上一行的数字数组,所以总的空间复杂度是O(rowIndex)。
示例和测试
假设给定一个示例 rowIndex
为 4
,我们可以生成帕斯卡三角形的第 4
行。我们可以使用以下代码进行测试:
public class Main {
public static void main(String[] args) {
PascalTriangleII solution = new PascalTriangleII();
int rowIndex = 4;
List<Integer> result = solution.generateRow(rowIndex);
// 打印帕斯卡三角形的第 rowIndex 行
System.out.println(result);
}
}
总结
生成帕斯卡三角形的第 rowIndex
行是一个经典的数学问题,它的规律非常简单,每个数字都是上一行相邻两数字之和。我们使用递归来生成指定行的帕斯卡三角形,每一行的数字依赖于上一行的数字。这个问题的时间复杂度是O(rowIndex^2),空间复杂度是O(rowIndex)。解决这个问题有助于理解递归在数学问题中的应用。