LeetCode 119 Pascal's Triangle II（帕斯卡三角形II）（vector、數學公式）（*）

LeetCode 119 Pascal's Triangle II（帕斯卡三角形II）（vector、數學公式）（*）

翻譯

給定一個索引K，返回帕斯卡三角形的第K行。

例如，給定K=3，
返回[1,3,3,1]。

注釋：
你可以改進你的算法只用O(k)的額外空間嗎？

原文

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?

分析

這一題呢實際上是承接上一題的，我也正好剛寫完。

LeetCode 118 Pascal’s Triangle（帕斯卡三角形）（vector）

上一題是返回完整的帕斯卡三角形：

class Solution {
public:
    vector> generate(int numRows) {
        vector> pascal;
        if (numRows < 1) return pascal;
        vector root;
        root.push_back(1);
        pascal.push_back(root);
        if (numRows == 1)   return pascal;
        root.push_back(1);
        pascal.push_back(root);
        if (numRows == 2)   return pascal;
        if (numRows > 2) {
            for (int i = 2; i < numRows; ++i) {
                vector temp;
                temp.push_back(1);
                for (int j = 1; j < pascal[i - 1].size(); ++j) {
                    temp.push_back(pascal[i - 1][j - 1] + pascal[i - 1][j]);
                }
                temp.push_back(1);
                pascal.push_back(temp);
            }
            return pascal;
        }
    }
};

所以我就偷個懶，既然是索引K，那就返回它好了，不過效率就……

class Solution {
public:
    vector getRow(int rowIndex) {
        rowIndex += 1;
        vector> pascal;
        if (rowIndex < 1) return pascal[0];
        vector root;
        root.push_back(1);
        pascal.push_back(root);
        if (rowIndex == 1)  return pascal[0];
        root.push_back(1);
        pascal.push_back(root);
        if (rowIndex == 2)  return pascal[1];
        if (rowIndex > 2) {
            for (int i = 2; i < rowIndex; ++i) {
                vector temp;
                temp.push_back(1);
                for (int j = 1; j < pascal[i - 1].size(); ++j) {
                    temp.push_back(pascal[i - 1][j - 1] + pascal[i - 1][j]);
                }
                temp.push_back(1);
                pascal.push_back(temp);
            }
            return pascal[rowIndex - 1];
        }
    }
};

更高效的方法應該是有某種公式了，看看別人寫的就知道了……

vector getRow(int rowIndex) {
    vector r;
    r.resize(rowIndex + 1);
    r[0] = r[rowIndex] = 1;
    for (auto i = 1; i < (r.size() + 1) / 2; ++i) {
        r[i] = r[rowIndex - i] = (unsigned long)r[i - 1] * (unsigned long)(rowIndex - i + 1) / i;
    }
    return r;
}

果然，數學的威力再次顯現了。讓我用Markdown語法寫出這個公式……

ri=ri?1?(index?i+1)/i