Leetcode 118 - Pascal's Triangle

題目

Problem#

給你 n 要你建 n 層的帕斯卡三角形

想法#

照著帕斯卡三角形的規則建立即可

• 時間複雜度: $\mathcal{O}(n^2)$
• 空間複雜度: $\mathcal{O}(n^2)$

AC Code#

Copy

class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> generate(int n)
    {
        if(n >= 1)
            ans.emplace_back(vector<int>{1});
        if(n >= 2)
            ans.emplace_back(vector<int>{1, 1});
        
        for(int i = 2; i < n; i++)
        {
            vector<int> tmp;
            tmp.push_back(1);
            for(int j = 0; j < ans[i-1].size()-1; j++)
            {
                tmp.push_back(ans[i-1][j] + ans[i-1][j+1]);
            }
            tmp.push_back(1);
            ans.push_back(tmp);
        }
        return ans;
    }
};

view raw 118.cpp delivered with ❤ by emgithub

Copy

class Solution2 {
public:
    vector<vector<int>> generate(int n)
    {
        vector<vector<int>> ans;
        for(int i = 1; i <= n; i++)
        {
            ans.push_back(vector<int>(i));
            auto &cur = ans.back();
            cur[0] = 1;
            if(n >= 2)
            {
                cur[i-1] = 1;
 
                auto &prev = *(ans.end()-2);
                for(int j = 1; j <= i-2; j++)
                    cur[j] = prev[j] + prev[j-1];
            }
        }
 
        return ans;
    }
};

view raw leetcode/118.cpp delivered with ❤ by emgithub

賞析#

• https://leetcode.com/problems/pascals-triangle/discuss/38171/Maybe-shortest-c%2B%2B-solution
  • 先建好 vector 再 resize，看起來蠻漂亮的