Leetcode 119 - Pascal's Triangle II

題目

Problem#

給你 r 要你求第 r 層的帕斯卡三角形

想法#

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

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

AC Code#

Copy

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

view raw 119.cpp delivered with ❤ by emgithub

Copy

class Solution2 {
public:
    vector<int> getRow(int n)
    {
        vector<int> p[2] = {{1}, {1}};
 
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j < i; j++)
            {
                p[1][j] = p[0][j]+p[0][j-1];
            }
            p[1].push_back(1);
            p[0] = p[1];
        }
 
        return p[1];
    }
};

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

賞析#

• https://leetcode.com/problems/pascals-triangle-ii/discuss/38420/Here-is-my-brief-O(k)-solution
  • 先 resize 好 vector