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

Leetcode No.119 Pascal's Triangle II(c++实现)

程序员文章站 2022-06-19 12:16:54
1. 题目 1.1 英文题目 Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle. In Pascal's triangle, each number is the sum ......

1. 题目

1.1 英文题目

given an integer rowindex, return the rowindexth (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:

1.2 中文题目

输出杨辉三角形的指定行

1.3输入输出

输入 输出
rowindex = 3 [1,3,3,1]
rowindex = 0 [1]
rowindex = 1 [1,1]

1.4 约束条件

0 <= rowindex <= 33

2. 实验平台

ide:vs2019
ide版本:16.10.1
语言:c++11

3. 分析

这一题最简单粗暴的方法就是先求出到指定行的杨辉三角形,之后再取最后一行作为结果,代码为:

class solution {
public:
    vector<int> getrow(int rowindex) {
        vector<vector<int>> ans(rowindex + 1);
        for(int i = 0; i < rowindex + 1; i++)
        {
            ans[i].resize(i + 1);
            ans[i][0] = ans[i][i] = 1;
            for(int j = 1; j < i; j++)
            {
                ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j]; 
            }
        }
        return ans[rowindex];
    }
};

这样做也固然没问题,但是算法很冗杂,不够优化,我们可以适当优化下,不需要把所有行的结果都存储起来,只需要保存最后一行。新代码如下:

class solution {
public:
    vector<int> getrow(int rowindex) {
        vector<int> ans;
        for(int i = 0; i < rowindex + 1; i++)
        {
            vector<int> temp(i + 1);
            temp[0] = temp[i] = 1;
            for(int j = 1; j < i; j++)
            {
                temp[j] = ans[j - 1] + ans[j]; 
            }
            ans = temp;
        }
        return ans;
    }
};

但是我们提交后发现算法时间和空间复杂度都没变,于是我在想还有没有优化空间,我发现每行计算时都需要重新定义temp,并为其开辟内存空间,有待优化,故可以将其提前定义,并在每行计算时重定义temp大小,代码如下:

class solution {
public:
    vector<int> getrow(int rowindex) {
        vector<int> ans;
        vector<int> temp;
        for(int i = 0; i < rowindex + 1; i++)
        {
            temp.resize(i + 1);
            temp[0] = temp[i] = 1;
            for(int j = 1; j < i; j++)
            {
                temp[j] = ans[j - 1] + ans[j]; 
            }
            ans = temp;
        }
        return ans;
    }
};

这次性能不错。但是我觉得有个temp,还是很繁琐,那么能不能去掉temp呢,但是如果去掉temp,递推那一步就会涉及混乱,考虑到递推关系式是j-1和j,于是我们可以在递推时进行反向递推,代码如下:

class solution {
public:
    vector<int> getrow(int rowindex) {
        vector<int> ans;
        for(int i = 0; i < rowindex + 1; i++)
        {
            ans.resize(i + 1);
            ans[0] = ans[i] = 1;
            for(int j = i - 1; j > 0; j--)
                ans[j] += ans[j - 1];
        }
        return ans;
    }
};

这次算法空间复杂度又提高了,另外,每次都要重新定义ans的尺寸,能不能不这么做呢?我想到每次循环只是比之前尺寸多1,因此可以不重新定义尺寸,而是尺寸加1,即使用push_back();具体代码如下:

class solution {
public:
    vector<int> getrow(int rowindex) {
        vector<int> ans;
        for(int i = 0; i < rowindex + 1; i++)
        {
            ans.push_back(1);
            for(int j = i - 1; j > 0; j--)
                ans[j] += ans[j - 1];
        }
        return ans;
    }
};