Plus One

Q: Qual é a complexidade de tempo de Plus One?

Ambas as abordagens são executadas em tempo O(n) para n dígitos, porque, no pior caso, com todos os dígitos sendo 9, todas as posições são percorridas. A versão com saída antecipada para após os 9s finais, então, para um número que termina em um dígito menor que 9, ela executa uma etapa. Ela usa espaço extra O(1) , exceto quando a resposta precisa de um novo dígito inicial.

Q: Quando o resultado tem mais dígitos do que a entrada?

Somente quando todos os dígitos são 9. Então, o número é 10^n - 1 , e somar um resulta em 10^n : um 1 seguido de n zeros. Se algum dígito for menor que 9, ele absorve o vai-um, então o comprimento permanece o mesmo.

FácilMatemática e simulação

+10

Um número inteiro não negativo é armazenado como um array de seus dígitos decimais, digits, começando pelo dígito mais significativo: 472 é [4, 7, 2]. Some um ao número e retorne os dígitos do resultado no mesmo formato. O número pode ter até 100 dígitos, muito mais do que um inteiro de 64 bits comporta.

Função

plusOne(digits: integer-array) → integer-array

digitsinteger-array: os dígitos do número, do mais significativo para o menos significativo
Retornainteger-array: os dígitos do número mais um, do mais significativo para o menos significativo

Restrições

1 ≤ digits.length ≤ 100
0 ≤ digits[i] ≤ 9
digits não tem zero à esquerda, exceto o próprio número 0, que é [0].

Exemplos

Entrada: digits = [4, 3, 9]
Saída: [4, 4, 0]
Explicação: O número é 439, e 439 + 1 = 440. O último dígito, 9, se transforma em 0 e passa um vai-um para o 3, que se torna 4.

Entrada: digits = [0]
Saída: [1]
Explicação: O número 0 é escrito como [0], e 0 + 1 = 1.

+13 testes ocultos ao enviar

Para ir além

Como você subtrairia um, em vez disso, para um número de pelo menos 1? Quais dígitos mudam, e quando o resultado perde seu dígito inicial, como em [1, 0, 0]?

Solução

Converter os dígitos em um número, adicionar um e converter de volta falha aqui: 100 dígitos excedem o limite de qualquer inteiro de 64 bits, que vai até cerca de 1.8 × 10^19. Então, você soma como faria no papel, começando pelo último dígito e levando um. A observação que encurta o trabalho: adicionar 1 altera apenas os 9s finais, que se tornam 0s, e o primeiro dígito à esquerda deles. Todos os outros dígitos permanecem como estão.

Adição com transporte, dígito por dígito

Intuição

Escreva o número e some 1 abaixo de seu último dígito, como na escola. Comece com um vai-um de 1, que é o valor que você está somando. Em cada dígito, da direita para a esquerda, o total da coluna é o dígito mais o vai-um. Seu último dígito, total % 10, vai para a resposta, e seu dígito das dezenas, total / 10, é o vai-um para a próxima coluna.

Com um vai-um de 1, o total de uma coluna é no máximo 9 + 1 = 10, então o vai-um é sempre 0 ou 1. Se ainda restar um vai-um depois do primeiro dígito, a resposta ganha um novo dígito à esquerda: 999 + 1 precisa de uma quarta posição para o 1 de 1000.

A resposta sai primeiro com o último dígito, porque essa é a ordem em que você a calcula. Reúna os dígitos nessa ordem e inverta-os no final. Isso leva O(n) de tempo e exige um novo array com até n + 1 dígitos.

Algoritmo

Defina carry como 1 e comece uma lista vazia para a resposta.
Para cada dígito, do último ao primeiro, calcule total = digit + carry.
Adicione total % 10 à resposta e defina carry como total / 10, arredondado para baixo.
Após o loop, se carry for 1, adicione-o.
Inverta a resposta e retorne-a.

def plusOne(digits):
    result = []  # the answer, last digit first
    carry = 1  # the one you are adding
    for i in range(len(digits) - 1, -1, -1):
        total = digits[i] + carry
        result.append(total % 10)
        carry = total // 10
    if carry > 0:
        result.append(carry)
    result.reverse()
    return result

Parar no primeiro dígito menor que 9

Intuição

