119. Pascal's Triangle II
Problem
Given an integer rowIndex, return the rowIndexᵗʰ (0-indexed) row of the Pascal’s triangle.
In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:
https://leetcode.cn/problems/pascals-triangle-ii/
Example 1:
Input: rowIndex = 3
Output: [1,3,3,1]
Example 2:
Input: rowIndex = 0
Output: [1]
Example 3:
Input: rowIndex = 1
Output: [1,1]
Constraints:
Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?
Test Cases
1
2
| class Solution:
def getRow(self, rowIndex: int) -> List[int]:
|
solution_test.py1
2
3
4
5
6
7
8
9
10
11
12
13
| import pytest
from solution import Solution
@pytest.mark.parametrize('rowIndex, expected', [
(3, [1,3,3,1]),
(0, [1]),
(1, [1,1]),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, rowIndex, expected):
assert sol.getRow(rowIndex) == expected
|
Thoughts
杨辉三角的的每个数字都是一个组合数，第 n（0-indexed）行第 m（0-indexed）个数字的值为 (mn)=m!(n−m)!n!。
因为要输出一整行，还可以看一下同一行前后数字的递推关系，易知
(mn)=m!(n−m)!n!=m(m−1)!(n−m+1)!n!(n−m+1)=(m−1n)mn−m+1
这样就可以从第一个数（1）依次递推出整个数组。另外因为对称性，有 (mn)=(n−mn)，只需要计算前半个数组，后边个数组直接根据对称性填充即可。
时间复杂度 O(n)，附加的空间复杂度 O(1)。
Code
solution.py1
2
3
4
5
6
7
8
| class Solution:
def getRow(self, rowIndex: int) -> list[int]:
n = rowIndex
res = [1] * (n + 1)
for m in range(1, n // 2 + 1):
res[m] = res[n - m] = res[m - 1] * (n - m + 1) // m
return res
|
