118. Pascal's Triangle

題目敘述

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

Constraints:

• 1 <= numRows <= 30

題目翻譯

題目就如同名字一樣，給定一個數值，要算出等高的帕斯卡三角形。

解法解析

這題基本上就是簡單的算式，只需要專注在中間的數值，頭跟尾再塞入 1 即可了。

解法範例

Go

func generate(numRows int) [][]int {
    var triangle [][]int

    for i := 0; i < numRows; i++ {
        row := make([]int, i+1)
        row[0], row[i] = 1, 1
        for j := 1; j < len(row)-1; j++ {
            row[j] = triangle[i-1][j-1] + triangle[i-1][j]
        }
        triangle = append(triangle, row)
    }

    return triangle
}

JavaScript

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
    const triangle = [[1]];

    for (let i = 1; i < numRows; i++) {
        const row = [];
        const triangleLength = triangle.length - 1;

        for (let j = 1; j < i; j++) {
            row.push(
                triangle[triangleLength][j] +
                    triangle[triangleLength][j - 1]
            );
        }
        triangle.push([1, ...row, 1]);
    }

    return triangle;
};

Kotlin

class Solution {
    fun generate(numRows: Int): List<List<Int>> {
        val triangle = mutableListOf<List<Int>>()
        for (i in 0 until numRows) {
            val row = mutableListOf<Int>()
            for (j in 0..i) {
                if (j == 0 || j == i) {
                    row.add(1)
                } else {
                    row.add(triangle[i - 1][j - 1] + triangle[i - 1][j])
                }
            }
            triangle.add(row)
        }
        return triangle
    }
}

PHP

class Solution
{

    /**
     * @param Integer $numRows
     * @return Integer[][]
     */
    function generate($numRows)
    {
        $triangle = array();

        for ($row = 0; $row < $numRows; $row++) {
            $triangle[$row] = array();
            for ($col = 0; $col <= $row; $col++) {
                if ($col == 0 || $col == $row) {
                    $triangle[$row][$col] = 1;
                } else {
                    $triangle[$row][$col] = $triangle[$row - 1][$col - 1] + $triangle[$row - 1][$col];
                }
            }
        }

        return $triangle;
    }
}

Python

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        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 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

Rust

impl Solution {
    pub fn generate(num_rows: i32) -> Vec<Vec<i32>> {
        let mut triangle = Vec::new();
        for i in 0..num_rows as usize {
            triangle.push(vec![1; i+1]);
            for j in 1..i {
                triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
            }
        }
        return triangle;
    }
}

Swift

class Solution {
    func generate(_ numRows: Int) -> [[Int]] {
        var triangle = [[Int]]()

        for i in 0..<numRows {
            var row = [Int]()
            for j in 0..<i + 1 {
                if j == 0 || j == i {
                    row.append(1)
                } else {
                    row.append(triangle[i - 1][j - 1] + triangle[i - 1][j])
                }
            }
            triangle.append(row)
        }

        return triangle
    }
}