Fork me on GitHub

leetcode之119. 杨辉三角 II

发表于 | 分类于
字数统计 253 字 | 阅读时长 1 分钟

题目描述：

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。

img

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

1
2
3
> 输入: 3
> 输出: [1,3,3,1]
>

进阶：

你可以优化你的算法到 O(k) 空间复杂度吗？

解题思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> temp;
        
        if(rowIndex < 0) return temp;
        
        temp.push_back(1);
        
        for(int i = 1; i <= rowIndex; i++)
        {
            temp.clear();
            for(int j = 0; j < i-1; j++)
            {
                if(temp[j+1])
                    temp.push_back(temp[j] + temp[j+1]);
                else
                    break;
            }

            temp.insert(temp.begin(), 1);
            temp.push_back(1);
        }
        
          return temp;
    }
};

解题思路二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> getRow(int rowIndex) {
	vector<int> vec;
	vec.push_back(1);
	if(rowIndex <= 0) return vec;
	// 注意这里的边界条件
	for(int i = 0 ; i <= rowIndex;i++)
	{
		vector<int> temp(i + 1,1);  //长度为i+1的数组，默认都是1
		for(int j = 1;j < i ;j++)
		{
			temp[j] = vec[ j ] + vec[ j - 1];
		}
		vec = temp;
		temp.clear();
	}
	return vec;
}