leecode 解题总结：119. Pascal's Triangle II

#include <iostream>#include <stdio.h>#include <vector>using namespace std;/*问题:Given an index k, return the kth row of the Pascal's triangle.For example, given k = 3,Return [1,3,3,1].Note:Could you optimize your algorithm to use only O(k) extra space?分析:给定下标k，返回地k行的杨辉三角，只能使用k个常量的空间。这个明显用公式(a+b)^n=C(n,k) * a^(n-k) * b^k 累加求和，其中k从0到nC(n,k) = n! / ( (k!) * (n-k)! )来计算，k从0到n输入:03输出:11,3,3,1,报错:输入21，溢出，用long long 仍然溢出：输入30溢出关键:1 关于溢出，看到阶乘想到long long,如果long long 溢出，用迭代求，迭代仍然报错，不能直接用result.at(i) = result.at(i-1) *(rowIndex - i + 1) / i;则之前的乘积必须用long long变量来求，后面存储最终结果用一下转换2C(n,k) = n! / ( (k!) * (n-k)! ) , i累加时， 初始结果为1，计算下一个结果是乘以:n/1,再下一个是(n-1)/2,(n-2)/3,...,1/n 。 但是这样计算需要转化为浮点数*/class Solution {public:    vector<int> getRow(int rowIndex) {        if(rowIndex < 0)		{			vector<int> result;			return result;		}		vector<int> result(rowIndex + 1 , 1);//初始化		//初始化阶乘，用long long也会溢出，说明题目想让我们迭代求		//C(n,k) = n! / ( (k!) * (n-k)! ) , i累加时， 		long long current = 1;		long long temp;		for(int i = 1 ; i <= rowIndex ; i++)		{			//result.at(i) = ( (fact.at(rowIndex) /  fact.at(i) ) / fact.at(rowIndex - i) );//类型转换没有用			//初始结果为1，计算下一个结果是乘以:n/1,再下一个是(n-1)/2,(n-2)/3,...,1/n 。 但是这样计算需要转化为浮点数			temp = current * (rowIndex - i + 1) / i;			current = temp;			result.at(i) = (int) temp;//转换为整形		}		return result;    }};void PRint(vector<int >& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		cout << result.at(i) << "," ;	}	cout << endl;}void process(){	 int num;	 Solution solution;	 vector<int > result;	 while(cin >> num )	 {		 result = solution.getRow(num);		 print(result);	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}