118. Pascal's Triangle

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5, return

[

[1],

[1,1],

[1,2,1],

[1,3,3,1],

[1,4,6,4,1]

]

118. Треугольник Паскаля

Дано число numRows. Сгенерируйте первые numRows строк треугольника Паскаля.

Например, для numRows = 5 верните

[

[1],

[1,1],

[1,2,1],

[1,3,3,1],

[1,4,6,4,1]

]

// C++

class Solution {

public:

vector<vector<int>> generate(int numRows) {

}

};

// Java

public class Solution

{

public List<List<Integer>> generate(int numRows) {

}

}

РЕШЕНИЕ

структуры данных - двумерный массив

Анализ алгоритма

В динамическом двумерном массиве следует сгенерировать строки треугольника Паскаля.

Пусть m[i][j] – текущая ячейка массива. Тогда

m[i][0] = 1,

m[i][j] = m[i – 1][j – 1] + m[i – 1][j]

Реализация алгоритма

class Solution

{

public:

vector<vector<int> > generate(int numRows)

{

vector<vector<int> > res;

if (numRows == 0) return res;

vector<int> temp(1,1);

res.push_back(temp);

for(int i = 1; i < numRows; i++)

{

vector<int> c(i+1,1);

for(int j = 1; j < i; j++)

c[j] = res[i-1][j-1] + res[i-1][j];

res.push_back(c);

}

return res;

}

};

Java реализация

class Solution

{

public List<List<Integer>> generate(int numRows)

{

List<List<Integer>> res = new ArrayList<List<Integer>>();

if (numRows == 0) return res;

for (int i = 0; i < numRows; i++)

res.add(new ArrayList<Integer>());

res.get(0).add(1); // first row = [1]

for (int i = 1; i < numRows; i++)

{

res.get(i).add(1);

for (int j = 1; j < i; j++)

res.get(i).add(res.get(i - 1).get(j) + res.get(i - 1).get(j - 1));

res.get(i).add(1);

}

return res;

}

}