Observe o que acontece com o vai-um quando você soma exatamente 1. Um dígito menor que 9 o absorve: 3 vira 4, o vai-um passa a ser 0, e todos os dígitos mais à esquerda mantêm seus valores. Só um 9 repassa o vai-um, transformando-se em 0. Portanto, somar 1 significa: transformar os 9s finais em 0s e, em seguida, somar 1 ao dígito imediatamente à esquerda deles.

Percorra os dígitos da direita para a esquerda. Ao encontrar um 9, escreva 0 e continue. Ao encontrar qualquer outro dígito, aumente-o em um e retorne o array imediatamente, pois nada à sua esquerda pode mudar. Para [2, 9, 0, 9], o último 9 vira 0, o 0 vira 1, e você para com [2, 9, 1, 0] sem olhar para os dois primeiros dígitos.

Se o loop nunca encontrar um dígito menor que 9, todos os dígitos eram 9 e agora são 0. O número era 10^n - 1, então a resposta é um 1 seguido de n zeros. Esse é o único caso que precisa de um novo array. Em todos os outros casos, você altera a entrada no próprio lugar, então o espaço extra é O(1), e o loop executa uma vez para cada 9 final, mais uma etapa.

Algoritmo

Percorra os índices do último ao primeiro.
Se o dígito for menor que 9, incremente-o em um e retorne o array.
Caso contrário, o dígito é 9: defina-o como 0 e avance uma posição para a esquerda.
Se o loop terminar, todos os dígitos eram 9: retorne 1 seguido de n zeros.

def plusOne(digits):
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1  # no carry leaves this digit, so the rest stays as it is
            return digits
        digits[i] = 0  # 9 + 1 = 10: write 0 and carry one to the left
    # Every digit was 9: the answer is 1 followed by zeros.
    return [1] + digits

Armadilhas e casos extremos

As armadilhas são o estouro de inteiro e o caso em que todos os dígitos são 9.

Transformar o array em um inteiro e depois voltar. Ele passa nos testes pequenos, mas falha nos de 100 dígitos: um inteiro de 64 bits comporta no máximo 19 ou 20 dígitos, e um número de ponto flutuante perde os últimos dígitos ainda mais cedo.
Esquecer o dígito extra. [9, 9, 9] deve se tornar [1, 0, 0, 0], com quatro dígitos. Um código que apenas reescreve as posições existentes retorna [0, 0, 0].
Somar 1 ao primeiro dígito em vez do último. O array está na ordem do dígito mais significativo para o menos significativo, então o dígito das unidades fica no final.
Esquecer de retornar depois que um dígito menor que 9 absorve o transporte. Na versão com saída antecipada, o loop continua e altera dígitos que devem permanecer como estão. Em [1, 9, 3], apenas o 3 pode mudar; a resposta é [1, 9, 4].
Confundir a ordem dos índices em Lua e R, nos quais os arrays começam em 1: o último dígito fica no índice n, e um novo 1 à esquerda vai antes do índice 1.

Perguntas frequentes4

Qual é a complexidade de tempo de Plus One?

Ambas as abordagens são executadas em tempo O(n) para n dígitos, porque, no pior caso, com todos os dígitos sendo 9, todas as posições são percorridas. A versão com saída antecipada para após os 9s finais, então, para um número que termina em um dígito menor que 9, ela executa uma etapa. Ela usa espaço extra O(1), exceto quando a resposta precisa de um novo dígito inicial.

Por que não converter os dígitos em um número inteiro?

Como o número pode ter 100 dígitos e um inteiro de 64 bits chega a cerca de 1.8 × 10^19, que tem 20 dígitos. Python e Ruby têm inteiros ilimitados, então a conversão funciona nessas linguagens, mas isso oculta o objetivo do exercício e não se aplica a outras linguagens. Trabalhar dígito por dígito nunca causa estouro.

Quando o resultado tem mais dígitos do que a entrada?

Somente quando todos os dígitos são 9. Então, o número é 10^n - 1, e somar um resulta em 10^n: um 1 seguido de n zeros. Se algum dígito for menor que 9, ele absorve o vai-um, então o comprimento permanece o mesmo.

Como somar dois números armazenados em arrays de dígitos?

Use o método das colunas da primeira abordagem, com dois índices, um no final de cada array. Cada coluna soma os dois dígitos, considerando um dígito ausente como 0, mais o vai-um. Continue até que os dois arrays tenham sido percorridos e o vai-um seja 0; em seguida, inverta os dígitos coletados.

Python

def plusOne(digits):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

digits = [4, 3, 9]

Esperado

[4, 4, 0]