LeetCode 119：杨辉三角

杨辉三角

题目描述

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

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例 1:

输入: 3输出: [1,3,3,1]

进阶:

你可以优化你的算法到 O(k) 空间复杂度吗？

思路1

初始化前两层，后面层直接累加左上方和右上方的数的和

代码实现

class Solution {public:    //思路：初始化前两层，后面层直接累加左上方和右上方的数的和    vector<vector<int>> generate(int numRows) {        vector<vector<int>> result(numRows);        if(numRows == 0){ return result;}        else if(numRows == 1)        {            result[0].push_back(1);            return result;        }        else if(numRows == 2)        {            result[0].push_back(1);            result[1].push_back(1);            result[1].push_back(1);             return result;        }        else{            result[0].push_back(1);            result[1].push_back(1);            result[1].push_back(1);            for(int i = 2; i < numRows;   i)            {                for(int j = 0; j <= i;   j)                {                    if(j == 0){result[i].push_back(1);}                    else if(j == i){result[i].push_back(1);}                    else{                        //cout<<" "<<result[i-1][j-1]<<"  "<<result[i-1][j]<<endl;                        int tmp = result[i-1][j-1]   result[i-1][j];                        result[i].push_back(tmp);                    }                }            }        }        return result;    }};

思路2

进阶，空间复杂度O(K),因为要使用O(K)的空间复杂度，所以创建rowIndex 1个元素的数组，因为第rowIndex行有rowIndex 1个元素从第1行开始计算直到rowIndex层，每一层计算该层具体数值，需要注意从后往前计算，避免了第i-1行计算结果被覆盖丢失

代码实现

class Solution {public:    //思路：因为要使用O(K)的空间复杂度，所以创建rowIndex   1个元素的数组，因为第rowIndex行有rowIndex   1个元素    //从第1行开始计算直到rowIndex层，每一层计算该层具体数值，需要注意从后往前计算，避免了第i-1行计算结果被覆盖丢失    vector<int> getRow(int rowIndex) {        vector<int> result(rowIndex   1,0);        result[0] = 1;        for(int i = 1; i <= rowIndex;   i){//表示第i行            for(int k = i; k > 0; --k){//k是第k个数 从i开始，是因为第i行共有i 1个数字，从后往前计算，避免了第i-1行计算结果被覆盖丢失                result[k] = result[k]   result[k-1];            }        }        return result;    }};