Pascal's Triangle

Q: Qual é a complexidade de tempo para gerar o triângulo de Pascal?

O(n²) para n linhas: o triângulo tem cerca de n²/2 entradas, e cada uma exige uma adição. Isso é ideal, já que você precisa escrever todas as entradas da saída. O espaço extra além da saída é O(1) .

Q: Como o triângulo de Pascal está relacionado aos coeficientes binomiais?

A entrada k da linha r , contando a partir de 0, é C(r, k) , o número de maneiras de escolher k itens entre r . A regra da soma é a identidade C(r, k) = C(r-1, k-1) + C(r-1, k) , e a soma da linha r é 2^r , o número de subconjuntos de r itens.

Q: Você consegue calcular uma linha sem construir as linhas acima dela?

Sim. Comece com 1 e obtenha cada próximo elemento a partir do anterior: C(r, k) = C(r, k-1) × (r-k+1) / k . Multiplique antes de dividir para que a divisão seja exata e use um inteiro de 64 bits para o produto. A linha r então leva O(r) de tempo.

FácilProgramação dinâmica

+10

No triângulo de Pascal, a primeira linha é [1]. Cada linha seguinte tem uma entrada a mais, começa e termina com 1, e cada entrada entre elas é a soma das duas entradas diretamente acima dela. Você recebe um inteiro numRows. Retorne as primeiras numRows linhas do triângulo, começando pela linha do topo, cada linha como um array de inteiros.

Função

generate(numRows: integer) → integer-2d-array

numRowsinteger: quantas linhas do triângulo construir
Retornainteger-2d-array: as primeiras numRows linhas, começando pela linha superior

Restrições

1 ≤ numRows ≤ 30
Todas as entradas das primeiras 30 linhas cabem em um inteiro assinado de 32 bits. A maior é 77558760, no meio da linha 30.

Exemplos

Entrada: numRows = 5
Saída: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Explicação: Cada entrada interna soma as duas que estão acima dela. Quarta linha: 3 = 1 + 2 e 3 = 2 + 1. Quinta linha: 4 = 1 + 3, 6 = 3 + 3, 4 = 3 + 1.

Entrada: numRows = 1
Saída: [[1]]
Explicação: Com uma linha, o triângulo é apenas o seu topo, [1].

Para ir além

Você consegue manter apenas um array e atualizá-lo no próprio lugar, linha após linha? Em que direção o loop interno deve ser executado e por quê?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Um elemento é a soma de dois elementos da linha acima. Avaliar essa regra do zero para cada elemento recalcula os mesmos valores, e o trabalho dobra a cada linha. As linhas que você retorna são as respostas armazenadas para esses problemas menores, então construa o triângulo de cima para baixo, cada linha a partir da anterior.

Calcule cada entrada recursivamente

Correta, mas não termina nos maiores testes

Intuição

Numere as linhas e as posições a partir de 0. A definição se torna uma função: entry(row, col) é 1 nas bordas, onde col é 0 ou row, e, caso contrário, entry(row-1, col-1) + entry(row-1, col). Ela está correta porque é a definição.

A recursão para apenas nas bordas, que retornam 1, então uma entrada de valor v leva cerca de 2v chamadas. A linha r soma até 2^r, então 30 linhas exigem cerca de 2^31 chamadas, mais de dois bilhões.

Algoritmo

Escreva entry(row, col): retorne 1 se col for 0 ou se col for igual a row.
Caso contrário, retorne entry(row-1, col-1) + entry(row-1, col).
Para cada row de 0 a numRows-1, colete entry(row, col) para cada col de 0 a row.
Retorne a lista de linhas.

def pascalEntry(row, col):
    if col == 0 or col == row:
        return 1  # the edges of the triangle
    return pascalEntry(row - 1, col - 1) + pascalEntry(row - 1, col)


def generate(numRows):
    triangle = []
    for row in range(numRows):
        triangle.append([pascalEntry(row, col) for col in range(row + 1)])
    return triangle

Construa cada linha a partir da linha acima

Intuição

A recursão continua pedindo entradas das linhas anteriores, e você constrói essas linhas mesmo assim. Portanto, calcule as linhas de cima para baixo e, enquanto preenche a linha r, leia a linha r-1, que já está pronta. Cada entrada custa uma adição: a tabela de respostas menores é a própria saída.

Começar cada linha com r + 1 uns define as duas extremidades, então as linhas 0 e 1, que não têm posições internas, não precisam de nenhum caso especial. O triângulo tem 1 + 2 + ... + n, cerca de n²/2, entradas, então o trabalho é O(n²), sem memória além da saída: 465 entradas para 30 linhas, em vez de dois bilhões de chamadas.

Algoritmo

Comece com uma lista de linhas vazia.
Para cada row de 0 a numRows-1, crie row + 1 uns.
Para cada col de 1 a row-1, defina-o como a soma das posições col-1 e col da linha anterior.
Acrescente a linha e continue. Retorne a lista.

def generate(numRows):
    triangle = [[1]]
    for row in range(1, numRows):
        above = triangle[-1]
        values = [1] * (row + 1)  # both edges are 1
        for col in range(1, row):
            values[col] = above[col - 1] + above[col]
        triangle.append(values)
    return triangle

Armadilhas e casos extremos

Retornar numRows + 1 linhas. Numeradas a partir de 0, a última linha necessária é numRows-1.
Executar o loop interno sobre as bordas. A posição 0 não tem pai à esquerda, e a posição row não tem pai à direita, então acessá-las ultrapassa os limites.
Um intervalo que falha em linhas pequenas. O 1..<row do Swift causa uma falha quando row é 0, e o 2:(row-1) do R faz a contagem regressiva até 1 quando row é 2.
Calcular os elementos usando fatoriais. C(29, 14) cabe em um int, mas 29! excede até mesmo um inteiro de 64 bits.
Adicionar o mesmo array para cada linha e depois alterá-lo. Todas as linhas da resposta acabam sendo a última.

Perguntas frequentes3

Qual é a complexidade de tempo para gerar o triângulo de Pascal?

O(n²) para n linhas: o triângulo tem cerca de n²/2 entradas, e cada uma exige uma adição. Isso é ideal, já que você precisa escrever todas as entradas da saída. O espaço extra além da saída é O(1).

Como o triângulo de Pascal está relacionado aos coeficientes binomiais?

A entrada k da linha r, contando a partir de 0, é C(r, k), o número de maneiras de escolher k itens entre r. A regra da soma é a identidade C(r, k) = C(r-1, k-1) + C(r-1, k), e a soma da linha r é 2^r, o número de subconjuntos de r itens.

Você consegue calcular uma linha sem construir as linhas acima dela?

Sim. Comece com 1 e obtenha cada próximo elemento a partir do anterior: C(r, k) = C(r, k-1) × (r-k+1) / k. Multiplique antes de dividir para que a divisão seja exata e use um inteiro de 64 bits para o produto. A linha r então leva O(r) de tempo.

def generate(numRows):
    # Escreva o código aqui

Teste #1

Teste #2

Argumento

numRows = 5

Saída Esperada

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]