Plus One

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

Ambas as abordagens levam tempo O(n) para n dígitos, porque o caso em que todos são 9 percorre cada dígito. A versão com saída antecipada para após os 9s finais e usa espaço extra O(1) , exceto quando a resposta precisa de um novo dígito inicial.

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 transporte 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.

Para ir além

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

Solução

Um número de 100 dígitos excede o limite de qualquer inteiro de 64 bits, que chega perto de 1.8 × 10^19, então você não pode convertê-lo e somar. Some como se faz no papel, começando pelo último dígito e carregando o vai-um. Somar 1 altera apenas os 9s finais, que se tornam 0s, e o dígito à esquerda deles.

Some com transporte, dígito por dígito

Intuição

Comece com um vai-um de 1, o número que você está somando. Para cada algarismo, da direita para a esquerda, o total da coluna é o algarismo mais o vai-um: total % 10 vai para a resposta e total / 10 é o próximo vai-um. O total é no máximo 9 + 1 = 10, então o vai-um permanece 0 ou 1. Um vai-um que sobra após o primeiro algarismo se torna um novo algarismo inicial, como em 999 + 1 = 1000.

Você produz a resposta começando pelo último algarismo, então colete os algarismos nessa ordem e inverta-os no final. Isso leva tempo O(n) e usa um novo array de até n + 1 algarismos.

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

Pare no primeiro dígito menor que 9

Intuição

Um dígito menor que 9 absorve um vai-um: ele aumenta em um e todos os dígitos à sua esquerda mantêm seus valores. Somente um 9 passa o vai-um adiante, transformando-se em 0. Portanto, você pode parar no primeiro dígito menor que 9 e retornar o array de entrada, modificado no próprio lugar. Para [2, 9, 0, 9], o último 9 se torna 0, o 0 se torna 1, e você retorna [2, 9, 1, 0] sem ler os dois primeiros dígitos.

Se nenhum dígito for menor que 9, o número era 10^n - 1 e a resposta é 1 seguido de n zeros. Esse é o único caso que exige um novo array; portanto, nos demais casos, o espaço extra é O(1).

Algoritmo

Percorra os índices do último ao primeiro.
Se o dígito for menor que 9, aumente-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

Converter o array em um inteiro e depois voltar. Um inteiro de 64 bits comporta no máximo 19 ou 20 dígitos, então 100 dígitos causam overflow, 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]; um código que reescreve apenas as posições existentes retorna [0, 0, 0].
Somar 1 ao primeiro dígito. O array está na ordem do dígito mais significativo primeiro, então o algarismo das unidades é o último elemento.
Não retornar quando um dígito menor que 9 absorver o vai-um. O loop então altera dígitos que devem permanecer iguais: [1, 9, 3] deve se tornar [1, 9, 4].
Em Lua e R, os arrays começam em 1, então o último dígito está no índice n, não em n - 1.

Perguntas frequentes3

Qual é a complexidade de tempo de Plus One?

Ambas as abordagens levam tempo O(n) para n dígitos, porque o caso em que todos são 9 percorre cada dígito. A versão com saída antecipada para após os 9s finais e 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?

O número pode ter 100 dígitos, e um inteiro de 64 bits chega apenas 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 nesses casos, mas o código não pode ser usado em outras linguagens. Trabalhar dígito por dígito nunca causa overflow.

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

Use o método das colunas com um índice no final de cada vetor. Cada coluna soma os dois algarismos, considerando como 0 um algarismo ausente, além do transporte. Pare quando os dois vetores tiverem sido usados e o transporte for 0; em seguida, inverta os algarismos coletados.

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

Teste #1

Teste #2

Teste #3

Argumento

digits = [4, 3, 9]

Saída Esperada

[4, 4, 0]