杨辉三角||

大忽悠爱学习

发布于 2021-11-15 10:18:02

4330

发布于 2021-11-15 10:18:02

文章被收录于专栏：c++与qt学习

法1：递归求解

class Solution {
public:
        vector<int> getRow(int rowIndex) 
        {
            vector<int> ret;
            vector<int> prior;//记录上一层元
            //默认值为1
            ret.resize(rowIndex+1,1);
            prior.resize(rowIndex + 1, 1);
            display(ret, prior,rowIndex);
            return ret;
        }
        void display(vector<int>& ret,vector<int>& prior ,int numRows)
        {
            if (numRows == 1 || numRows == 0)
            {
                return;
            }
            display(ret, prior,numRows - 1);
            //prior负责保存上一层的值
            prior.resize(numRows, 1);
            prior = ret;
            //ret负责计算当前层的值
            ret.resize(numRows+1, 1);
            for (int i = 1; i < ret.size() - 1; i++)
            {
                ret[i] = prior[i - 1] + prior[i];
             }
        }
    };

法2：递推

class Solution {
public:
        vector<int> getRow(int rowIndex) 
        {
            vector<vector<int>> ret(rowIndex+1);
            for (int i = 0; i <= rowIndex; i++)
            {
                ret[i].resize(i + 1);
                ret[i][0] = ret[i][i] = 1;
                //j=1开始，j<i-->确保从从第三行开始递推
                for (int j = 1; j < i; j++)
                {
                    ret[i][j] = ret[i-1][j - 1] + ret[i-1][j];
                }
            }
            return ret[rowIndex];
        }
    };

优化注意到对第 i+1i+1 行的计算仅用到了第 i 行的数据，因此可以使用滚动数组的思想优化空间复杂度。

class Solution {
public:
        vector<int> getRow(int rowIndex) 
        {
            vector<int> cur;//当前层
            vector<int> pre;//上一层
            for (int i = 0; i <=rowIndex; i++)
            {
                cur.resize(i + 1);
                cur[0] = cur[i] = 1;
                for (int j = 1; j < i; j++)
                {
                    cur[j] = pre[j - 1] + pre[j];
                }
                pre = cur;//pre记录上一层元素
            }
            return cur;
        }
};

进一步优化 能否只用一个数组呢？

class Solution {
public:
        vector<int> getRow(int rowIndex) 
        {
            vector<int> ret(rowIndex + 1);
            ret[0] = 1;
            for (int i = 1; i <=rowIndex; i++)
            {
                for (int j = i; j > 0; j--)
                {
                    ret[j] += ret[j - 1];
                }
            }
            return ret;
        }
    };