题目

给定一个非负整数 numRows,生成帕斯卡三角形的前 numRows 行。

帕斯卡三角形如下所示:

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

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

引言

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

算法思路

  1. 初始化一个二维数组 triangle,其中 triangle[i][j] 表示帕斯卡三角形的第 i 行第 j 列的数字。
  2. 遍历每一行i,从第二行开始(第一行已知为1):

    • 初始化 triangle[i][0] = 1,表示每一行的第一个数字为 1
    • 遍历每一列1,从第二列开始(第一列已知为1):

      • 计算 triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j],表示当前数字是上一行相邻两数字之和。
  3. 返回生成的帕斯卡三角形。

代码实现

以下是使用 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)。

示例和测试

假设给定一个示例 numRows5,我们可以生成帕斯卡三角形的前 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)。解决这个问题有助于理解循环和二维数组的应用。

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