[教學] Leetcode- Pascal's Triangle－一個小小工程師的心情抒發天地

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

Constraints:

1 <= numRows <= 30

關於巴斯卡三角形; 這一題一看就知道是用數學公式套進去的, 但礙於年代真的太過久遠, 這類型的公式基本上都已經還給數學老師了, 所以還是上谷歌大神找了一下; 而有了算是之後, 結果就不難了.

先上初版的程式碼,

int PascalsTriangle(int n, int r)
{
   // n = row, r = element
   // nCr = n! / r!(n-r)!
   //

   int fraction   = 1;
   int deneminator = 1;

   // n!
   for (int i = 1; i <= n; i++)
       fraction *= i;

   // r!
   for (int i = 1; i <= r; i++)
       deneminator *= i;

   // n-r
   int k = n - r;
   int temp = 1;
   for (int i = 1; i <= k; i++)
       temp *= i;
   // r!(n-r)!
   deneminator *= temp;

//nCr
return fraction / deneminator;
}

vector<vector<int>>generate(int numRows)
{
   vector<vector<int>> matrix;
   vector<int>row;
   row.push_back(1);
   matrix.push_back(row);

   if (numRows == 1)
       return matrix;

   for (int i = 1; i <= numRows; i++)
   {
       row.clear();
       for (int j = 0; j <= i; j++)
       {
           row.push_back(PascalsTriangle(i, j));
       }
       matrix.push_back(row);
   }
   return matrix;
}

接下來我們把公式寫進去generate裡面, 讓整體變的更精簡一點

vector<vector<int>>generate(int numRows)
{
   vector <vector <int>> res;
   vector <int> temp;
   temp.reserve(numRows);
   for (int i = 0; i < numRows; i++) {
       temp.push_back(1);
       for (int j = 1; j < i; j++) {
           temp[j] = res[i - 1][j - 1] + res[i - 1][j];
       }
       res.push_back(temp);
   }
   return res;
}