题解

题面描述

给定一个非负整数 $numRows$，要求生成杨辉三角的前 $numRows$ 行。在杨辉三角中，每个数字都是它左上方和右上方数字的和。

思路

1. 初始化：从第一行开始，每行的首尾数字都为 $1$。
2. 递推关系：对于第 $i$ 行（$0$ 基下标），从第二个到倒数第二个数字，其值为上一行第 $j-1$ 和第 $j$ 个数字之和，即：$$row[j] = prev[j-1] + prev[j]$$
3. 逐行构建：依次构造每一行并将其加入最终结果中。

代码分析

• 输入输出处理：由于要求是 ACM 模式，代码需要从标准输入读取数据，并将结果输出到标准输出。
• 数据结构：使用二维数组或容器存储杨辉三角。
• 时间复杂度：外层循环运行 $numRows$ 次，内层循环最多运行 $numRows$ 次，总体复杂度为 $O(numRows^2)$，适合 $1 \leq numRows \leq 30$ 的情况。

C++

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    // 生成杨辉三角的前 numRows 行
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        for (int i = 0; i < numRows; i++) {
            vector<int> row(i + 1, 1); // 每一行的第一个和最后一个数字都是 1
            // 中间的数字通过上一行求和得到
            for (int j = 1; j < i; j++) {
                row[j] = res[i-1][j-1] + res[i-1][j]; // row[j] = prev[j-1] + prev[j]
            }
            res.push_back(row);
        }
        return res;
    }
};

int main() {
    int numRows;
    cin >> numRows;  // 读取输入的行数
    Solution sol;
    vector<vector<int>> triangle = sol.generate(numRows);
    // 输出杨辉三角，每行数字之间用空格分隔
    for (int i = 0; i < triangle.size(); i++) {
        for (int j = 0; j < triangle[i].size(); j++) {
            cout << triangle[i][j];
            if(j < triangle[i].size() - 1) cout << " ";
        }
        cout << endl;
    }
    return 0;
}

Python

class Solution:
    # 生成杨辉三角的前 numRows 行
    def generate(self, numRows: int):
        res = []
        for i in range(numRows):
            row = [1] * (i + 1)  # 每一行的第一个和最后一个数字都是 1
            # 对于中间的数字，根据上一行计算
            for j in range(1, i):
                row[j] = res[i-1][j-1] + res[i-1][j]  # $row[j] = prev[j-1] + prev[j]$
            res.append(row)
        return res

if __name__ == "__main__":
    import sys
    # 读取输入
    numRows = int(sys.stdin.readline())
    sol = Solution()
    triangle = sol.generate(numRows)
    # 按行输出，数字之间用空格分隔
    for row in triangle:
        print(" ".join(map(str, row)))

Java

import java.util.*;

public class Main {
    static class Solution {
        // 生成杨辉三角的前 numRows 行
        public List<List<Integer>> generate(int numRows) {
            List<List<Integer>> res = new ArrayList<>();
            for (int i = 0; i < numRows; i++) {
                List<Integer> row = new ArrayList<>();
                for (int j = 0; j <= i; j++) {
                    // 每一行的第一个和最后一个数字都是 1
                    if (j == 0 || j == i) {
                        row.add(1);
                    } else {
                        // 中间的数字等于上一行的相邻两个数字之和：row[j] = prev[j-1] + prev[j]
                        row.add(res.get(i-1).get(j-1) + res.get(i-1).get(j));
                    }
                }
                res.add(row);
            }
            return res;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int numRows = sc.nextInt();  // 读取输入的行数
        Solution sol = new Solution();
        List<List<Integer>> triangle = sol.generate(numRows);
        // 输出杨辉三角，每行数字之间用空格分隔
        for (List<Integer> row : triangle) {
            for (int i = 0; i < row.size(); i++) {
                System.out.print(row.get(i));
                if (i < row.size() - 1) {
                    System.out.print(" ");
                }
            }
            System.out.println();
        }
        sc.close();
    }
}

Leetcode 118.杨辉三角-原题链接

题目内容

给定一个非负整数 $numRows$，生成「杨辉三角」的前 $numRows$ 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

输入描述

一个非负整数 $numRows$

输出描述

输出杨辉三角的前$numRows$行

样例1

输入

5

输出

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

样例2

输入

1

输出

1

提示

• $1 <= numRows <= 30$