LeetCode Solution, Easy, 118. Pascal's Triangle

帕斯卡三角形

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:

PascalTriangleAnimated2.gif

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
    }
}

Did you find this article valuable?

Support 攻城獅 by becoming a sponsor. Any amount is appreciated!