Problema
A primeira linha é [1]. Cada linha seguinte começa e termina com 1. Todo elemento interno é a soma dos dois elementos imediatamente acima dele. Retorne as primeiras rows linhas, começando pelo único 1.
Implemente pascals_triangle(rows).
Entrada
rows: Quantas linhas gerar.
Saída
Retorne uma lista de linhas, começando do topo; cada linha é uma lista de inteiros.
Restrições
0 ≤ rows ≤ 60. Cada elemento cabe em um inteiro assinado de 64 bits. Zero linhas retorna uma lista vazia.
Exemplos
Entrada:
rows = 4
Saída esperada:
expected = [
[1],
[1, 1],
[1, 2, 1],
[1, 3, 3, 1]
]Entrada:
long long rows = 4;
Saída esperada:
std::vector<std::vector<long long>> expected = {
{1},
{1, 1},
{1, 2, 1},
{1, 3, 3, 1}
};Entrada:
long rows = 4;
Saída esperada:
long[][] expected = new long[][] {
new long[] {1},
new long[] {1, 1},
new long[] {1, 2, 1},
new long[] {1, 3, 3, 1}
};Explicação
O 2 na linha 3 é 1 + 1. Os dois 3 internos na linha 4 são 1 + 2 e 2 + 1.
Entrada:
rows = 0
Saída esperada:
expected = []Entrada:
long long rows = 0;
Saída esperada:
std::vector<std::vector<long long>> expected = {};Entrada:
long rows = 0;
Saída esperada:
long[][] expected = new long[][] {};Explicação
Nenhuma linha foi solicitada, então retorne uma lista vazia.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Cada linha começa e termina com 1, e os valores internos vêm dos dois valores acima.
Dica 2
Monte as linhas uma a uma a partir da linha anterior em vez de recalcular do zero.
Dica 3
Trate o caso da linha zero retornando uma lista vazia imediatamente.
Complexidade esperada
tempo O(rows^2), espaço extra O(rows^2)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.