#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;}