综合

leetcode:Pascal#39;s Triangle

导读: 

一、 题目

经典题目,杨辉三角,输入行数,生成杨辉三角的数组。

二、 分析

首先,我们知道有如下规律:

1、每一行的第一个数和最后一个数都为1

2、中间的数是上面数和上面数左边的数的和值

需要注意的是,当行数为0时输出[[1]]

结果为一个二维数组,所以不难想到解决方案。

每层保存前一行的指针,然后当前行数据根据上一行来得到,每个元素就是上一行两个相邻元素相加(第一个和最后一个元素是1)。算法时间复杂度应该是O(1+2+3+...+n)=O(n^2),空间上只需要二维数组来存储结果,不需要额外空间。:

<span style="font-size:18px;">//方法一: 
class Solution {
public:
    vector<vector<int> > generate(int numRows) {
        vector<vector<int>> cls;
        for(int i=0;i < numRows;i++) {
        	vector<int> flag;
        	if(i<=0) //flag.push_back(1);
        	   return cls;
        	else {
        		for(int j=0;j<=i;j++) {
        			if(j==0||j==i) flag.push_back(1);
        			else
        			  flag.push_back(cls[i-1][j-1]+cls[i-1][j]);
        		}
        	}
        	cls.push_back(flag);
        }
        return cls;
    }
};


//方法二:
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> cls;
        if(numRows<=0) return cls;
        cls.push_back(vector<int>(1,1));
        for(int i=1;i<numRows;i++) {
        	int cur_size = (int)cls[i-1].size();
        	vector<int> cur_ver;
			cur_ver.push_back(1);
			for(int j=1;j<cur_size;j++) {
				int flag = cls[i-1][j]+cls[i-1][j-1];
				cur_ver.push_back(flag);
			} 
			cur_ver.push_back(1);
			cls.push_back(cur_ver);
        }
        return cls;
    }
};




</span>

相关资讯

发表评论
网友评论0 条评论)
暂无评论