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

题目

给定一个非负整数 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)。

示例和测试

假设给定一个示例 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)。解决这个问题有助于理解循环和二维数组的应用。