题目
给定一个行号，返回杨辉三角的第 N 行的数列。
解析
如果从空间维度完整构造一个拥有 N 行的杨辉三角，需要 N ! 个存储单位。考虑杨辉三角的特殊性，第 N+1 行的第 I 个元素值为 c(n+1)(i) = c(n)(i-1) + c(n)(i)。
所以考虑从后往前计算新的行。具体的方法时
- 每次新增一行时，在末尾补 1
- 计算 i-1 的值并更新，直到首元素不再计算
伪代码
c = [row+1]int
c[0] = 1
for (r = 1; r<=row; r++)
c[r] = 1
for(i = r-1; i > 0; i--)
c[i] = c[i] + c[i-1]
return c
代码
func getRow(rowIndex int) []int {
row := rowIndex
c := make([]int, row+1)
c[0] = 1
for r := 1; r <= row; r++ {
c[r] = 1
for i := r-1; i > 0; i-- {
c[i] += c[i-1]
}
}
return c
}
image.png
网友评论