杨辉三角
前端小菜-贺俊兰 2020-08-30 LeetCode
# 题一
给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。
在杨辉三角中,每个数是它左上方和右上方的数的和。
示例
//输入: 5
//输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 题意拆分
分析题目得出如下信息:
- numRows不能为0,为0直接return []。
- 行数就是每行所拥有的元素个数。
- 每一行的每一个元素(除去首尾固定1)又是由它所对应的左上方的元素和右上方的元素的和组成的。
- 第一行和第二行元素都是固定1.所以其实逻辑推理应该从第三行开始。
# 双层循环
按照分析题目得出的基本信息,可以用最简单的递推,逐行推出所拥有的元素。代码如下
/**
* @param {number} numRows
* @return {number[][]}
*/
var generate = function(numRows) {
if( numRows === 0 ) return []
//最终数据集合
let result=[]
//一共numRows行
for( var i = 0 ; i < numRows ; i++ ){
//每行数字的个数即为行号、例如第1行1个数、第2行2个数
// list存储每行的元素
let list=[]
//直接写出没每行的首尾数字1
list[0]=1
list[i]=1
if(i>1){
//从第三行开始每个元素都是根据它的左上方和右上方的两个数相加得来的
//最后一个元素除外
for ( var j = 1 ; j < i ; j++ ) {
list[j]=result[i-1][j-1]+result[i-1][j]
}
}
//打印杨辉三角
result.push(list)
}
return result
};
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
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
# 题二
给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。
在杨辉三角中,每个数是它左上方和右上方的数的和。
示例:
输入: 3
输出: [1,3,3,1]
1
2
2
# 递推
与题一的解法一样,运用递推,逐行推导出所有元素,人后return出对应的行。思路一摸一样。不做展示。
# 通项公式
通过数学公式可以得出通项公式,按照通项公式来求解。如图
如果要求其中某一个数字
代码如下
/**
* @param {number} rowIndex
* @return {number[]}
*/
var getRow = function(rowIndex) {
//res*(n-k+1)/k
//k>0
if(rowIndex==0) return [1]
let res=1
let result=[res]
for(let i=1;i<rowIndex;i++){
res = (rowIndex-i+1)*res / i
result.push(res)
}
result.push(1)
return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17