欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

119. Pascal's Triangle II [杨辉三角形2]

程序员文章站 2022-04-01 12:40:48
...

描述

Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal’s triangle.
Note that the row index starts from 0.

给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k+1 行

例子
119. Pascal's Triangle II [杨辉三角形2]
思路

  • 方法1
    递归:不使用其他临时变量,重点:1,一开始将vector的长度设定为最终的长度;2,从i-1到1,获取值
  • 方法2:
    第n下标行第m下标列的数为:
    Cnm=AnmAmm=n(nm+1)m!=n!m!×(nm)! C_n^m=\frac{A_n^m}{A_m^m}=\frac{n\cdots (n-m+1)}{m!}=\frac{n!}{m!\times (n-m)!}
    第n下标行第m+1下标列的数为:
    Cnm+1=Cnm×nmm+1 C_n^{m+1}=C_n^m \times \frac{n-m}{m+1}

答案

  • python
class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        now=[1]*(rowIndex+1)
        i = 0
        while i<rowIndex:
            i += 1
            for j in range(i-1,0,-1):
                now[j]=now[j]+now[j-1]
            
        return now
*方法2*
	def getRow(self, rowIndex: int) -> List[int]:
        now = [1]*(rowIndex+1)
        for m in range(rowIndex):#通过前一个下标0~rowIndex-1,来获取下标1~rowIndex
            now[m+1] = int(now[m]*(rowIndex-m)/(m+1))
        return now
  • c++
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> now(rowIndex+1,1);
        int i=0;
        while (i++<rowIndex)
        {
            for (int j=i-1; j>=1; j--)
                now[j] = now[j]+now[j-1];
        }
        return now;
   }
}

*方法2*
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> now(rowIndex+1,1);
       
        for (int m=0; m<rowIndex; m++)
            now[m+1]=(long)now[m]*(long)(rowIndex-m)/(m+1);//因为相乘后超过范围,
     
        return now;
   
    }
};