题目

给定一个非负整数 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
    • 遍历当前行的中间数字,从1rowIndex - 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)。

示例和测试

假设给定一个示例 rowIndex4,我们可以生成帕斯卡三角形的第 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)。解决这个问题有助于理解递归在数学问题中的应用。

标签: 编程算法, 编程算法题, 编程算法大全, 编程算法流程, 算法设计与分析, 数据结构与算法, 算法优化, 算法实现, 常见编程算法, 编程算法入门, 编程算法进阶, 编程算法精通