Fork me on GitHub

leetcode之118. 杨辉三角

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

题目描述：

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

img

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

示例:

1
2
3
4
5
6
7
8
9
10
> 输入: 5
> 输出:
> [
>      [1],
>     [1,1],
>    [1,2,1],
>   [1,3,3,1],
>  [1,4,6,4,1]
> ]
>

解题思路一：

时间复杂度：$O(n^2)$,空间复杂度：$O(n)$.

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
28
29
30
31
32
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int> > vec;
        vector<int> temp;
        
        if(numRows < 1) return vec;
        
        temp.push_back(1);
        vec.push_back(temp);
        temp.clear();
        
        for(int i = 1; i < numRows; 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);
           vec.push_back(temp);

        }
       
        return vec;
        
    }
};

解题思路二：

时间复杂度：$O(n^2)$,空间复杂度：$O(n)$.

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
28
29
30
31
32
33
class Solution {
public:
   
// 思路比较简单和冗余
vector<vector<int> > generate(int numRows) 
{
	vector<vector<int> > result;
    
	if(numRows < 1) return result;
    
	vector<int > temp;
	temp.push_back(1);
	result.push_back(temp);
    
    // 从第二行开始进行迭代
	for(int i = 1;i < numRows;i++)
	{ 
		temp.clear();
		temp.push_back(1);
   		 // 对于每一行的数，进行计算
		for(int j = 0; j < i - 1;j++)
		{
            // 测试语句
            // cout << "j is " << j << endl;
			temp.push_back(result[i - 1][j] + result[i - 1][j + 1]);
		}
		temp.push_back(1);
		result.push_back(temp);
	} 
	return result;
        
}
};