LeetCode Pascal's Triangle II （楊輝三角）

題意：給出楊輝三角的層數k，傳回最後一層。k=0時就是隻有一個數字1。

思路：滾動數組計算前一半出來，傳回時再複制另一半。簡單但是每一句都挺長的。

0ms的版本：

1 class Solution {
 2 public:
 3     vector<int> getRow(int rowIndex) {
 4         if(rowIndex==0) return vector<int>(1,1);    //0和1特殊處理
 5         if(rowIndex==1) return vector<int>(2,1);
 6         vector<int> ans[2];
 7         ans[0].push_back(1);    //隻需要處理一半，另一半在傳回時複制。
 8         for(int i=2; i<=rowIndex; i++)
 9         {
10             ans[~i&1].clear();              //滾動數組
11             ans[~i&1].push_back(1);         //這是必須的
12             int j=1;
13             for(; j<ans[i&1].size(); j++)    ans[~i&1].push_back( ans[i&1][j-1]+ans[i&1][j]);
14 
15             if(i%2==0)    ans[~i&1].push_back( ans[i&1][j-1]+ans[i&1][j-1] );   //k為偶數時，裡面有奇數個呢。
16         }
17 
18 
19         ans[rowIndex&1].clear();
20         ans[rowIndex&1].insert( ans[rowIndex&1].end(),ans[~rowIndex&1].begin(), ans[~rowIndex&1].end()  );
21 
22         if(!(rowIndex&1))
23             ans[rowIndex&1].insert( ans[rowIndex&1].end(),ans[~rowIndex&1].rbegin()+1, ans[~rowIndex&1].rend() );//總數為奇數個，最後1個不要複制進去。
24         else
25             ans[rowIndex&1].insert( ans[rowIndex&1].end(), ans[~rowIndex&1].rbegin(), ans[~rowIndex&1].rend() );//偶數個，全複制。
26         return ans[rowIndex&1];
27     }
28 };      

AC代碼

簡潔但4ms的版本：

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> ans(rowIndex+1,1);
        for(int i=1; i<rowIndex; i++)   //正在産生第i+2行。
        {
            for(int j=i; j>0; j--)      //必須從右開始，不然前面行就被覆寫了。
            {
                ans[j]+=ans[j-1];
            }
        }
        return ans;
    }
};      

作者：​​xcw0754​​

水準有限，若有疏漏，歡迎指出。