杨辉三角

题目要求

编写一个函数，接收一个非负整数 numRows 作为参数，该函数的任务是生成一个包含「杨辉三角」前 numRows 行的列表。

「杨辉三角」是一个二维数组，其中第 n 行（行号从 0 开始）有 n + 1 个数字。对于三角形的每一行，第一个和最后一个数字总是 1。对于任何其他位置的数字，可以通过将上一行同一位置的数字和该位置前一个数字相加得到。

解题思路

初始化一个空列表 triangle，用于存储整个「杨辉三角」。
从第 0 行开始，一直到 numRows - 1 行，按行构建「杨辉三角」。
对于每一行，创建一个新的子列表 row，并将其添加到 triangle 中。
设置每一行的第一个元素和最后一个元素为 1，因为「杨辉三角」的边界总是 1。
对于第 i 行（i 从 0 开始计数）的中间元素，即 row[j]（j 从 1 开始到 i - 1 结束），可以通过 triangle[i-1][j-1] + triangle[i-1][j] 来计算。这里 triangle[i-1] 表示上一行，triangle[i-1][j-1] 和 triangle[i-1][j] 分别表示上一行的左上方和右上方的数。
重复步骤 3 到 5，直到构建完所有的行。
返回 triangle 列表，该列表现在包含了「杨辉三角」的前 numRows 行。

注意：在实际编码时，需要考虑 numRows 为 0 的特殊情况，此时应返回一个空列表。如果 numRows 为 1，则返回的列表中只包含一个元素 [1]。

Golang 版本

package main

import "fmt"

func generate(numRows int) [][]int {
    triangle := make([][]int, numRows) // 创建一个二维切片，用于存储杨辉三角的所有行

    for i := 0; i < numRows; i++ {
        triangle[i] = make([]int, i+1) // 初始化当前行，长度为 i+1
        triangle[i][0], triangle[i][i] = 1, 1 // 第一个和最后一个元素设置为 1

        // 从第二行开始，计算中间的元素
        for j := 1; j < i; j++ {
            // 上一行的左上方和右上方元素之和
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]
        }
    }

    return triangle
}

func main() {
    numRows := 5
    result := generate(numRows)
    for _, row := range result {
        fmt.Println(row)
    }
}

这段代码定义了一个 generate 函数，它接收一个 numRows 参数，并返回一个二维切片，其中包含了「杨辉三角」的前 numRows 行。在 main 函数中，我们调用了 generate 函数，并打印出返回的杨辉三角。

C++版本

#include <iostream>
#include <vector>

std::vector<std::vector<int>> generate(int numRows) {
    std::vector<std::vector<int>> triangle;

    for (int i = 0; i < numRows; ++i) {
        // 每一行的大小是行号+1
        std::vector<int> row(i + 1, 1); // 初始化当前行，并将所有元素设置为1

        // 计算非边界位置的元素值
        for (int j = 1; j < i; ++j) {
            row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
        }

        // 将当前行添加到杨辉三角中
        triangle.push_back(row);
    }

    return triangle;
}

int main() {
    int numRows = 5;
    std::vector<std::vector<int>> result = generate(numRows);

    // 打印杨辉三角
    for (const auto &row : result) {
        for (int num : row) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

这段代码定义了一个 generate 函数，它接收一个 numRows 参数，并返回一个 vector 容器，其中包含了「杨辉三角」的前 numRows 行。在 main 函数中，我们调用了 generate 函数，并打印出返回的杨辉三角。

Python 版本

def generate(numRows):
    triangle = []

    for row_num in range(numRows):
        # The first and last row elements are always 1.
        row = [None for _ in range(row_num + 1)]
        row[0], row[-1] = 1, 1

        # Each triangle element (except the first and last of each row)
        # is equal to the sum of the elements above-and-to-the-left and above-and-to-the-right.
        for j in range(1, len(row) - 1):
            row[j] = triangle[row_num - 1][j - 1] + triangle[row_num - 1][j]

        triangle.append(row)

    return triangle

# Example usage:
numRows = 5
triangle = generate(numRows)
for row in triangle:
    print(row)

这段代码定义了一个 generate 函数，它接收一个 numRows 参数，并返回一个列表，其中包含了「杨辉三角」的前 numRows 行。在示例用法中，我们调用了 generate 函数，并打印出返回的杨辉三角。

Java 版本

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<>();

        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                // First and last row elements are always 1.
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    // Each triangle element is equal to the sum of the elements
                    // above-and-to-the-left and above-and-to-the-right.
                    int left = triangle.get(i - 1).get(j - 1);
                    int right = triangle.get(i - 1).get(j);
                    row.add(left + right);
                }
            }
            triangle.add(row);
        }

        return triangle;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<List<Integer>> result = solution.generate(5);
        for (List<Integer> row : result) {
            for (int num : row) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }
}

这段代码定义了一个 Solution 类，其中包含了一个 generate 方法，它接收一个 numRows 参数，并返回一个 List，其中包含了「杨辉三角」的前 numRows 行。在 main 方法中，我们创建了 Solution 类的实例，并调用了 generate 方法，然后打印出返回的杨辉三角。

Rust 版本

fn generate(num_rows: i32) -> Vec<Vec<i32>> {
    let mut triangle: Vec<Vec<i32>> = Vec::new();

    for row_number in 0..num_rows as usize {
        // Start each row with a vector containing one element, 1.
        let mut row: Vec<i32> = vec![1; row_number + 1];

        // Each triangle element (except the first and last of each row)
        // is equal to the sum of the elements above-and-to-the-left and above-and-to-the-right.
        for j in 1..row_number {
            row[j] = triangle[row_number - 1][j - 1] + triangle[row_number - 1][j];
        }

        // Add the current row to the triangle.
        triangle.push(row);
    }

    triangle
}

fn main() {
    let num_rows = 5;
    let triangle = generate(num_rows);

    for row in triangle {
        for num in row {
            print!("{} ", num);
        }
        println!();
    }
}

这段代码定义了一个 generate 函数，它接收一个 num_rows 参数，并返回一个 Vec<Vec<i32>> 类型的向量，其中包含了「杨辉三角」的前 num_rows 行。在 main 函数中，我们调用了 generate 函数，并打印出返回的杨辉三角。

总结

在上述的解法中，无论是使用 Golang、C++、Python 还是 Rust，核心算法的逻辑是一致的。我们首先创建一个能够存储整个杨辉三角的数据结构，然后按行逐步构建每一行的内容。每一行的第一个和最后一个元素始终是 1，而行内的其他元素则是通过将上一行对应位置的元素与其前一个元素相加得到的。

具体步骤如下：

初始化一个空的数据结构（在不同语言中可能是动态数组、向量等）来存储整个三角形。
遍历从 0 到 numRows（不包括 numRows），对于每一行：
- 初始化当前行，并设置所有元素的默认值为 1。
- 对于当前行的中间元素（即非首尾元素），通过上一行的 triangle[i-1][j-1] + triangle[i-1][j] 来计算当前元素的值。
- 将构建好的当前行添加到三角形结构中。
在主函数中调用构建杨辉三角的函数，并打印或返回结果。

不同语言之间的主要区别在于语法和数据结构的使用。例如：

在 C++ 中，使用 std::vector 来动态存储数据。
在 Python 中，使用列表（list）来存储数据，并且语法更为简洁。
在 Java 中，使用 ArrayList 来存储数据，并且需要更多的类型声明。
在 Rust 中，使用 Vec 来存储数据，并且有明确的所有权和借用规则。

尽管实现的细节不同，但所有解法都遵循了相同的算法逻辑和步骤。

hot-100