LeetCode118—Pascal's Triangle

刺骨的言语ヽ痛彻心扉 2022-07-26 11:07 159阅读 0赞

# LeetCode118—Pascal’s Triangle #

## 原题 ##

> Given numRows, generate the first numRows of Pascal’s triangle.
> 
> For example, given numRows = 5,  
> Return
> 
> \[  
> \[1\],  
> \[1,1\],  
> \[1,2,1\],  
> \[1,3,3,1\],  
> \[1,4,6,4,1\]  
> \]

## 分析 ##

输出特定层数的杨辉三角。

### 杨辉三角 ###

杨辉三角最重要的三个性质：  
1. 每个数等于它上方两数之和。  
2. 每行数字左右对称，由1开始逐渐变大。  
3. 第n行的数字有n项。  
如图所示：

![这里写图片描述][20160409205328275]

把这种三角形的形状往左边压缩成“直角三角形”，即：  
1  
1 1  
1 2 1  
1 3 3 1  
…  
直接用二维数组保存即可，初始化的时候第一列和对角线的值都是1，其他值可以由：

#### **a\[i\]\[j\]=a\[i-1\]\[j-1\]+a\[i-1\]\[j\]表示** ####

最后要注意的就是输出格式要除去多余的0（因为初始化的时候默认构造函数会自动赋0）

## 代码 ##

class Solution {
    public:
        vector<vector<int>> generate(int numRows) {
            int row=numRows;
            int col=numRows;
            vector< vector<int> >res(row,vector<int>(col));
            for (int i = 0; i < res.size(); i++)
            {
                res[i][0] = 1;
                res[i][i] = 1;
            }//初始化
            for (int i = 2; i < row; i++)
            {
                for (int j = 1; j < col; j++)
                {
                    if (i - 1>=0 && j - 1 >= 0)
                    {
                        res[i][j] = res[i - 1][j - 1] + res[i - 1][j];
                    }
                }
            }//赋值
            for(int i=0;i<row;i++)
            {
                for(int j=0;j<col;j++)
                {
                    if(res[i][j]==0)
                        res[i].pop_back();
                }
            }//删去0
            return res;
        }
    };

[20160409205328275]: /images/20220724/f5e3bb19536a4fd39c39c2605f9ecc00.png