Java算法题-解析帕斯卡三角形 II问题

题目

给定一个非负整数 rowIndex，返回帕斯卡三角形的第 rowIndex 行。

帕斯卡三角形如下所示：

      1
     1 1
    1 2 1
   1 3 3 1
  1 4 6 4 1

每个数字是前两个数字之和。帕斯卡三角形的第一行是 1，第二行是 1 1，以此类推。

引言

帕斯卡三角形是一个经典的数学问题，它的生成规律非常简单，每个数字都是上一行对应位置和前一个位置的数字之和。我们可以使用递归来生成帕斯卡三角形的指定行。

算法思路

1. 如果 rowIndex 等于 0，直接返回 [1]，因为第一行只有一个数字 1。

2. 使用递归来生成帕斯卡三角形的第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。
3. 返回生成的第 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)。解决这个问题有助于理解递归在数学问题中的应用。