3ms solution (Can it be improved?)

• ``````class Solution {
public:
vector<vector<int> > generate(int numRows) {
vector<vector<int> > triangle;
vector<int> previous;

if (numRows > 0) {
for (unsigned int i = 0; i < (unsigned int) numRows; i++) {
vector<int> current;
if (i == 0) {
current.push_back(1);
triangle.push_back(current);
} else if (i == 1) {
current.push_back(1);
current.push_back(1);
triangle.push_back(current);
} else {
previous = triangle[i - 1];
for (unsigned int j = 0; j < i + 1; j++) {
if (j == 0 || j == i)
current.push_back(1);
else{
current.push_back(previous[j - 1] + previous[j]);
}
}
triangle.push_back(current);
}
}
}
return triangle;
}
};``````

• It didn't make much difference to the runtime, but you can make the code slightly leaner on memory by not creating a temporary variable for previous, and instead using a pointer (or reference). You also don't really need to handle special cases in their own blocks, as they are dealt with in the loop:

``````vector<vector<int> > generate(int numRows) {
vector<vector<int>> triangle;
vector<int> *previous;

for (int i = 0; i < numRows; ++i) {
vector<int> current;
for (int j = 0; j < i+1; ++j) {
if (j == 0 || j == i) {
current.push_back(1);
}
else {
current.push_back(previous->at(j-1) + previous->at(j));
}
}
triangle.push_back(current);

previous = &triangle[i];
}

return triangle;
}``````

• 哈哈，可以用中文说不呢？
我觉得只要一层一层往下生长就行，这应该是最优的，

• I got this idea because I somehow did the second part first.

``````   class Solution {
public:
vector<int> getRow(int rowIndex)
{
vector<int> A(rowIndex+1, 0);
A[0] = 1;
for(int i=1; i<rowIndex+1; i++)
for(int j=i; j>=1; j--)
A[j] += A[j-1];
return A;
}
vector<vector<int>> generate(int numRows)
{

vector<vector<int>> b;
for(int i=1;i<=numRows;i++)
{
b.push_back(getRow(i-1));
}
return b;
}

};
``````

• ``````vector<vector<int>> result;
for (int i = 0; i < numRows; i++){
vector<int> t(i + 1, 1);
result.push_back(t);
if (i >= 2){
for (int j = 1; j < t.size() - 1; j++){
result[i][j] = result[i - 1][j - 1] + result[i - 1][j];
}
}
}
return result;
``````

0 ms :)

• Nice solution! So simple.

• 笑死了，你是我看到的第一个中文回复

• @chengzhoukun bu yao yong zhong wen hui fu

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.