1. 題目
1.1 英文題目
Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:
1.2 中文題目
輸出楊輝三角形的指定行
1.3輸入輸出
| 輸入 | 輸出 |
|---|---|
| rowIndex = 3 | [1,3,3,1] |
| rowIndex = 0 | [1] |
| rowIndex = 1 | [1,1] |
1.4 約束條件
0 <= rowIndex <= 33
2. 實驗平臺
IDE：VS2019
IDE版本：16.10.1
語言：c++11
3. 分析
這一題最簡單粗暴的方法就是先求出到指定行的楊輝三角形，之后再取最后一行作為結果，代碼為：
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<vector<int>> ans(rowIndex + 1);
for(int i = 0; i < rowIndex + 1; i++)
{
ans[i].resize(i + 1);
ans[i][0] = ans[i][i] = 1;
for(int j = 1; j < i; j++)
{
ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j];
}
}
return ans[rowIndex];
}
};
這樣做也固然沒問題，但是演算法很冗雜，不夠優化，我們可以適當優化下，不需要把所有行的結果都存盤起來，只需要保存最后一行，新代碼如下：
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> ans;
for(int i = 0; i < rowIndex + 1; i++)
{
vector<int> temp(i + 1);
temp[0] = temp[i] = 1;
for(int j = 1; j < i; j++)
{
temp[j] = ans[j - 1] + ans[j];
}
ans = temp;
}
return ans;
}
};
但是我們提交后發現演算法時間和空間復雜度都沒變，于是我在想還有沒有優化空間，我發現每行計算時都需要重新定義temp，并為其開辟記憶體空間，有待優化，故可以將其提前定義，并在每行計算時重定義temp大小，代碼如下：
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> ans;
vector<int> temp;
for(int i = 0; i < rowIndex + 1; i++)
{
temp.resize(i + 1);
temp[0] = temp[i] = 1;
for(int j = 1; j < i; j++)
{
temp[j] = ans[j - 1] + ans[j];
}
ans = temp;
}
return ans;
}
};
這次性能不錯，但是我覺得有個temp，還是很繁瑣，那么能不能去掉temp呢，但是如果去掉temp，遞推那一步就會涉及混亂，考慮到遞推關系式是j-1和j,于是我們可以在遞推時進行反向遞推，代碼如下：
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> ans;
for(int i = 0; i < rowIndex + 1; i++)
{
ans.resize(i + 1);
ans[0] = ans[i] = 1;
for(int j = i - 1; j > 0; j--)
ans[j] += ans[j - 1];
}
return ans;
}
};
這次演算法空間復雜度又提高了，另外，每次都要重新定義ans的尺寸，能不能不這么做呢？我想到每次回圈只是比之前尺寸多1，因此可以不重新定義尺寸，而是尺寸加1，即使用push_back();具體代碼如下：
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> ans;
for(int i = 0; i < rowIndex + 1; i++)
{
ans.push_back(1);
for(int j = i - 1; j > 0; j--)
ans[j] += ans[j - 1];
}
return ans;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/288946.html
標籤：C++
上一篇：Leetcode No.108 Convert Sorted Array to Binary Search Tree(c++實作）