Given an integer rowIndex
, return the rowIndexth
(0-indexed) row of the Pascal’s triangle.
In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:
Example 1:
Input: rowIndex = 3 Output: [1,3,3,1]
Example 2:
Input: rowIndex = 0 Output: [1]
Example 3:
Input: rowIndex = 1 Output: [1,1]
Constraints:
0 <= rowIndex <= 33
Follow up: Could you optimize your algorithm to use only O(rowIndex)
extra space?
Solution: Remember last row
Time complexity: O(n2)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
# Author: huahua class Solution { public: vector<int> getRow(int rowIndex) { vector<int> ans(1, 1); for (int i = 2; i <= rowIndex + 1; ++i) { vector<int> tmp(i, 1); for (int j = 1; j < i - 1; ++j) tmp[j] = ans[j] + ans[j - 1]; swap(ans, tmp); } return ans; } }; |
Related Problems
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment