【leetcode】Pascal's Triangle I & II (middle)

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

思路:杨辉三角,直接按规律生成即可

vector<vector<int> > generate(int numRows) {
vector<vector<int>> ans;
for(int i = ; i < numRows; i++)
{
vector<int> v(i + , );
for(int j = ; j < i; j++)
{
v[j] = ans[i - ][j - ] + ans[i - ][j];
}
ans.push_back(v);
}
return ans;
}

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?

思路:

要靠数学公式了,设杨辉三角的最顶层为第0行,每行的第一个数字是第0个,则

第 i 行第 j 个元素的计算为:C(i, j) =  (i)! / (j)! * (i - j)!

那么第 i 行第 j 个元素和它前一个元素的关系是  ans[i][j] = ans[i][j - 1] * (i - j + 1) / j; //这里要注意不要越界

vector<int> getRow(int rowIndex) {
vector<int> ans(rowIndex + , );
ans[rowIndex - ] = ans[] = rowIndex;
for(int i = ; i < rowIndex / + ; i++)
{
ans[rowIndex - i] = ans[i] = (long long)ans[i - ] * (rowIndex - i + ) / i; //用long long防止越界 同时利用杨辉三角的对称性减少一半的计算量
}
return ans;
}
上一篇:【风马一族_Android】Android 前端内容1


下一篇:face recognition[MobiFace]