Pascal's Triangle II--LeetCode

港控/mmm° 2022-08-07 12:38 3阅读 0赞

# 题目： #

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层的数 
    void PascaltriangleKth(int k)
    {
    	vector<int> result(k,0);
    	int tmp1,tmp;
    	for(int i=0;i<k;i++)
    	{
    		for(int j=0;j<=i;j++)
    		{
    			if(j==0 || j==i)
    			{
    				tmp = 0;
    				tmp1 = 1;
    				result[j]=1;
    			}
    				
    			else
    			{
    				tmp = result[j];
    				result[j] += tmp1;
    				tmp1 = tmp;
    			}
    		}
    	}
    	
    	for(int j=0;j<result.size();j++)
    		cout<<result[j]<<" ";
    	cout<<endl; 
    }

需要使用两个变量来记录先前的两个值

vector<int> Trigangle(int k)
    {
    	int i,j;
    	vector<int> vec(k,1);
    	int pre,next;
    	for(i=1;i<=k;i++)
    	{
    		pre = vec[0];
    		next = vec[1];
    		for(j=1;j<i-1;j++)
    		{
    			vec[j] = pre+next;
    			pre = next;
    			next = vec[j+1];
    		}
    			
    	}
    	return vec;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，3人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode－118. Pascal's Triangle，119. Pascal's Triangle II

118 Problem: > Given numRows, generate the first numRows of Pascal’s triangle.For exa

浅浅的花香味﹌/ 2022年08月20日 13:28/ 0 赞/ 138 阅读

相关 Pascal's Triangle--LeetCode

题目： Given numRows, generate the first numRows of Pascal's triangle. For example, giv

Love The Way You Lie/ 2022年08月07日 12:37/ 0 赞/ 163 阅读

相关 Leetcode: Pascal's Triangle

题目： Given numRows, generate the first numRows of Pascal's triangle. For example, gi

逃离我推掉我的手/ 2022年08月07日 03:56/ 0 赞/ 134 阅读

相关 LeetCode118—Pascal's Triangle

LeetCode118—Pascal’s Triangle 原题 > Given numRows, generate the first numRows of Pa

刺骨的言语ヽ痛彻心扉/ 2022年07月26日 11:07/ 0 赞/ 159 阅读

相关 [leetcode]: 118. Pascal's Triangle

1.题目 Given numRows, generate the first numRows of Pascal’s triangle. For example, gi

川长思鸟来/ 2022年06月15日 06:15/ 0 赞/ 154 阅读

相关 118. Pascal's Triangle

Given numRows, generate the first numRows of Pascal's triangle. For example, given numR

我不是女神ヾ/ 2022年06月13日 11:21/ 0 赞/ 141 阅读

相关 119. Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle. For example,

我就是我/ 2022年05月31日 23:14/ 0 赞/ 155 阅读

相关 leetcode-118. Pascal's Triangle

题目杨辉三角 Given a non-negative integer numRows, generate the first numRows of Pascal’s

秒速五厘米/ 2022年03月08日 08:56/ 0 赞/ 159 阅读

相关 118. Pascal's Triangle

题目来源：[https://leetcode.com/problems/pascals-triangle/][https_leetcode.com_problems_pasc

灰太狼/ 2021年12月10日 03:11/ 0 赞/ 179 阅读

相关 leetcode--Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle. For example, given k = 3

短命女/ 2021年10月24日 03:46/ 0 赞/ 342 阅读