博文中会简要介绍Leetcode P0119题目分析及解题思路。
“Pascal’s Triangle II”是一道比较基础的题目，同样按题目要求迭代计算即可。如果想要在O(k)时间复杂度中完成，需要运用到数学技巧。C++代码实现了数学技巧并且在O(k)的复杂度中完成，思路在代码中已经注释，这里就不再赘述了。
Given an integer rowIndex, return the rowIndexth row of the Pascal’s triangle.
In Pascal’s triangle, each number is the sum of the two numbers directly above it.
Notice that the row index starts from 0.Follow up:
Could you optimize your algorithm to use only O(k) extra space?
以下是Java的题解代码实现。
class Solution {
public List<Integer> getRow(int rowIndex) {
List<List<Integer>> triangle = new ArrayList<>();
rowIndex += 1;
for (int row=1; row<=rowIndex; ++row) {
List<Integer> level = new ArrayList<>();
for (int col=1; col<=row; ++col) {
if (col == 1 || col == row)
level.add(1);
else {
int left = triangle.get(row-2).get(col-2);
int right = triangle.get(row-2).get(col-1);
level.add(left+right);
}
}
triangle.add(level);
}
return triangle.get(rowIndex-1);
}
}
以下是C++的题解代码实现。
class Solution {
public:
vector<int> getRow(int rowIndex) {
// O(k) Space and Time Complexity (Math)
// We know that the elements of the ith line of pascal triangle is just the coefficients of the expansion of:
// (a + b) ^ i
// For example, the 4th line:
// 1 4 6 4 1
// (a + b) ^ 4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4
// And the we know the coefficients can be computed by composition. For the above example, the coefficients are respectively C(4, 0), C(4, 1), C(4, 2), C(4, 3), C(4, 4).
// Then we have the following code:
vector<int> kth_row(rowIndex+1, 1);
long combns = 1;
for (int itr=1; itr<rowIndex; ++itr) {
combns = (combns*(rowIndex-itr+1))/itr;
kth_row[itr] = combns;
}
return kth_row;
}
};